Jake Tuero

Overview

16 min read

Leetcode

This note is meant to be a high level playbook for solving LeetCode-style problems. The goal is not to catalog every trick, but to build a repeatable process for recognizing the underlying structure of a problem and selecting a strong method quickly.

I generally prefer:

  • Optimal or near-optimal asymptotic solutions
  • Methods that generalize across many problems
  • Solutions built around a clean invariant or state definition
  • Avoiding one-off tricks unless the problem forces them

General Process

1. Classify the input and the output

Before thinking about code, classify what kind of object the problem gives you:

  • Array or string
  • Matrix / grid
  • Linked list
  • Tree
  • Graph
  • Interval set
  • Implicit state space

Then classify what the output is asking for:

  • Existence: does some solution exist?
  • Decision: true / false
  • Count: how many ways / objects?
  • Optimization: min / max / shortest / cheapest
  • Construction: return the path / ordering / structure / subsets

This usually narrows the candidate methods a lot.

2. Look for the strongest constraint first

The desired time complexity is usually hinted at by the input size.

  • n <= 20: brute force, subsets, bitmasking, backtracking are often acceptable
  • n <= 1000: O(n^2) may be fine, O(n log n) is usually good
  • n <= 10^5 or larger: usually need O(n) or O(n log n)

If the prompt says “can you do better than O(n^2)?” it is almost always pointing to a standard pattern, not a niche trick.

3. Ask what information must be remembered

Most problems reduce to one of these questions:

  • Do I need fast membership lookup? Use a hash set / map.
  • Do I need a moving valid region? Use a sliding window.
  • Do I need repeated best prefix / suffix information? Use DP, prefix sums, or Kadane-style state.
  • Do I need repeated exploration from a node or cell? Use DFS / BFS.
  • Do I need the next smallest / largest item repeatedly? Use a heap.
  • Do I need ordered access or range splitting? Use sorting or binary search.

4. Define the invariant before the implementation

Most good solutions become easy once the invariant is clear.

Examples:

  • Sliding window: “window [l, r] is always valid”
  • Binary search: “answer is always inside [l, r)”
  • DP: “dp[i] means the best / number of ways / feasibility for prefix or suffix i”
  • BFS: “everything currently in the queue is at the current distance or level”
  • DFS on trees: “the recursive return value is exactly the information the parent needs”

If you cannot state the invariant in one sentence, you probably do not understand the method yet.

5. Decide whether the problem is local or global

Local structure often suggests greedy or two pointers. Global dependence often suggests DP, graph search, or recursion.

  • Local: merging intervals, meeting rooms, container width decisions
  • Global: word segmentation, cheapest constrained path, tree reconstruction

Pattern Recognition by Problem Type

Arrays and strings

These are the most pattern-heavy problems. The first things to check are:

  • Hashing for membership or frequency
  • Two pointers for monotone movement
  • Sliding window for contiguous subarrays / substrings
  • Prefix sums for range aggregates
  • Sorting when relative order matters more than original position
  • Binary search when there is a monotone property

Hash map / hash set

Reach for hashing when you need:

  • Fast existence checks
  • Frequency counting
  • Matching complements
  • Deduplication

Examples:

Typical signal phrases:

  • “have we seen this before?”
  • “find two values that combine to …”
  • “count frequency”
  • “unique elements”

Two pointers

Use two pointers when both ends can move monotonically and you do not need to revisit positions.

Common cases:

  • Input already sorted
  • Need to shrink or expand a range
  • Need to compare symmetric characters or endpoints
  • Need to merge or partition in one pass

Examples:

Strong signal: moving one pointer can only make one quantity better and the other worse, so you can eliminate states safely.

Sliding window

Use sliding window when the answer is a contiguous region and validity can be maintained incrementally.

Good signals:

  • Subarray / substring
  • Longest / shortest contiguous block satisfying a condition
  • At most / at least k distinct, replacements, budget, frequency limit

Examples:

The key question is whether adding one element and removing one element lets you update the state without recomputing from scratch.

Prefix sums

Use prefix sums when many range queries can be answered from cumulative information.

Typical form:

  • prefix[i] stores information about everything before i
  • A range is computed by subtracting two prefixes

This extends beyond sums to counts, parity, balances, and transformed values.

Sorting

Sort when the actual values matter more than original order, especially for:

  • Intervals
  • Greedy scheduling
  • Sweep line logic
  • Grouping nearby values

Examples:

If sorting creates a left-to-right structure where each decision only depends on what has already been processed, that is usually a good sign.

Use binary search when there is a monotone predicate or partially sorted structure.

Two common forms:

  • Search for an element in structured data
  • Search for the smallest / largest feasible answer

Examples:

Ask:

  • If I guess an answer x, can I efficiently check whether x is feasible?
  • Does feasibility only switch once from false to true, or true to false?

Safe patterns:

  • Use m = low + (high - low) / 2 or std::midpoint(low, high) to avoid overflow
  • If your loop is while (low < high), updates must keep shrinking the window without stalling
  • A safe lower-mid template is:
while (low < high) {
    int m = low + (high - low) / 2;
    if (predicate(m)) {
        high = m;
    } else {
        low = m + 1;
    }
}

This is safe because high = m keeps m since it may be the answer, and low = m + 1 guarantees progress. The dangerous pattern with lower mid is low = m, since when m == low the loop can stall forever.

Rule of thumb:

  • Use while (low < high) when the answer is guaranteed to exist and you are narrowing to a single boundary value, such as Find Minimum in Rotated Sorted Array
  • Use while (low <= high) when searching for a target that may not exist, since you want to fully exhaust the candidate range before returning -1, such as Search in Rotated Sorted Array

For target search, a safe template is:

while (low <= high) {
    int m = low + (high - low) / 2;
    if (nums[m] == target) {
        return m;
    }
    if (target < nums[m]) {
        high = m - 1;
    } else {
        low = m + 1;
    }
}
return -1;

Small comparison rule:

  • Use inclusive comparisons when describing the current candidate interval or its structure, e.g. nums[l] <= nums[m] means the half [l, m] is sorted
  • Use strict comparisons against m after m has already been checked and ruled out, e.g. after if (nums[m] == target), use target < nums[m] or target > nums[m]
  • In rotated search, this is why nums[l] <= nums[m] is correct for identifying the sorted half, but nums[l] <= target && target < nums[m] is correct for checking whether the target lies in that half

Intervals

Intervals are usually one of:

  • Merge overlaps
  • Count concurrent intervals
  • Choose non-overlapping intervals optimally
  • Insert one interval into a sorted structure

The standard approach is almost always sorting by start or end, then scanning.

Examples:

Useful heuristics:

  • Sort by start if you need to merge or compare neighbors
  • Sort by end if you want a greedy maximum number of non-overlapping choices
  • Use a heap if you need the earliest finishing active interval repeatedly
  • Use a sweep line if you only need active counts over time

Linked lists

Linked list problems are usually pointer-manipulation problems. The main reusable ideas are:

  • Dummy head
  • Slow / fast pointers
  • Reverse a segment
  • Split and merge
  • Cycle detection

Examples:

Common signals:

  • “from end” often suggests two pointers with a gap
  • “cycle” suggests Floyd’s tortoise and hare
  • “reorder” often means split, reverse second half, merge alternating

Trees

Tree problems are often best solved by asking:

  • Is this naturally a traversal problem?
  • Does the parent need information from children?
  • Do I need DFS, BFS, or BST ordering?

DFS on trees

DFS is the default for most tree problems. The main question is what the recursive call should return.

Examples:

Useful mindset:

  • Define what dfs(node) returns
  • Make that return value be exactly what the parent needs
  • Keep any global answer separate if the local return and global optimum are different

For example, in maximum path sum, the value returned upward is not the same as the best path anywhere in the subtree.

BFS on trees

Use BFS when the problem is about levels, shortest unweighted distance, or nearest layer-by-layer behavior.

Example:

BST structure

If the problem is on a binary search tree, use the ordering immediately.

Examples:

Whenever you see BST, ask whether you can avoid exploring both subtrees by comparing values.

Tree construction

Construction problems usually combine recursion with index windows or maps.

Example:

The general pattern is:

  • One traversal tells you the root order
  • Another tells you subtree boundaries
  • A map avoids repeated searches

Graphs

Many problems are graphs even when they are not presented that way.

Hidden graph signals:

  • Courses with prerequisites
  • Words connected by transformations
  • Cells connected by moves
  • States reachable by operations

Once you see a graph, the next question is what kind:

  • Unweighted reachability: DFS / BFS
  • Unweighted shortest path: BFS
  • DAG ordering: topological sort
  • Weighted shortest path with non-negative weights: Dijkstra
  • Limited number of edges / transitions: DP or layered BFS / Bellman-Ford style relaxation
  • Connected components: DFS / BFS / Union-Find

DFS / BFS for reachability and components

Examples:

Use DFS when recursion makes the structure easy to express. Use BFS when distance in edges matters or the process is naturally layer-based.

Topological sort

Use topological sort for dependency problems on DAGs.

Examples:

Typical signal phrases:

  • “must happen before”
  • “ordering consistent with constraints”
  • “can all tasks be finished?”

Indegree + queue is usually the most reusable approach.

Shortest path

Decide based on the edge model:

  • All edges equal weight: BFS
  • Non-negative weights: Dijkstra
  • Bounded number of edges / stops: DP relaxation can be cleaner

Example:

This is a good example of not forcing Dijkstra when the constraint is really on the number of edges used. The state of the problem matters more than the classical graph label.

Matrices and grids

Grid problems are usually one of:

  • Flood fill / connected component search
  • Multi-source BFS
  • DFS backtracking path search
  • DP over rows / columns

Examples:

Quick recognition rules:

  • “spread”, “minimum minutes”, “nearest”, “fewest moves” often means BFS
  • “does a path exist following rules?” often means DFS / backtracking
  • “count paths” often means DP

Dynamic programming

DP is appropriate when:

  • There are overlapping subproblems
  • A brute force recursion would recompute the same states many times
  • The answer for a large instance can be built from smaller instances

Examples:

How to recognize DP

Ask these questions:

  • Is there a natural prefix, suffix, index, or state parameter?
  • If I write the obvious recursion, do many calls repeat?
  • Does the choice at one step leave me with a smaller problem of the same form?

How to design the state

Most DP work is state design. Common state types:

  • Prefix index: first i elements
  • Suffix index: from i onward
  • Two indices: substring / subsequence problems
  • Position plus extra condition: remaining sum, remaining capacity, previous choice, number of steps used

The state should be just enough information to make the future independent of the past.

Common DP families

1-D linear DP

Examples:

These often have the form:

  • Take current
  • Skip current
  • Transition from a small fixed number of previous states
Prefix / segmentation DP

Examples:

Signal: “can the prefix up to i be formed?” or “how many ways can suffix i: be parsed?”

2-D sequence DP

Examples:

Signal: comparing two sequences or solving over substring boundaries.

Knapsack-style DP

Examples:

Signal: choices consume some resource such as sum, weight, or capacity.

Backtracking

Use backtracking when you need to enumerate candidates under constraints.

Examples:

Recognition signals:

  • Return all combinations / subsets / permutations / paths
  • Constraint violations let you prune early
  • The space of possibilities forms a search tree

Backtracking template:

  1. Choose a candidate
  2. Recurse
  3. Undo the choice

The important part is pruning. Without pruning, backtracking often becomes too slow.

Greedy

Greedy is appropriate when a locally optimal choice can be shown not to hurt the global optimum.

Examples:

Good greedy signals:

  • Need only one scalar summary of everything seen so far
  • Earlier decisions can be proven to dominate worse ones
  • Sorting creates a canonical order where the best current choice is obvious

Greedy should usually come with a proof sketch, even if informal. If you cannot explain why the local choice is safe, DP may be the more reliable model.

Heaps

Use a heap when you repeatedly need the current smallest or largest item under updates.

Examples:

Typical signals:

  • “top k”
  • “stream”
  • “next smallest” while items are being inserted
  • Need an online algorithm

Choosing Between Similar Techniques

Sliding window vs two pointers

Use sliding window when you maintain a contiguous region with a validity condition.

Use general two pointers when the two indices move for a structural reason, often on sorted arrays or opposite ends.

DFS vs BFS

Use DFS when:

  • You only need existence, counting, structure, or postorder information
  • Recursion makes the relation natural

Use BFS when:

  • Shortest path in an unweighted graph matters
  • Layer / distance / minute / step count matters
  • You want nearest-first processing

DP vs backtracking

Use backtracking when you need to enumerate actual solutions.

Use DP when you only need existence, count, or optimum and subproblems overlap heavily.

DP vs greedy

Try greedy if the problem has a strong ordering and a local choice seems dominant.

If choices interact in a way that can invalidate a local decision later, DP is safer.

Sorting vs hashing

Use hashing for O(1) average lookup when order is irrelevant.

Use sorting when relative order or adjacency after ordering exposes the structure.

A Practical Checklist

When I see a new problem, I usually go through this checklist:

1. What is the object?

Array, string, tree, graph, interval set, grid, linked list?

2. What is being asked?

Existence, count, optimization, or construction?

3. What complexity is realistic?

From the constraints, which classes of algorithms are even allowed?

4. Is there a standard pattern signal?

  • Subarray / substring: sliding window or prefix sums
  • Dependency ordering: topological sort
  • Connected cells: DFS / BFS
  • Min / max over choices with overlap: DP
  • Sorted / rotated / monotone: binary search
  • Overlapping intervals: sort and scan

5. What should the state or invariant be?

Can I state in one sentence what my window, DP table, queue, or recursion means?

6. Can I solve a smaller version of the same problem?

If yes, recursion or DP is likely nearby.

7. Can I discard possibilities safely?

If yes, that usually points to greedy, two pointers, binary search, or pruning in backtracking.

Common Pitfalls

Forcing the wrong pattern

A problem may contain strings but really be a graph problem, or contain a grid but really be a shortest path problem.

Writing code before defining state

Most bugs in DP, sliding window, and graph traversal come from unclear state semantics.

Ignoring edge cases implied by the invariant

Examples:

  • Empty input
  • Single element
  • Duplicate values
  • Inclusive vs exclusive interval boundaries
  • Revisiting nodes or cells
  • Whether touching intervals count as overlap

Using a clever trick instead of a robust pattern

A one-off trick may pass a single problem but not build reusable instinct. Prefer a method you can explain and reuse unless the problem clearly demands something more specialized.

Final Heuristic

When in doubt, reduce the problem to one of these repeatable questions:

  • Can I scan once while maintaining a valid window?
  • Can I sort first so the structure becomes obvious?
  • Can I model it as a graph and traverse it?
  • Can I define a DP state that captures the remaining work?
  • Can I make a local greedy choice and justify why it is safe?
  • Can I search over the answer because feasibility is monotone?

If one of those questions has a clean answer, that is usually the method to grab first.

Pattern Lookup Table

Common signals

Signal in problem statementLikely techniqueCanonical examples
“find two values that sum / combine to target”Hash map, sometimes two pointers after sortingTwo Sum, 3Sum
“longest / shortest substring or subarray satisfying condition”Sliding windowLongest Substring Without Repeating Characters, Minimum Window Substring
“sorted array”, “rotated sorted array”, “find target in O(log n)”Binary search74 - Search a 2D Matrix, Search in Rotated Sorted Array
“overlapping intervals”, “minimum rooms”, “schedule meetings”Sorting + scan, heap, or sweep lineMerge Intervals, Meeting Rooms II
“tree level by level”BFSBinary Tree Level Order Traversal
“parent depends on children”DFS on treesMaximum Depth of Binary Tree, Binary Tree Maximum Path Sum
“BST”Use ordering to prune searchLowest Common Ancestor in Binary Search Tree, Kth Smallest Integer in BST
“can finish all tasks”, “dependency order”, “prerequisites”Topological sortCourse Schedule, Alien Dictionary
“connected components”, “islands”, “flood fill”DFS / BFS / Union-FindNumber of Islands, Max Area of Island
“fewest steps”, “minimum moves”, “spread over time” in unweighted graph or gridBFSRotting Fruit
“cheapest / shortest path” with weighted edgesDijkstra, or DP if edge count is constrainedCheapest Flights Within K Stops
“count ways”, “can segment”, “best value with repeated overlapping choices”Dynamic programmingWord Break, Decode Ways, House Robber
“return all combinations / paths / subsets”BacktrackingCombination Sum, Word Search
“stream of values”, “top k”, “repeatedly get min / max”HeapFind Median From Data Stream, Merge K Sorted Linked Lists
“linked list cycle”, “middle node”, “nth from end”Slow / fast pointersLinked List Cycle Detection, Remove Nth Node From End of List

Quick decision rules

If the problem feels like…Check this first
A contiguous region with a validity conditionSliding window
A repeated best choice among active candidatesHeap
A dependency graphTopological sort
A search over reachable statesDFS / BFS
An optimization over overlapping subproblemsDP
A local choice might safely dominate worse onesGreedy
Ordering the data may expose the structureSorting
The answer space is monotone under a feasibility testBinary search on answer

Graph View