Which Technique When?

Most interview problems are variations on a few dozen techniques. The hard part is recognising which one applies. This guide is a lookup table: find the signal in the problem statement or constraints, and it tells you what to try first and the one key move that makes it work. It is not a full course on each pattern; for that, work through the NeetCode roadmap.

Start with the constraints#

Input size usually tells you the target complexity before you've read the rest of the problem. These are rough rules of thumb for a typical time limit.

Arrays and strings#

Most array and string problems fall into prefix sums, sliding windows, two pointers or hashing.

Stacks and binary search#

Stacks handle nesting and "next greater" questions; binary search handles anything sorted or monotonic.

Intervals#

Interval problems almost always start with a sort. What you sort by depends on the question.

Before coding, clarify whether the boundaries are inclusive: do [1, 2] and [2, 3] overlap?

Linked lists#

Linked-list problems are mostly about pointer bookkeeping, and a few standard tricks remove the edge cases.

Trees#

Most tree problems are a DFS or a BFS. The signal tells you which, and what each call should return.

Edge cases to check every time: empty tree, missing left or right child, single leaf.

Tries and heaps#

Tries answer prefix questions; heaps answer "top k" and "smallest next" questions.

Complexity cues for heaps: sort everything is $O(n \log n)$; scan $n$ items with a size-k heap is $O(n \log k)$; heapify then pop $k$ times is $O(n + k \log n)$.

Graphs#

Default to an adjacency list; use a matrix only when the graph is dense or the input already is a grid. For undirected graphs add both u → v and v → u.

Very wide graphs make BFS queues large; very deep graphs risk recursion limits in DFS. Use an explicit stack in Python when depth can reach thousands.

Backtracking and DP#

Both explore choices. Backtracking lists every outcome, while DP reuses overlapping subproblems.

A reusable top-down DP shape:

from functools import lru_cache

def min_coins(coins, amount):
    @lru_cache(maxsize=None)
    def solve(remaining):        # state: what's left to make
        if remaining == 0:       # base case: goal reached
            return 0
        if remaining < 0:        # invalid: dead end
            return float("inf")
        # start at inf for min, -inf for max, 0 for counts
        best = float("inf")
        for c in coins:          # explore every choice
            best = min(best, 1 + solve(remaining - c))
        return best

    ans = solve(amount)
    return -1 if ans == float("inf") else ans

print(min_coins((1, 2, 5), 11))   # 3

Checklist before writing DP:

1. What is the state? (index, remaining amount, last choice, ...)
2. What does a call return? (count, min cost, max profit, boolean)
3. Does the answer depend only on the state? If not, add what's missing to the state.
4. How do sub-results combine? min(cost + sub), max(val + sub), or sum(sub) for counting.

Estimating complexity quickly#

Use these rules of thumb to state your complexity with confidence.

• Memoised DP: (number of states) × (work per state). Two parameters with ranges x and y and constant choices: $O(xy)$. Looping over k choices per state: $O(xyk)$.
• Backtracking: about (branching factor)^(depth), times the cost of copying each result.
• String building: each s + t is $O(n)$; sorting n strings of length L is $O(n L \log n)$.
• Hashing tuples: a tuple key costs $O(\text{its length})$ to hash, so keep keys small.

Key takeaways#

• Read the constraints first: they usually reveal the target complexity.
• Contiguous + monotonic condition → sliding window; contiguous + negatives or exact counts → prefix sums with a hash map.
• Next greater/smaller → monotonic stack; "min X such that" → binary search on the answer.
• Top k → size-k heap or quickselect; shortest path in an unweighted graph → BFS.
• For DP, name the state, the return value and the combine step before you write code.