Big Tech DSA Patterns

1 · Sliding window very common

Picture the moment the interview goes sideways. You're asked for the longest stretch of a string with no repeated letter. You write the honest answer: for every start position, try every end position, check the slice. It's correct, you're relieved — and then the interviewer says "now make it faster." You freeze, because you're staring at two nested loops and don't see the exit. That frozen feeling is the exact problem this pattern was invented to dissolve. The nested loops were re-examining the same characters over and over; the sliding window refuses to.

When to reach for it: the instant a problem talks about a contiguous run — a subarray or substring, never a scattered subset — and asks for the best one under some rule. That word "contiguous" is the tell in disguise; scattered picks are backtracking or DP, but an unbroken run means a window. The everyday analogy is looking through a train window at the countryside: you don't teleport around, you see a continuous band of scenery that shifts as the train moves. Your window is that band over the array — it has a left edge and a right edge, and it only ever slides forward.

The one idea that makes it O(n): instead of rebuilding each window from scratch, you reuse the previous one. Push the right edge forward to let a new element in; when that breaks your rule (a duplicate appears, the sum grows too big), drag the left edge forward to kick elements out until the rule holds again. Crucially, each element is admitted exactly once and evicted at most once — so even though there are two moving pointers, the total travel is bounded by 2n, which is just O(n). The two loops you feared collapse into a single sweep.

The common mistake is treating the inner shrink as a second nested loop and panicking that it's still O(n²). It isn't: left never moves backward and can't overtake right, so across the whole run it advances a total of n steps no matter how the shrinks clump together. The second trap is a variable-size window that never shrinks — if your while condition is wrong, the window only grows and you silently get the whole array as your answer. Watch for two flavors: a fixed window (width k is constant, so you slide in lockstep — add one, drop one) and a variable window (width flexes to satisfy a constraint). Naming which flavor you're in before you type is half the battle. Tell: "longest / shortest / max / min contiguous subarray or substring satisfying …". Grow a window on the right, shrink from the left when a constraint breaks — O(n) instead of O(n²).

pythondef length_of_longest_substring(s):
    seen = {}                       # char -> last index seen
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1    # jump left past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)
    return best                    # O(n) time, O(min(n, alphabet)) space

print(length_of_longest_substring("abcabcbb"))   # 3

pythonfrom collections import Counter

# (a) Max sum of a FIXED window of size k (classic problem style) — O(n)
def max_sum_k(nums, k):
    window = sum(nums[:k]); best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i-k]        # slide: add new, drop old
        best = max(best, window)
    return best

# (b) Minimum window substring (classic) — variable window + counts
def min_window(s, t):
    need = Counter(t); missing = len(t)
    lo = start = 0; end = 0
    for hi, ch in enumerate(s, 1):        # hi is 1-based right edge
        if need[ch] > 0: missing -= 1
        need[ch] -= 1
        if missing == 0:                    # window covers all of t
            while need[s[lo]] < 0:           # shrink past surplus chars
                need[s[lo]] += 1; lo += 1
            if end == 0 or hi - lo < end - start:
                start, end = lo, hi           # record best window
    return s[start:end]

print(max_sum_k([2,1,5,1,3,2], 3), min_window("ADOBECODEBANC", "ABC"))  # 9 BANC

2 · Two pointers & fast/slow very common

Here's a habit worth breaking early. Given a sorted array and asked to find two numbers that add to a target, most people's reflex is a nested loop: pick each number, then scan the rest for its partner. It works, it's O(n²), and it throws away the single most valuable fact you were handed — that the array is sorted. Sorted order is a gift, and the two-pointer pattern is how you unwrap it. Once you internalize this, a whole family of "find the pair/triplet" problems stops being a search and becomes a steering problem.

The converging-pointers analogy: imagine tuning an old radio dial with two hands. One hand sits at the smallest value, one at the largest, and you're hunting for a target frequency. If the current sum is too high, you can only bring it down by moving the top hand inward toward smaller numbers; too low, you move the bottom hand inward toward bigger ones. Every move is informed — the sortedness tells you unambiguously which pointer to nudge — so you never waste a comparison. The two hands march toward each other and the whole scan is one linear pass, O(n), after the sort.

The second, very different cousin lives on linked lists: fast and slow pointers. Here the two pointers don't converge from the ends — they start together and move at different speeds, one hopping one node at a time, the other two. Picture two runners on a circular track: if the track loops, the faster runner inevitably laps and collides with the slower one; if the track is a straight dead-end, the fast runner simply reaches the finish first. That single idea detects a cycle (they meet), finds the exact middle (when fast hits the end, slow is halfway), and locates the nth-from-last node — all in O(1) extra space, no hash set of visited nodes required.

The mistake that costs interviews is reaching for two pointers on an unsorted array for a pair-sum problem — the technique is only valid because moving a pointer monotonically changes the sum, which requires order. If the array isn't sorted and you can't afford to sort it, a hash map is your tool instead. The other classic slip is duplicate handling: once you find a valid pair or triplet, you must skip over equal neighbours or you'll emit the same answer several times (you'll see that guard in the 3Sum code below). Tell: "sorted array, find a pair/triplet" → converging pointers; "find the cycle / middle / nth-from-end of a linked list" → fast & slow pointers.

pythondef three_sum(nums):
    nums.sort()                          # O(n log n)
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue                     # skip duplicate anchors
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0: lo += 1
            elif s > 0: hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1; hi -= 1
                while lo < hi and nums[lo] == nums[lo-1]: lo += 1  # skip dups
    return res                       # O(n²) total, O(1) extra

python# (a) Container with most water (classic) — greedy two-pointer, O(n)
def max_area(height):
    lo, hi, best = 0, len(height) - 1, 0
    while lo < hi:
        best = max(best, (hi - lo) * min(height[lo], height[hi]))
        if height[lo] < height[hi]:      # move the SHORTER wall inward
            lo += 1
        else:
            hi -= 1
    return best

# (b) Reverse a linked list (classic) — the pointer-flip classic, O(n)
def reverse_list(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next   # flip & advance
    return prev

# (c) Middle of a linked list (classic) — fast/slow, O(n)
def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next    # slow ends at the middle
    return slow

print(max_area([1,8,6,2,5,4,8,3,7]))    # 49

3 · Top-K with a heap very common

A story from a real system, because this pattern hides inside the code this course builds. Your RAG retriever scores a query against a million document chunks and needs the best 5. The naive move is to sort all million scores and slice off the top 5 — and it works, but you just paid O(n log n) to rank 999,995 chunks you're going to throw away. That waste is the itch the Top-K pattern scratches. You don't need the whole ordering; you need a tiny leaderboard that only remembers the current champions and cheaply forgets everyone else.

When to reach for it: any question phrased as "the K largest / smallest / most frequent / closest," especially when k is much smaller than n or the data arrives as a stream you can't fully hold. That "K best out of many" shape is the tell. The everyday analogy is a talent show with only three trophies: you don't rank every contestant end-to-end, you just keep three trophies on the table, and each new act only matters if it beats your current weakest trophy-holder — who then goes home.

The counter-intuitive twist that trips everyone: to keep the K largest items, you use a min-heap, not a max-heap. It feels backwards until you see why — the heap's root is always its smallest element, and the smallest of your current winners is precisely the one on the bubble, the first to be evicted the moment something bigger shows up. So the min-heap puts your most-vulnerable champion right where you can check and drop it in O(1). Each of the n items costs an O(log k) push (and maybe a pop), giving O(n log k) overall — and because you only ever hold k items, it's memory-friendly and streaming-friendly in a way that a full sort never is.

The common mistake is grabbing a max-heap "because we want the biggest," which forces you to push all n items and pop k — that's O(n + k log n) and, worse, holds the entire dataset in memory. For a bounded stream the size-k min-heap is the disciplined choice. In Python this is the heapq module, and here's its own quirk to remember: it isn't a Heap class, it's a set of functions (heappush, heappop, nlargest) that operate on a plain list you maintain, with the minimum always sitting at index 0. Tell: "K largest / smallest / most frequent / closest …". Keep a size-K heap: O(n log k), far better than sorting everything when k ≪ n.

pythonimport heapq
from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)                       # O(n)
    # heap of (freq, value); nlargest keeps only k
    return [v for v, _ in heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])]

print(top_k_frequent([1,1,1,2,2,3], 2))   # [1, 2]

pythonimport heapq

# (a) K closest points to origin (classic) — O(n log k)
def k_closest(points, k):
    return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)

# (b) Merge k sorted lists (classic) — heap of (val, list_idx, node), O(N log k)
def merge_k(lists):
    heap = [(vals[0], i, 0) for i, vals in enumerate(lists) if vals]
    heapq.heapify(heap)
    out = []
    while heap:
        val, i, j = heapq.heappop(heap)      # smallest across all lists
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j+1], i, j+1))
    return out

# (c) Find median from a data stream (classic) — TWO heaps
class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (store negatives) — smaller half
        self.hi = []   # min-heap — larger half
    def add(self, num):
        heapq.heappush(self.lo, -heapq.heappushpop(self.hi, num))
        if len(self.lo) > len(self.hi):
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
    def median(self):
        if len(self.hi) > len(self.lo): return float(self.hi[0])
        return (self.hi[0] - self.lo[0]) / 2

print(k_closest([[1,3],[-2,2],[5,8]], 2))    # [[-2,2],[1,3]]

4 · Binary search on the answer common

This is the pattern that makes people feel like they've been let in on a secret. You learned binary search as "find a value in a sorted array" — halve the range, keep the half that could contain your target. Fine. But then a problem shows up that has no array to search: "what's the slowest speed Koko can eat bananas and still finish in time?" There's no sorted list of speeds handed to you. The reflex is to try every speed from 1 upward, which is a linear grind. The leap — and it genuinely feels like a magic trick the first time — is realizing you can binary-search the space of possible answers itself.

When to reach for it: the tell is a phrase like "minimum value such that…" or "maximum value such that…" attached to something you can test. If you can look at a candidate answer x and cheaply decide yes-this-works or no-too-small, and the yes/no verdict flips exactly once as x increases, you're in business. That "flips exactly once" property has a name — monotonic — and it's the whole ballgame. The analogy is a dimmer switch wired to a light sensor: turn the knob up and at some precise point the room crosses from "too dark" to "bright enough," and it never flickers back. You're not scanning brightness levels one by one; you're bisecting the knob to pounce on that threshold.

How to actually build it: write a helper feasible(x) that returns True/False, decide the low and high bounds of the answer range, and binary-search for the boundary where feasibility switches on. Each guess halves the candidate range, so if the answers span a range R and one feasibility check costs C, the total is O(log R · C) — logarithmic in the size of the answer space, not linear. A problem that looked like brute force over thousands of speeds becomes a dozen probes.

The mistake that quietly breaks it: applying this when feasibility isn't monotonic. If a candidate can be "good, then bad, then good again" as x grows, bisection is meaningless — you'll happily discard the half that held the answer. Always convince yourself of the monotonic property first ("if speed x finishes in time, any faster speed obviously does too"). The other perennial bug is the loop's boundary logic: off-by-one errors in whether you keep mid or move past it are what turn a correct idea into an infinite loop. Nail down "am I searching for the leftmost True or the rightmost?" before you write the lo/hi updates. Tell: "minimum/maximum value such that a condition holds", or a sorted/rotated array. If you can write a monotonic feasible(x) check, binary-search the answer space in O(log range · check).

pythonimport math

def min_eating_speed(piles, h):
    def hours_at(speed):
        return sum(math.ceil(p / speed) for p in piles)
    lo, hi = 1, max(piles)              # answer lives in [1, maxpile]
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_at(mid) <= h:         # feasible -> try slower
            hi = mid
        else:
            lo = mid + 1              # too slow -> go faster
    return lo                        # smallest feasible speed

5 · Merge intervals common

Everyone has fought this in a calendar app. You've got a pile of meetings — some back-to-back, some overlapping, some with gaps — and you want to know your true "busy blocks" for the day. Do it by eye and you'll try to compare every meeting against every other meeting, an O(n²) tangle that gets worse as the day fills up. The merge-intervals pattern is the clean way out, and its power comes almost entirely from one preparatory move that feels too simple to matter: sort the intervals by their start time first.

Why that sort changes everything: once the ranges are lined up by start, any two intervals that overlap are guaranteed to be adjacent in the list. That means you never have to look backward or compare distant pairs — you just walk the sorted line once, holding the interval you're currently building, and check each newcomer against only that one. The analogy is packing a moving truck by loading boxes in the order they arrive at the door: because they're pre-ordered, you only ever decide whether the next box stacks onto the current pile or starts a new one. Sort plus one sweep is O(n log n), dominated by the sort.

When to reach for it: the tell is anything built from start/end pairs — "merge overlapping ranges," "can this person attend all meetings," "insert a new interval and re-merge," "how many rooms do we need." The moment you see ranges on a timeline, your first instinct should be "sort by start, then sweep." The merge rule itself is tiny: two intervals overlap when the next one's start is at or before the current one's end, and you merge them by stretching the end to the larger of the two ends.

The mistakes to guard against are subtle but common. First, sorting by the wrong key — sort by start, not end, or the adjacency guarantee evaporates and you'll miss merges. Second, the boundary case of touching intervals like [1,3] and [3,5]: decide up front whether a shared endpoint counts as overlapping (usually yes, so use <= not <) and be consistent. Third, mutating the input list in place and then comparing against your own half-built output — copy the first interval before you start extending it, as the code below does with a deliberate slice. Tell: anything with start/end ranges — "merge overlapping", "can attend all meetings", "insert interval". Sort by start, then sweep.

pythondef merge(intervals):
    intervals.sort(key=lambda iv: iv[0])     # by start
    out = [intervals[0][:]]
    for start, end in intervals[1:]:
        if start <= out[-1][1]:            # overlaps previous
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

print(merge([[1,3],[2,6],[8,10]]))   # [[1,6],[8,10]]

6 · BFS/DFS on a grid (islands) common

The unlock here is a change of eyes, not a change of algorithm. A 2-D grid of cells looks like a table, so people attack grid problems with clever double-loop bookkeeping and quickly drown in edge cases. The realization that makes these problems easy is that a grid is just a graph wearing a disguise: every cell is a node, and each cell has an edge to its up/down/left/right neighbours. The instant you see it that way, "count the islands" stops being a puzzle about maps and becomes the textbook graph problem "count the connected components" — which you already know how to solve with the search you learned in D5.

When to reach for it: the tell is a 2-D grid plus a verb like "count regions," "flood fill," "how many groups," or "shortest path through a maze." If cells clump into connected blobs and you care about the blobs, that's connected components (use DFS or BFS to flood each one). If instead you care about the fewest steps from A to B, that's shortest path on an unweighted graph — and that specific need is what forces the choice between the two searches.

DFS vs BFS — the choice actually matters, and here's the intuition. DFS is a single explorer who charges as far down one corridor as possible before backtracking; it's perfect for "just flood this whole region and mark it seen," and it's a two-line recursion. BFS is a ripple spreading outward in rings from a starting point, one full ring per step — a dropped stone in a pond. Because BFS reaches everything at distance 1 before anything at distance 2, the first time it touches the goal it has found the shortest path. So the rule of thumb is: counting or filling → DFS is simplest; shortest path or "how many minutes until everything is infected" → BFS. Either way every cell is visited once, so the cost is O(rows·cols).

The mistakes are almost always mechanical, not conceptual. The big three: forgetting to mark cells visited (so the search revisits and either loops forever or double-counts — the fix is to flip the cell or keep a seen-set); letting neighbour coordinates run off the edge of the grid (every neighbour check needs a bounds guard); and reaching for DFS recursion on a huge grid, where Python's recursion limit can blow the stack — a large flood fill is safer done iteratively with an explicit stack or a BFS queue. Also resist counting diagonals as connected unless the problem says so; "island" problems are almost always 4-directional. Tell: a 2-D grid where you "count regions / flood fill / shortest path in a maze". Treat each cell as a graph node with up/down/left/right edges.

pythondef num_islands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "1":
            grid[r][c] = "0"                # mark visited
            sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1; sink(r, c)      # one new island, flood it
    return count

pythonfrom collections import deque

# (a) Rotting oranges (classic) — BFS from ALL rotten cells at once
def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    q = deque(); fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2: q.append((r, c, 0))   # seed all sources
            elif grid[r][c] == 1: fresh += 1
    minutes = 0
    while q:
        r, c, t = q.popleft(); minutes = max(minutes, t)
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2; fresh -= 1; q.append((nr, nc, t+1))
    return minutes if fresh == 0 else -1

# (b) Course schedule (classic) — cycle detect via topological sort (Kahn)
def can_finish(n, prereqs):
    adj = {i: [] for i in range(n)}; indeg = [0] * n
    for a, b in prereqs:
        adj[b].append(a); indeg[a] += 1
    q = deque([i for i in range(n) if indeg[i] == 0])
    done = 0
    while q:
        node = q.popleft(); done += 1
        for nxt in adj[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0: q.append(nxt)
    return done == n              # all scheduled → no cycle

print(can_finish(2, [[1,0]]), can_finish(2, [[1,0],[0,1]]))   # True False

7 · Trees: DFS, BFS & LCA common

Tree problems feel scary until you notice they nearly all rhyme. Candidates freeze because a tree looks like it demands custom cleverness for every question — depth, diameter, path sums, validation, common ancestors — but underneath, the overwhelming majority are the same move: recurse to the children, then combine what they report back. The trick isn't inventing a new traversal each time; it's deciding what one piece of information each node should return to its parent. Get that contract right and the recursion writes itself.

The mental model — think like a manager delegating. A node doesn't compute its answer alone; it asks its left subtree and its right subtree to each report a summary ("how deep are you?", "did you contain the node I'm looking for?"), then merges those two reports into its own and passes it upward. This is "bubbling up": information flows from the leaves back toward the root. Depth is 1 + max(left, right). Diameter is the best path that bends through a node, left_depth + right_depth. "Does this subtree contain both targets?" is a boolean report — and the first node that hears "yes" from both sides is the lowest common ancestor. Same shape, different summary.

When to reach for BFS instead: the one big fork is whether the problem cares about levels. "Print the tree level by level," "find the rightmost node on each row," "what's the minimum depth" — anything that groups nodes by their distance from the root wants breadth-first traversal with a queue, processing one full row before the next. Everything else — paths, depths, sums, validation, ancestors — is depth-first recursion returning info up. That single question, "do I need level order or not?", picks your traversal before you write a line.

The mistakes worth pre-empting: forgetting the base case (a None child must return a sensible neutral value like depth 0 or "not found," or the recursion crashes on the leaves); and conflating "the deepest path through a node" with "the deepest path starting at a node" — diameter needs both children's depths added, but the value you return to your parent is only the longer single branch, because a parent can't walk down both your sides at once. That subtle "return one thing, but track another for the global answer" split is exactly what LCA and diameter both hinge on. Tell: "level order" → BFS; "path / depth / diameter / validate" → DFS recursion returning info up; "lowest common ancestor" → recurse and bubble up where the two targets are found.

pythondef lowest_common_ancestor(root, p, q):
    if root is None or root is p or root is q:
        return root                     # found a target (or hit the bottom)
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root                     # p & q split here -> this is the LCA
    return left or right              # both on one side -> pass it up   O(n)

8 · Backtracking (subsets, permutations, combinations) common

Think about how you actually solve a maze on paper. You walk down a corridor, hit a dead end, and — this is the key part — you don't start over from the entrance. You rub out your last few steps and try the other fork. That erase-and-retry instinct is the entire soul of backtracking. It's how you explore an enormous space of possibilities without getting lost: make a choice, follow it as far as it goes, and if it doesn't pan out, undo exactly that one choice and try the next. Every "generate all combinations" problem is a maze, and this is the map-drawing technique.

When to reach for it: the tell is the word "all" — "generate all subsets," "find all valid arrangements," "list every way to…". You're not optimizing to a single number (that's often DP or greedy); you're enumerating a combinatorial space, usually with constraints that let you abandon dead branches early (N-queens, Sudoku, word search, generate-parentheses). If the answer is a collection of configurations rather than one value, backtracking is almost always the frame.

The skeleton is three lines you will reuse forever: choose → recurse → un-choose. Add an element to your running path (choose), recurse to build on top of it (explore everything that choice leads to), then remove it (un-choose) so the next iteration starts from a clean slate. That final undo is what lets a single shared path list explore an exponential tree — you're reusing one piece of scratch paper for millions of branches by carefully erasing between them. The shape of the space is a decision tree with up to O(2ⁿ) or O(n!) leaves, and that's inherent: you're producing exponentially many answers, so the work is exponential no matter how clean the code.

The two mistakes that bite hardest. First, forgetting the un-choose (the path.pop()): the shared list never rewinds, so each branch pollutes the next and your output turns to nonsense — comment it out once and watch it break, because seeing that failure cements the lesson. Second, appending the path itself to your results instead of a copy of it: since you keep mutating that same list, every stored "answer" ends up pointing at the same object, which is empty by the end — always snapshot with path[:]. The optimization layer on top, pruning, is where backtracking earns its keep: abandon a branch the instant it can't possibly lead to a valid answer, and an intractable search becomes fast. Tell: "generate all / find all valid …", combinatorial explosion, constraints (N-queens, Sudoku, word-search). Choose → recurse → un-choose.

pythondef subsets(nums):
    res, path = [], []
    def backtrack(start):
        res.append(path[:])                 # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])            # choose
            backtrack(i + 1)               # explore (no reuse)
            path.pop()                      # un-choose
    backtrack(0)
    return res                          # 2ⁿ subsets

print(subsets([1, 2, 3]))            # [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]

9 · Dynamic programming the hard round expert

This is the round people fear, and the fear is mostly a trick of the light. DP has a reputation as arcane wizardry, but almost every DP problem starts life as a simple, obvious recursion that happens to be catastrophically slow because it re-solves the same subproblem thousands of times. The canonical eye-opener is naive Fibonacci: fib(50) recomputes fib(10) millions of times over. Dynamic programming is nothing more than the fix your common sense already suggests — write the answer down the first time you compute it, and look it up ever after. That's it. The mystique is just the name.

The everyday analogy: filling in a crossword or a spreadsheet. Each cell's value depends on a few earlier cells, so you can't compute the whole thing at once — but you can fill the easy cells first (the base cases), then work outward, each new cell built from ones already solved. That's a DP table. A cell answers one subproblem ("the best value using the first i items with capacity w"), and every cell is computed exactly once and reused forever after. Exponential recursion collapses into a polynomial-sized grid you fill in order.

When to reach for it: two tells stacked on top of each other. The phrasing is "count the number of ways," "minimum/maximum cost or steps," or "can you reach / partition / make change" — you're optimizing or counting over a sequence of choices. And structurally, the problem has overlapping subproblems (the same smaller question recurs) plus optimal substructure (the best overall answer is built from best answers to those smaller questions). If choices are independent and you never revisit a subproblem, it's plain recursion or greedy; the repetition is what invites DP. Your job is to name three things: the state (what defines a subproblem), the recurrence (how a state's answer combines smaller states' answers), and the base case.

Two ways to implement, one common trap. Top-down memoization keeps your natural recursion and just caches results (add @lru_cache or a dict) — easiest to write, closest to how you reasoned. Bottom-up tabulation fills an array from the base cases outward — no recursion limit, often faster, sometimes more memory. Both give the same complexity; pick whichever you can code cleanly under pressure. The mistake that sinks candidates isn't the code, it's defining the state wrong — choosing state variables that don't fully capture a subproblem, so different situations collide in the same cell and the answer is silently corrupt. Spend your first minutes pinning down "what exactly does dp[i][w] mean?" before writing the recurrence; a precise state definition is 80% of the solution. Tell: "count the ways", "min/max cost/steps", "can you reach/partition", overlapping subproblems. Define a state, a recurrence, and a base case — then either memoize (top-down) or fill a table (bottom-up).

python# Fewest coins to make `amount` — bottom-up DP, O(amount · coins)
def coin_change(coins, amount):
    dp = [0] + [float("inf")] * amount     # dp[x] = min coins for x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

# Longest common subsequence — the classic 2-D table, O(m·n)
def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1       # match -> extend diagonal
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(coin_change([1,2,5], 11), lcs("abcde", "ace"))   # 3  3

python# (a) Climbing stairs (classic) — Fibonacci in disguise, O(n) / O(1) space
def climb(n):
    a, b = 1, 1
    for _ in range(n): a, b = b, a + b     # ways(i) = ways(i-1) + ways(i-2)
    return a

# (b) House robber (classic) — take-or-skip, O(n) / O(1) space
def rob(nums):
    take = skip = 0
    for x in nums:
        take, skip = skip + x, max(skip, take)   # rob this? then couldn't rob prev
    return max(take, skip)

# (c) Longest increasing subsequence (classic) — O(n log n) with bisect
import bisect
def lis(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)     # first tail >= x
        if i == len(tails): tails.append(x)
        else: tails[i] = x                      # keep tails as small as possible
    return len(tails)

# (d) Word break (classic) — dp[i] = can we segment s[:i]?  O(n²)
def word_break(s, words):
    wordset = set(words); dp = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordset:
                dp[i] = True; break
    return dp[len(s)]

print(climb(5), rob([2,7,9,3,1]), lis([10,9,2,5,3,7,101,18]))  # 8 12 4

10 · Two more high-frequency tools common

These last two feel like cheats the first time they click. Both take a problem that screams "nested loop, O(n²)" and quietly flatten it to a single O(n) pass — and both are so common that seasoned interviewers use them as litmus tests for whether you've drilled patterns or are still solving from scratch. What unites them is a shared instinct: keep a little bit of history around so you never have to look backward twice.

The monotonic stack answers "for each element, what's the next bigger (or smaller) one to its right?" — daily temperatures, next-greater-element, largest-rectangle-in-histogram, trapping rain water. The tell is "next greater/smaller" or "how far until something taller." The idea: you keep a stack of elements that are still waiting for their answer, deliberately kept in sorted order (say, decreasing). When a new element arrives that breaks the order, it is the answer for everything it's bigger than, so you pop those off and resolve them. Picture people queued on a hill looking rightward for someone taller — the moment a giant walks up, everyone shorter who was waiting gets their answer at once and steps aside. Each element is pushed and popped exactly once, so the whole thing is O(n) despite the inner while loop — the same amortized argument as the sliding window.

Prefix sum + hashmap answers "how many contiguous subarrays sum to exactly K?" — subarray-sum-equals-K, continuous-subarray-sum, count-nice-subarrays. The tell is "contiguous subarray with a target sum/count." The insight is that the sum of the slice between two positions equals the difference of their running totals (prefix sums), so "find a subarray summing to K" becomes "find two prefix sums that differ by K" — and finding a needed complement is exactly what a hash map does in O(1). It's the Two Sum trick applied to running totals. The mistake here is a classic: forgetting to seed the map with prefix 0 → count 1, which represents the empty prefix and is what lets a subarray starting at index 0 be counted; leave it out and you'll undercount every answer that begins at the front. Both tools appear constantly and are easy to name once seen:

• Monotonic stack — "next greater/smaller element", "daily temperatures", "largest rectangle in histogram", "trapping rain water". Keep a stack that stays sorted; pop while the new element breaks the order. O(n) (built on the stack from D2).
• Prefix sum + hashmap — "subarray sum equals K", "continuous subarray sum", "count nice subarrays". Store running prefix sums in a dict to find a needed complement in O(1) (combines D1 prefix sums + D3 hashing).

pythondef daily_temperatures(temps):
    res = [0] * len(temps)
    stack = []                          # indices, temps DECREASING down the stack
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:   # t is the "next warmer" for these
            j = stack.pop()
            res[j] = i - j              # days until warmer
        stack.append(i)
    return res                       # O(n): each index pushed/popped once

print(daily_temperatures([73,74,75,71,69,72,76,73]))   # [1,1,4,2,1,1,0,0]

pythonfrom collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                    # empty prefix
    running = count = 0
    for x in nums:
        running += x
        count += seen[running - k]   # a prefix that leaves exactly k? O(1)
        seen[running] += 1
    return count                    # O(n) time, O(n) space

print(subarray_sum([1, 1, 1], 2))     # 2

11 · Linked list manipulation very common

Linked lists are where confident coders suddenly get clumsy, and it's worth understanding why. With an array you can glance at any index and see the whole picture; with a linked list you're feeling your way along a chain in the dark, holding one node and a couple of pointers, and a single mis-ordered assignment either loses the rest of the list or ties it in a knot. Interviewers love this precisely because it tests whether you can manipulate pointers carefully and in the right order — a skill that array problems never exercise. The good news: almost every linked-list question is a remix of three small techniques.

The three tools, and the intuition behind each. A dummy head is a throwaway node you glue in front of the real list so that "insert/delete at the front" stops being a special case — the head becomes just another middle node, and a whole category of null-pointer bugs vanishes. Think of it as a placeholder chair at the head of a table so there's always a "seat before the first guest." Pointer-flip reversal walks the list turning each next arrow around to point backward; the ritual is "save the next node before you overwrite the arrow, or you'll strand the rest of the list." And fast/slow pointers (from §2) find the middle or detect a cycle in one pass with O(1) space.

When to reach for this pattern: the tell is blunt — the input is a linked list and you're asked to reverse it, merge two, reorder it, remove the nth-from-end, or find a node, ideally without allocating extra space. The O(1)-space constraint is often the whole point of the question; a naive solution that copies values into an array is correct but sidesteps exactly what's being tested. The dominant mistake, beyond null-pointer edge cases at head and tail, is overwriting a pointer before you've saved what it pointed to — the instant you do cur.next = prev without first stashing cur.next, the tail of your list is gone. Draw the three or four nodes on paper and move the arrows by hand before you type; that ten-second sketch prevents nearly every bug. This is such a big topic it has its own page — D8 · Linked list patterns — but here are the interview must-knows with diagrams. Tell: the input is a linked list and you must reverse, merge, reorder, or find a node with O(1) space. The toolkit: a dummy head to kill edge cases, pointer-flip reversal, and fast/slow pointers.

pythonclass ListNode:
    def __init__(self, val=0, nxt=None): self.val, self.next = val, nxt

# (a) Reverse a list (classic) — O(n), O(1)
def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

# (b) Merge two sorted lists (classic) — build behind a dummy tail
def merge_two(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val: tail.next, a = a, a.next
        else: tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

# (c) Remove nth node from end (classic) — offset two-pointer, one pass
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head); fast = slow = dummy
    for _ in range(n): fast = fast.next   # open an n-gap
    while fast.next: fast, slow = fast.next, slow.next
    slow.next = slow.next.next            # unlink the target
    return dummy.next

Pattern → tell cheat-sheet expert

Checkpoint — you're interview-ready when you can… expert

def max_window_sum(nums, k):           # O(n) time, O(1) space
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # add entering, drop leaving
        best = max(best, window)
    return best

print(max_window_sum([2, 1, 5, 1, 3, 2], 3))   # 9  (5+1+3)

def merge_intervals(intervals):        # O(n log n)
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:     # overlaps the last merged interval
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]

import heapq
from collections import Counter

def top_k_frequent(nums, k):           # O(n log k)
    counts = Counter(nums)
    return [val for val, _ in heapq.nlargest(k, counts.items(),
                                             key=lambda kv: kv[1])]

print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))   # [1, 2]

def ship_within_days(weights, D):
    def days_needed(cap):              # greedy fill under a fixed capacity
        days, load = 1, 0
        for w in weights:
            if load + w > cap:
                days += 1; load = 0
            load += w
        return days
    lo, hi = max(weights), sum(weights)   # feasible capacity range
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= D:
            hi = mid                   # feasible -> try smaller
        else:
            lo = mid + 1               # infeasible -> need bigger
    return lo

print(ship_within_days([1,2,3,4,5,6,7,8,9,10], 5))   # 15

def combination_sum(candidates, target):
    candidates.sort()
    result = []
    def backtrack(start, remaining, path):
        if remaining == 0:
            result.append(path[:]); return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                  # sorted -> no later candidate fits either
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i], path)  # i (reuse allowed)
            path.pop()
    backtrack(0, target, [])
    return result

print(combination_sum([2, 3, 6, 7], 7))   # [[2, 2, 3], [7]]

def coin_change(coins, amount):        # O(amount * len(coins))
    INF = amount + 1
    dp = [0] + [INF] * amount          # dp[x] = fewest coins to make x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 2, 5], 11))      # 3  (5 + 5 + 1)
print(coin_change([2], 3))             # -1

Knowledge check check yourself