Start here. Ask these questions about every new problem:
When you see these words in a problem statement, reach for the corresponding pattern:
| You hear… | You think… | You need… |
|---|---|---|
| "find pair", "duplicate", "frequency", "group by" | O(1) lookup or counting | Hash Map |
| "sorted array", "palindrome", "subarray sum", "substring" | Converge or slide through data | Two Pointers |
| "level order", "shortest path", "flood fill", "components" | Explore neighbors layer by layer | BFS |
| "max depth", "validate tree", "all paths", "combinations" | Recurse, aggregate, or backtrack | DFS |
| "minimum / maximum", "number of ways", "can you reach", "optimal substructure" | Reuse answers to smaller subproblems (skip/jump to prior states) | Dynamic Programming |
| "sorted + pair from both ends" | Pointers move toward each other | Converging Pointers |
| "longest / shortest contiguous", "window", "shrink while invalid" | One pointer always advances; the other moves only when a condition fails | One-way Contingent |
| "take or skip", "previous house", "i−1 / i−2", "fibonacci-like" | Not scanning pointers — dependency offsets into a DP table | Skip Pointers (DP) |
| "search sorted", "lower / upper bound", "first True", "rotated sorted" | Halve the range with a computed midpoint | lo / mid / hi (Search) |
| "sort colors", "3-way partition", "0s then 1s then 2s" | Three live cursors: mid walks; lo/hi collect buckets | lo / mid / hi (Partition) |
Whenever you need to check existence, count occurrences, or group items without nested loops.
dict — complement lookup (Two Sum)set — existence check (Contains Duplicate)Counter — frequency counting (Valid Anagram)defaultdict(list) — grouping (Group Anagrams)in dict is O(1) average. This replaces the O(n) inner loop of the brute-force approach.
True. For frequency problems you continue counting.
seen[num] = i # build map as you go
Two Sum, Two Sum II
Valid Anagram, Top K
Group Anagrams
When the data is sorted or sequential and you need to find a pair, shrink/expand a range, or process a contiguous subarray.
Interviewers say “two pointers,” but several different mechanics hide under that phrase. Pick the right family before you code:
| Family | When you hear… | How they move | Not this if… |
|---|---|---|---|
| Converging | “sorted,” “pair that sums to,” “palindrome from both ends,” “max area between lines” | Start at both ends; each step moves at least one pointer inward until they meet. | You need a contiguous window whose size grows/shrinks (that’s one-way contingent). |
| One-way contingent | “longest substring,” “minimum window,” “shrink while invalid,” “same-direction scan” | Right (or the lead) always advances. Left advances only when a condition fails (contingent). | Both ends are active decision-makers that move toward each other (that’s converging). |
| lo / mid / hi (3 pointers) | “binary search,” “first True / lower bound,” “rotated sorted,” “sort colors / 3-way partition” | Three named indices. Search: mid = (lo+hi)//2, then shrink lo or hi. Partition: mid walks once; swap with lo/hi to bucket values. |
You only need a pair sum from both ends (converging) or a growing/shrinking window (one-way contingent). Also not DP skip offsets. |
| Skip pointers (DP) | “take or skip,” “previous house,” “ways from n−1 and n−2,” “optimal up to i” | Not scanning the array live. You read earlier DP cells (i-1, i-2, …) as dependency offsets. |
You are comparing nums[L] and nums[R] while sliding indices — that is still two-pointers, not DP skips. |
lo-mid-hi.
Offsets into a filled table (dp[i-1]) → Dynamic Programming.
A computed midpoint that halves a range → lo / mid / hi search.
total == target → found ittotal < target → need larger sum → move left righttotal > target → need smaller sum → move right left if total == target: return [left, right]
elif total < target: left += 1
else: right -= 1
set — track unique chars (Longest Substring Without Repeating)dict — track frequencies (Minimum Window Substring, Character Replacement)int — running sum (Min Size Subarray Sum, Best Time to Buy)freq[s[right]] += 1. For sum problems: total += nums[right].
window.remove(s[left]); left += 1
result = max(result, right - left + 1)
lo and hi bound the remaining search space; mid is computed each step (not walked like a window). Halve until the range collapses.
[lo, hi] is the classic interview default. Write the loop invariant aloud: “if the answer exists, it is still inside [lo, hi].”
<= when the range is inclusive.lo or hi) so the loop terminates. Off-by-one bugs almost always come from mixing inclusive/exclusive updates.
lo + (hi - lo) // 2 in languages that overflow on lo + hi.
if nums[mid] == target: return mid
elif nums[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
mid changes, not the lo/mid/hi skeleton.
lo grows the left bucket, hi grows the right bucket, mid walks the unknown middle once. One pass, O(1) extra space.
[0..lo) is bucket 0, [lo..mid) is bucket 1, (hi..n) is bucket 2, and [mid..hi] is unprocessed.
while mid <= hi:
if nums[mid] == 0:
nums[lo], nums[mid] = nums[mid], nums[lo]
lo += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[hi] = nums[hi], nums[mid]
hi -= 1 # do not mid++ yet
mid walks and swaps. Search mid is recomputed and never swapped with lo/hi. Same names, different jobs.
Both ends move inward. Two Sum II, Valid Palindrome, 3Sum, Container
Lead always advances; trail moves only when the window breaks. Sliding Window family.
Binary Search, Rotated Search, Sort Colors / 3-way partition
Same direction, different speeds. Cycle Detection, Middle Node
DP skip pointers (i-1/i-2) are covered under Dynamic Programming — they are not live scan cursors.
When you need to explore level by level, find the shortest path, or process all nodes at the same distance before moving deeper.
deque, never a list.list.pop(0) is O(n) — it shifts every element. deque.popleft() is O(1). This matters when the queue holds thousands of nodes.
len(queue) before the inner loop. New children added during the loop belong to the next level. This is what separates level-order BFS from a simple queue drain.
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(current_level)
return result
len(queue)) is the single line that separates "I know BFS" from "I understand BFS." Always mention it.
while queue:
r, c = queue.popleft()
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 (nr,nc) not in visited:
visited.add((nr, nc))
queue.append((nr, nc))
[(-1,0),(1,0),(0,-1),(0,1)] is a reusable constant. Name it DIRS for clarity.
When you need to explore to the deepest point first, compute a bottom-up value from subtrees, or explore all possible paths.
return 0return Truereturn [] right = solve(root.right)
lo < node.val < hi.
Initial call: isValid(root, -inf, inf).
return False
return isValid(node.left, lo, node.val) \
and isValid(node.right, node.val, hi)
n-1, n-2) are skip offsets, not live scan cursors.
ways(0) = 1, ways(1) = 1. For other DP problems, identify the smallest subproblem that has a known answer.
memo[n] = solve(n-1) + solve(n-2) # skip pointers
return memo[n]
When the answer at step i is built from a small set of earlier answers (optimal substructure) and the same subproblems would be recomputed without a table or memo (overlapping subproblems).
Translate the prompt language into a DP move:
| You hear… | You think… | Likely recurrence |
|---|---|---|
| “number of ways to climb / decode / reach” | Count paths through states | dp[i] = dp[i-1] + dp[i-2] (or more branches) |
| “maximum money without adjacent” / “take or skip” | Skip pointer choice at each house/index | dp[i] = max(dp[i-1], nums[i] + dp[i-2]) |
| “fewest coins / min edits / min path sum” | Minimize over prior feasible states | dp[x] = 1 + min(dp[x - choice]) |
| “paths in a grid (only right/down)” | 2D table; each cell from up + left | dp[r][c] = dp[r-1][c] + dp[r][c-1] |
| “longest common / increasing subsequence” | Compare chars/values; extend or reset | Diagonal extend on match; max of neighbors on mismatch |
DP “pointers” look like indices, but they behave differently from Two Pointers:
| Converging / One-way Contingent | Skip Pointers (DP) | |
|---|---|---|
| What moves? | Live cursors on the input (L, R) |
The fill index i; you read earlier cells |
| Why move? | Compare values / keep a window valid | Express the recurrence: take, skip, or combine prior answers |
| Example | while L < R or while invalid: L++ |
dp[i-1] (skip current) vs dp[i-2] (take & jump) |
| Gotcha | Do not call window shrink “DP” just because you have two indices | Do not invent a second live cursor when you only need prior states |
i-1 and i-2 are skip pointers into the DP table for the take-or-skip recurrence.”
dp[i-1]) or take it and skip the previous (nums[i] + dp[i-2]). Those i-1 / i-2 reads are skip pointers.
dp[i] = best result using only the prefix nums[0..i]. Climbing Stairs uses the same skeleton with + instead of max.
dp[0] = nums[0]
if len(nums) == 1: return dp[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], nums[i] + dp[i-2]) # skip vs take
return dp[-1]
prev2, prev1 rolling variables — the skip pointers become two scalars.
(r-1, c) and (r, c-1). Same idea as Minimum Path Sum with min + cell weight.
1 (only one way along the border), then fill the interior.
for r in range(m): dp[r][0] = 1
for c in range(n): dp[0][c] = 1
for r in range(1, m):
for c in range(1, n):
dp[r][c] = dp[r-1][c] + dp[r][c-1] # skip to up / left
return dp[m-1][n-1]
House Robber, Climbing Stairs, Decode Ways
Coin Change, Partition Equal Subset Sum
LCS, Edit Distance, Unique Paths, Min Path Sum
i-1 and i-2. Fibonacci in disguise.i-2 when you rob house i.Custom problems rarely hand you LeetCode stubs. Model the domain first, then algorithm.
| You hear… | You think… | You need… |
|---|---|---|
| "node with left/right" | tiny public data bag | struct TreeNode |
| "cache / queue / stack API" | encapsulate + invariants | class with methods |
| "graph of sensors / rooms" | identity + sharing | indices or Node* |
| "don't copy this object" | alias without ownership transfer | const T& |
| "this method shouldn't mutate" | document + enforce | const method |
struct over a heavy class when there are no invariants to protect.
string id; / double weight; for custom problems.vector<TreeNode>). Never store by-value children — that copies subtrees.
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
explicit avoids accidental conversions. Init list seeds members.const = "safe on a const object / won't mutate". Instant credibility.private:
vector<int> buf;
int head, size_;
};
vector/string/unique_ptr so you don't hand-write copy constructors under time pressure.Custom problems become: build the type → fill it from input → run BFS/Dijkstra on the API.
cout << node << " L=" << node->left;assert(cap > 0);const T&; mutate via non-const ref only when intentional.For custom prompts, name the nouns first. @dataclass keeps models clean; classic classes still win for heavy behavior.
| You hear… | You think… | You need… |
|---|---|---|
| "reading with ts + value" | immutable-ish data bag | @dataclass |
| "list of children / edges" | mutable default hazard | field(default_factory=list) |
| "left/right may be missing" | nullable child | Optional[TreeNode] |
| "use as dict key" | hashable record | frozen=True |
| "enqueue / get / put API" | behavior + state | classic class |
__init__, __repr__, __eq__. Perfect under interview time pressure.slots=True for many tiny objects; frozen=True when instances should be keys.tags: list = [] — that shared list bites everyone. default_factory is the fix.
self.val = val
self.next = next # Optional[ListNode]
next: Optional["ListNode"] (or ListNode | None) documents nullability without slowing you down.When the prompt is an API surface, skip dataclass — methods are the product.
print(node) is useless without __repr__ — dataclasses give you one free.asdict(obj) + pprint.def f(xs=[]) and items: list = [] in dataclasses..next pointers carefully.