Patterns

Most problems are variations on a small number of techniques. Learning to recognise the pattern is worth more than memorising any individual solution — and it is what turns an unfamiliar problem into a familiar one.

This page maps every technique in the guide to the problems that teach it.

The Words First

Every term used below, defined plainly. If a page ever uses a word you have not met, it should be here.

Ways of saying "part of the data"

These three are constantly confused, and mixing them up sends you to the wrong technique entirely.

Original:      [ 2,  7, 11, 15,  3 ]
                 0   1   2   3   4

Subarray       [ 7, 11, 15 ]      contiguous — no gaps allowed
Subsequence    [ 2, 11,  3 ]      keeps order, gaps ARE allowed
Subset         { 11, 2 }          order does not matter at all

Substring is just "subarray" when the data is text. The counts matter: subarrays are few enough to consider directly, subsequences are not — which is why "longest subsequence" problems need dynamic programming and "longest subarray" problems usually need a sliding window.

Words about how the code works

Reading O(...)

Big-O answers one question: when the input gets bigger, how much slower does this get? It ignores constants and small details on purpose, because those stop mattering as n grows.

O(n)        →         100,000 steps    instant
O(n log n)  →       1,700,000 steps    instant
O(n²)       →  10,000,000,000 steps    minutes — too slow

Space complexity is the same idea applied to memory. O(1) space means you used a fixed number of variables no matter how big the input was; O(n) means you built something that grows with it — a hash map, a copy, a recursion stack.

The Recognition Table

Start here. The wording of a problem usually points straight at the technique.

The Patterns

1. Hash Map / Set — trade memory for time

Turn an O(n) search into an O(1) lookup. The single highest-leverage move in this guide.

What it means. A hash map stores pairs — a key and a value — and finds any key in one step, no matter how many it holds. A set is the same thing without values: it only remembers "I have seen this". Python calls them dict and set; TypeScript calls them Map and Set.

Why it changes the cost. Searching a list for a value means checking items one by one — O(n). A hash map turns the key into an address by arithmetic, so it goes straight there — O(1).

The move. Whenever you catch yourself writing a second loop to search for something, ask: could I have recorded that on the way past? One loop that remembers usually replaces two loops that search.

FINDING TWO NUMBERS THAT ADD TO 9,  in [2, 7, 11, 15]

Brute force — check every pair                O(n²)
  2+7  2+11  2+15  7+11  7+15  11+15

Hash map — remember what you passed           O(n)
  see 2   → need 7   → not seen yet → remember 2
  see 7   → need 2   → SEEN IT      → answer

Two Sum · Contains Duplicate · Group Anagrams · Valid Anagram · Minimum Index Sum · Unique Email Addresses

2. Two Pointers — converging

Start at both ends and move inward under a rule that provably discards possibilities.

What it means. Two index variables, one at each end, walking towards each other. Each step you decide which one to move — and moving it throws away every combination that used its old position.

Why it is fast. Checking every pair is O(n²). Here each pointer only ever moves inward, so together they take at most n steps total. The whole thing is one pass.

Container With Most Water · Valid Palindrome · Trapping Rain Water

3. Two Pointers — same direction

Both pointers move forward, at different rates or under different conditions.

What it means. Usually a read pointer and a write pointer. Read visits every item; write only advances when an item is worth keeping. When they finish, everything before write is the answer.

Removing duplicates in place from [1, 1, 2, 3, 3]

read  →  visits all five
write →  advances only on a new value

  [1, 2, 3, 3, 3]
   ↑        ↑
   kept     leftover junk — ignored, never cleaned up
   (write = 3, so the answer is the first 3 items)

The invariant. Everything left of write is already correct. Hold that in mind and the loop writes itself. The trailing junk is intentional — the caller is told to read only the first write items.

Is Subsequence · Remove Duplicates II · Merge Sorted Array

4. Fast & Slow Pointers

One pointer moves twice as fast. Finds middles, detects cycles, locates offsets.

What it means. Both start at the head; slow takes one step per turn, fast takes two. Two facts fall out of that speed difference:

| When fast reaches the end | slow is at the middle — it travelled half as far | | If there is a loop | fast must eventually lap slow and land on it |

Why the cycle check works. Inside a loop, fast gains exactly one position on slow every turn. A gap that shrinks by one each time must reach zero — so they meet. If there is no loop, fast runs off the end instead. There is no third outcome, which is what makes this a proof rather than a heuristic.

Middle of the Linked List · Linked List Cycle II · Intersection of Two Lists

5. Sliding Window

A range that slides or grows across the data. The two kinds behave differently and are worth separating.

What it means. A window is a subarray marked by two indices, left and right. Instead of recomputing the answer for each new window from scratch, you update the previous answer — add what entered on the right, subtract what left on the left.

Why it is fast. Recomputing each window is O(n·k). Updating is O(1) per step, so the whole scan is O(n). The saving comes from reusing work, not from cleverer looping.

6. Prefix / Suffix Precomputation

One pass forward, one pass back, then combine. Turns range queries into O(1) arithmetic.

What it means. A prefix sum array stores, at each position, the total of everything up to that point. Once you have it, the sum of any range is one subtraction — no loop.

nums     =  [ 2,  4,  1,  7,  3 ]
prefix   =  [ 2,  6,  7, 14, 17 ]      running total

Sum of nums[2..3]  =  prefix[3] - prefix[1]
                   =     14     -    6      =  8
                                              (1 + 7 ✓)

The subtraction removes exactly the part you did not want. Build it once in O(n), then answer any number of range questions in O(1) each.

Why the second pass exists. Some problems need to know about both sides of a position — "what is to my left" and "what is to my right". One forward pass gives the first, one backward pass gives the second, then you combine them at each index. That is how Product of Array Except Self reaches O(n) without division, and how Trapping Rain Water knows the tallest wall on each side.

Running Sum · Find Pivot Index · Product of Array Except Self · Candy · Trapping Rain Water

7. Stack

Last-in-first-out. Nesting, undo, deferred operands, depth-first traversal.

What it means. A pile. You add to the top (push) and remove from the top (pop). The most recent thing in is the first thing out — LIFO. A queue is the opposite: first in, first out, like a checkout line.

When to reach for it. Whenever the thing you need next is the most recent unfinished thing. That phrasing covers more than it sounds like:

If a problem involves nesting, or something that must be resolved in reverse order of arrival, a stack is almost certainly the answer.

Valid Parentheses · Min Stack · Evaluate RPN · Simplify Path

Monotonic stack

A stack deliberately kept sorted, so anything breaking the order is popped. Answers "next greater" questions in one pass instead of O(n²).

What it means. Monotonic means the stack only ever holds values in one direction — say, decreasing from bottom to top. Before pushing a new value, you pop everything that would break that order. And here is the point: the thing being popped has just found its answer. The new value is the first bigger one to its right.

The counting version of "each item enters and leaves once" is what makes the cost linear even though a single step can pop many items.

Daily Temperatures · Trapping Rain Water

8. BFS / DFS

Queue for breadth, stack for depth. The choice determines both the visit order and the space cost.

What it means. Both explore everything reachable. BFS sweeps outward in rings — everything one step away, then everything two steps away. DFS commits to one direction and follows it to the end before trying another.

They are the same code. Take something out of the container, record it, put its neighbours in. Swap a queue for a stack and BFS becomes DFS. Nothing else changes.

Choosing. "Fewest steps", "shortest path", "minimum moves" → BFS, because it arrives in distance order, so the first arrival is the closest one. Anything about whole branches — does a path exist, is there a cycle, how deep is this — → DFS.

See it animated on trees and on graphs, where the same start node gets visited third by one and last by the other.

Level Order Traversal · N-ary Preorder · Number of Islands · Course Schedule · Maximum Depth · Jump Game II

9. Binary Search

Halve the search space. Works for exact matches, for boundaries, and even when there is no array.

What it means. Look at the middle. If it is not the answer, you learn which half the answer must be in — and throw the other half away without looking at it. Repeat.

Why it is so fast. Each step removes half of what is left. A million items is gone in 20 steps, because doubling the input adds just one step. That is what O(log n) looks like in practice.

versions:   1    2    3    4    5    6    7
bad?        no   no   no   YES  YES  YES  YES
                          ↑ find this boundary

Binary Search · Search Insert Position · First Bad Version

10. Greedy vs. Dynamic Programming

Greedy when the local choice is provably safe; DP when it is not.

Greedy takes the best-looking option right now and never reconsiders. Fast and simple — and wrong whenever a good choice today blocks a better one tomorrow.

Dynamic programming (DP) does the opposite: it considers every option, but never solves the same subproblem twice. It remembers each answer the first time and reuses it.

What DP actually is. Two conditions, and it applies whenever both hold:

Climbing stairs — how many ways to reach step 5?
Plain recursion recomputes the same values constantly:

              ways(5)
             /       \
        ways(4)      ways(3)
        /     \      /     \
   ways(3) ways(2) ways(2) ways(1)      ← ways(3) computed twice,
                                          ways(2) three times

Remember each result → each is computed once → O(2ⁿ) becomes O(n).

How to tell them apart. Ask: can taking the best option now make me worse off later? If yes, greedy is unsafe.

Jump Game · Gas Station · Candy · Integer to Roman · Climbing Stairs · House Robber · Coin Change · Longest Increasing Subsequence

11. Heap — keep the best k reachable

A heap answers one question fast: what is the smallest right now? That is enough for "top k" and "next to process".

What it means. A heap keeps the smallest item permanently at the front. Adding or removing costs O(log n); reading the smallest is free. It does not keep everything sorted — it cannot search, and it cannot give you the second smallest without removing the first.

Why that narrow ability is enough. For "the 5 largest of a million", sorting everything is O(n log n) and wasteful — you throw away 999,995 results. Instead keep a heap of size 5: each new item is compared against the smallest kept so far, and replaces it if bigger. Cost O(n log k), memory O(k).

The inversion that trips people up. To find the largest items you keep a min-heap, because the thing you need instant access to is the weakest survivor — the one to evict.

See heaps for the shape rules and the sift operations, animated.

Kth Largest · Merge k Sorted Lists · Top K Frequent

12. Backtracking — choose, explore, undo

For problems asking for all arrangements. Always exponential, so the constraints will be small.

What it means. Build an answer one decision at a time. When you run out of options — or the partial answer is already invalid — undo the last decision and try the next one. It is DFS over the space of possible answers rather than over a graph.

Subsets of [1, 2, 3] — at each item, take it or skip it

                    []
            take 1 /  \ skip 1
                 [1]    []
          take 2 / \      / \  skip 2
              [1,2] [1]  [2] []
               ...  ...  ... ...        →  2³ = 8 subsets

The three lines that matter. Choose → recurse → un-choose. That last step is the one beginners drop, and forgetting it means later branches inherit decisions from earlier ones, producing answers that were never actually built.

Why exponential is acceptable here. The problem asks for every arrangement, and there are 2ⁿ or n! of them — no algorithm can be faster than the size of its own output. That is also the tell: when you see n ≤ 20 in the constraints, the author is telling you exponential is expected.

Subsets · Permutations · Combination Sum

When the Table Does Not Help

The recognition table works when a problem is phrased in familiar words. Sooner or later one is not. This is the procedure for that case — and it is more valuable than any single pattern above, because it does not run out.

1. Solve it by hand first

Take a tiny example — four or five items — and find the answer on paper, without writing code.

Then ask the question that matters: what did I actually do? You did something. Write it down in plain words. That description is your algorithm, and it is almost always closer to correct than whatever you would have typed first.

If you cannot solve it by hand, you do not yet understand the problem. Stay here. Writing code will not help.

2. Write the brute force

Not as a formality — it earns three things:

Almost every technique on this page is the brute force with one specific waste removed. You cannot remove waste you have not seen.

3. Name the waste

Look at the brute force and find where it repeats itself. The kind of repetition points straight at the fix:

4. Check the constraints — they name the target

The problem's limits tell you which complexity is expected, which usually tells you the technique.

n ≤ 20             →  exponential is fine   →  backtracking, bitmask
n ≤ 3,000          →  O(n²) passes          →  2-D dynamic programming
n ≤ 200,000        →  needs O(n log n)      →  sorting, heap, binary search
n ≤ 10,000,000     →  needs O(n) or better  →  one pass, hash map, two pointers

Read these before designing, not after your solution times out.

Complexity Cheat Sheet