Coding interview patterns: the 15 that keep coming back

Coding interview patterns are reusable solution shapes, and each one is really three things: a recognition cue, an invariant it maintains, and a repair action when the input threatens that invariant. Fifteen patterns cover the large majority of screening problems. Learn the cue and the invariant, and most medium-tier questions collapse into template selection plus edge cases.

That framing is the part usually left out. Every pattern list I have seen is a list of tags: sliding window, two pointers, BFS, DP. Tags tell you what a solution was called after the fact. They do not tell you how to arrive at it under pressure with a stranger watching. What follows is the catalogue rewritten so that each entry carries the thing you actually apply at minute three of an interview.

What is a coding interview pattern, exactly?

A pattern is not a problem category. It is a small machine defined by what it promises to keep true. Read three of them in that form and the family resemblance becomes obvious.

A sliding window promises that the current window is always valid. When you extend the right edge and the window becomes invalid, the repair is to advance the left edge until validity returns. A converging two-pointer scan on sorted input promises that the answer, if it exists, lies inside the range the pointers still bracket. When the current pair is too small, the repair is to move the left pointer right, because every pair the left pointer could still form with a smaller partner is also too small. Binary search promises that the answer lies within [lo, hi]. When the midpoint fails the predicate, the repair is to discard the half that provably cannot contain it.

Invariant plus repair is a better mental unit than a tag for three reasons. It is testable: you can state the invariant in one sentence and check it after each loop iteration while debugging. It is defensible: an interviewer asking "why is this correct?" is asking exactly what your invariant is, and a candidate who has one answers in ten seconds. And it produces the complexity argument almost for free, because the repair action is usually the thing you count. In a sliding window, each pointer only ever moves forward, so across the whole run the two pointers make at most 2n moves, which is where the O(n) comes from. Not from the pattern's reputation for being linear.

This is the companion piece to recognise the shape, not the problem. That essay argues you should study shapes rather than individual problems. This one is the reference table that argument implies.

Which 15 coding interview patterns cover most problems?

These fifteen, in rough order of how often they appear in technical screens. Each row gives the cue you can spot in the problem statement, the invariant the loop protects, the cost with its counting argument compressed to a phrase, and a walkthrough on this site to drill it.

A few patterns that appear on other lists are deliberately absent. Monotonic stacks, union-find, tries, and bitmask enumeration are real and worth knowing, but in screening rounds they show up rarely enough that learning them before the fifteen above is a poor use of a fixed study budget. Add them once the catalogue is automatic.

Which patterns should you learn first?

Start with the five that transfer the most: hash map seen-so-far, sliding window, converging two pointers, post-order tree recursion, and BFS. They transfer because their invariants reappear inside other patterns. The seen-so-far map is a subcomponent of sliding window with distinct-character conditions. Two pointers is the linear-scan cousin of binary search. Post-order recursion is the skeleton of tree DP.

The second tier is the search family: binary search on a sorted array, then binary search on the answer, then top-K with a heap. These share the idea that you can discard a provably useless portion of the search space without examining it, which is the single most reusable optimisation instinct in the whole catalogue.

Leave dynamic programming for last, not because it is unimportant but because it is the pattern most sensitive to the others. A DP solution is usually recursion plus memoisation, so if your recursive model is shaky the DP will be shakier. Work through state design only after tree recursion feels routine, and read memoisation versus tabulation before deciding which form to write in an interview.

How do you tell which pattern a problem wants?

Read the constraints before the prose. The size bound is the loudest signal in the problem and most candidates skip it. If n is at most 20, exponential search over subsets is expected and you should be thinking about backtracking or bitmasks. If n is at most a few thousand, an O(n²) double loop passes and you should not burn twenty minutes chasing linear. If n reaches 10⁵, you need O(n log n) at worst, which points at sorting, heaps, or binary search. If n reaches 10⁹, nothing that touches every element can run, so the answer is O(log n) or closed form, and binary search on the answer becomes the leading candidate.

After the constraint, ask what is monotone. Monotonicity is the property that makes discarding safe, and every discard-based pattern in the table depends on it. Then ask whether the question is about a contiguous run, because contiguity is what separates sliding window from the general subsequence problems that need DP. Here is the window template with its repair step marked:

def longest_valid_window(s, k):
    counts, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        # invariant: at most k distinct characters in s[left:right+1]
        while len(counts) > k:              # repair
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

The comment marks the only line that matters conceptually. Everything above it extends the window; everything inside the while restores the invariant the extension broke. When you narrate this solution to an interviewer, those two sentences are the entire explanation, and the complexity argument follows directly from them. The outer loop advances right exactly n times. The inner loop advances left, and left never decreases, so across the entire run the inner loop body executes at most n times in total no matter how it is distributed across iterations. Total pointer movement is bounded by 2n, each step does constant work on a hash map, so the algorithm is O(n) with O(k) space for the counts. Notice that this is an amortised argument, not a per-iteration one: any single outer iteration can run the inner loop many times. Candidates who assert "sliding window is linear" without this argument tend to fall apart when the interviewer asks about the worst case for one iteration. The same amortised reasoning covers every variant of the pattern, including the fixed-size window, where the repair is a single unconditional shrink instead of a loop. The full derivation lives in the sliding window concept page, and minimum-window-substring is the hardest common instance of it.

Why do candidates who know the patterns still fail?

Because they learned the code and not the invariant, which shows up in three specific ways.

The first is pattern forcing. A problem mentions a contiguous subarray, the candidate reaches for a sliding window, and the window quietly produces wrong answers because the validity condition is not monotone. Windows only work when extending the window can never fix a violation and shrinking can never cause one. With negative numbers in a sum-at-least-k problem, that fails immediately, and the correct pattern is prefix sums with a hash map instead. If you cannot state your invariant, you cannot notice that the problem violates it.

The second is the wrong repair. In converging two pointers, the choice of which pointer to move is the whole algorithm. In a sorted-array pair sum, moving the left pointer when the sum is too small is justified by an argument: the current pair is the largest sum available to that left index, so no partner remains for it. In container with most water the justification is different, since you move the shorter wall because keeping it can never yield a taller container across a narrower span. Same skeleton, different proof. Candidates who memorised one and applied the other lose correctness on a problem they thought they knew.

The third is asserted complexity. Saying "this is O(n log n)" without the counting argument is a coin flip that interviewers notice. The habit that fixes it is to name what you are counting and what each count costs. Here is the answer-space search, whose complexity is genuinely two factors multiplied:

def min_feasible(lo, hi, feasible):
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):        # invariant: answer lies in [lo, hi]
            hi = mid
        else:
            lo = mid + 1
    return lo

This is the shape behind "minimum capacity to ship packages in D days" and its many relatives, and its cost has to be stated as a product. The loop halves the interval each iteration, so it runs about log₂(hi minus lo) times, which is the number of times you can halve the numeric range before it collapses to a point. That count has nothing to do with the input array's length. The second factor is the cost of one feasible call, which almost always scans the input once at O(n). Multiply them and the total is O(n log range), and both halves of that product need saying out loud because a candidate who reports only O(log n) has hidden the expensive part. The pattern is also easy to break at the boundary: hi = mid rather than mid - 1 is required here because mid may itself be the answer, and pairing that with lo = mid + 1 is what guarantees the interval strictly shrinks and the loop terminates. Get one of those two lines wrong and you get an infinite loop rather than a wrong answer, which is why this template is worth memorising exactly as written. The monotonicity requirement, that feasible is false then true with no alternation, is covered in binary search on the answer.

How should you practise the pattern catalogue?

Classify before you solve. Read a problem, write one sentence naming the pattern, the cue that told you, and the invariant you expect to maintain, then solve it. Compare your sentence to what the solution actually did. The gap between your guess and the real answer is the only part of the session that teaches anything, and it disappears if you read the solution first.

Do the catalogue in vertical slices, not horizontal ones. Five problems on one pattern in a single sitting builds recognition much faster than one problem each on five patterns, because the second problem in a slice is where you notice which parts of the first were essential and which were incidental. Two sittings per pattern, spaced about a week apart, is enough for the first tier.

Keep a one-line-per-problem log in the format "this was a [pattern] problem, spotted by [cue], invariant [statement], solved in O([bound]) because [counting argument]". Twenty entries in and the fifteen rows above stop being a table you consult and start being the way you read a problem statement.

Concretely, start tomorrow with the Two Pointers and Sliding Window module, which covers three of the top five patterns in one pass, then work longest-substring-without-repeating and write the invariant sentence before you write any code.

Frequently asked questions

How many coding interview patterns do I actually need?

Fifteen is the working number for screening rounds, and the first five carry most of the weight. Adding patterns past that point has sharply diminishing returns compared with getting faster and more accurate at recognising the ones you already know. Depth beats breadth here because failures in interviews are far more often misapplication than ignorance.

Is memorising patterns the same as memorising solutions?

No, and the difference is whether you can state the invariant. Memorising a solution means you can reproduce code for a problem you have seen. Knowing a pattern means you can derive code for a problem you have not seen, because you know what property the loop must protect and what to do when it breaks. The test is simple: if an interviewer changes one constraint and your solution collapses, you memorised.

What should I do when a problem matches no pattern?

Solve it brute force first, out loud, and state its complexity honestly. A correct exponential solution with a clear complexity argument scores better than a stalled search for elegance, and the brute force usually exposes the repeated work that points at the right pattern. Overlapping subproblems in your brute force means dynamic programming; wasted rescanning means a window or a prefix structure.