Moves that unlock problems

These questions turn "which technique is this?" into something concrete you can check. Each one suggests an idea to try. None of them replaces checking your assumptions or showing the solution is correct.

Ask what the rest of the problem needs to know

Two different histories can share a state only if everything that can happen next is the same for both. To find whether you can reach a cell in a grid, you only need the current cell. But if doors need keys, you also need which keys you hold. To plan purchases, you may need the remaining budget and your position, but not the order of earlier purchases.

Try this sentence: "If I tell you these variables, can you solve the rest without knowing how I got here?" If not, find the missing variable. If so, look for repeated states and save their answers. A good state is information you've safely forgotten.

Name the question your loop keeps asking

Before you pick a data structure, say the question in plain words: "Have I seen this value's partner?", "What's the earliest index with this prefix sum?", "Which task finishes first?", or "How many earlier values are below this one?"

Those questions point to a hash map, a hash map that keeps the earliest index, a heap, and a sorted counting structure. Naming the question also separates problems that look alike: "is it there", "how many", "what rank", and "what's smallest" are different questions.

Change how you represent the input

A different representation can reveal a pattern that the story hides. To find runs with equal numbers of zeros and ones, turn each 0 into −1. A balanced run then sums to zero. Turn allowed moves into graph edges. Turn time intervals into start and end events.

In LC 525 Contiguous Array, a repeated prefix sum of the converted list marks a balanced run, and keeping the earliest index of each sum gives the longest one. The discovery is the conversion plus the prefix sum lookup. "Use a hash map" alone misses it.

Fix one part and solve the rest

3Sum fixes one value, then solves Two Sum on the rest. Counting triangles from sorted side lengths can fix the longest side, then count pairs. Fixing a boundary, a center, the last value, or how many items you pick can turn a tangled problem into a simpler one.

Count the outer loop too. An O(n) method run for each of n fixed values costs O(n²). And don't fix something that destroys the structure the rest of the method relies on.

Ask "does this value work?" before "what's the best value?"

Finding the best value directly can be hard when checking one value is easy. Replace "what's the smallest capacity?" with "does this capacity work?" Then show that once a capacity works, every larger one does too.

The real work is usually the check: a greedy simulation, a graph search under a limit, or a DP. Binary search on the answer only cuts down how many checks you run. If the check is slow, or a larger value can fail after a smaller one works, this won't help.

Compare two options against the same future

To justify dropping option A for option B, imagine the same future for both. If B is always at least as good and at least as possible, you can drop A.

This one argument explains several techniques. In longest increasing subsequence, keep the smaller ending value for each length. In sliding window maximum, a newer, larger value pushes out older, smaller ones. In shortest subarray with sum at least K, a later prefix sum that's no larger replaces an earlier one. If two options trade off, such as one costing less and the other leaving more resources, neither wins; keep both, or add to the state.

Run time backward, or choose the last step first

Some data structures handle adding easily but deleting badly. If you know every operation in advance, running them in reverse turns deletions into additions. This needs the whole history up front; it doesn't help when operations arrive one at a time.

Choosing the last step first is a similar trick. In LC 312 Burst Balloons, pick which balloon in a range bursts last. Its neighbors outside the range are then fixed, so the left and right parts become independent problems. Ask whether choosing the last event gives you fixed boundaries.

Count what each element contributes

Instead of building every subarray and adding up its value, ask how many subarrays include each element. To total the sums of every subarray, index i appears in (i + 1) × (n − i) of them: that's the number of ways to pick a left end and a right end around it.

In LC 907 Sum of Subarray Minimums, count the subarrays where each element is the minimum. The nearest smaller element on each side marks the boundaries. With equal values, use < on one side and <= on the other, so each subarray is counted once. The hard part moves to deciding which element "owns" each subarray.

Count the opposite, or subtract two easier counts

Sometimes what you want is hard to count, but everything and the unwanted part are easy. Another useful formula: exactly(k) = at_most(k) − at_most(k − 1).

To count subarrays with exactly k distinct values, count those with at most k using a sliding window, and subtract those with at most k − 1. The formula is simple, but the at-most count still needs its own correct sliding window. Watch the cases k = 0 and k − 1 < 0.

Process events in an order that settles things

Sorting can turn a shifting rule into steady one-way progress. Say each query is a point and asks for the smallest interval containing it. Sort the points. Add intervals once their start is reached, and drop them once their end is passed. A min-heap picks the shortest interval left. Then put the answers back in the original query order.

LC 1851 Minimum Interval to Include Each Query works this way. Ask: "Can I reorder the work so each option enters once and leaves once?" That requires knowing every query up front.

Split a huge search into two halves

If trying all subsets is too slow but n is still moderate, list the subset sums of each half separately. Sort one half's sums, and for each sum in the other half, binary search for a good partner. That cuts 2ⁿ down to about 2^(n/2), at the cost of much more memory.

Any extra rule has to survive the split. If you must pick exactly half the elements, group each half's sums by how many elements they use, and only combine matching group sizes. LC 1755 Closest Subsequence Sum and LC 2035 Partition Array Into Two Arrays to Minimize Sum Difference show the difference. If the numbers are small, a DP over possible sums may be better.

Find a limit, then reach it

To prove an answer is the best, first show that nothing can beat some bound. Then build an answer that reaches it. Capacity, odd/even counts, the most frequent item, or a bottleneck can give you the bound.

Be careful: a bound isn't always reachable. An arrangement can pass a count-based bound and still break a rule between neighbors. Until you build a valid answer, the bound is only a bound. Scheduling formulas need the same checking as code.

Try to break your own idea with a tiny example

Before you code a greedy rule, try three or four items that pull in different directions. To test a sliding window on sums, include a negative number. To test a count, include duplicates and zeros. To test a graph state, revisit a node with different resources. To test edge cases, try an empty input, one item, all-equal values, and no answer.

When an input breaks your idea, keep shrinking it while it still fails. A six-element example often shows the missing assumption far more clearly than a random hundred-element one. Building counterexamples is a skill: each one tells you what your next idea must remember or prove.

Recognizing isn't the same as deriving

It's fine to recognize a familiar pattern right away. You don't need to reinvent known algorithms in an interview. What matters is that you can explain why the pattern fits, and adapt it when a rule changes.

If a solution feels like a trick, find the first step you can't justify. Did you assume that once a check passes, it keeps passing? Did you drop an option without showing it could never win? Did you pick a DP state without checking it holds everything the future needs? Fix that step, and the code usually follows.