DSA — A Theory-First Reference

This document is structured to give you the vocabulary of data structures and algorithms before you start solving problems. Every section follows the same pattern: what it is → how it works (with a picture) → complexity → when to recognize it → Java implementation. The last section is a pattern recognition cheat sheet — the part you'll come back to most.

SECTION 01Complexity Analysis & Big-O

Every algorithm has two costs: time (how many operations it performs) and space (how much memory it allocates). Big-O notation describes how those costs grow as the input size n grows. It ignores constants and lower-order terms because, for large n, only the dominant term matters.

Big-O is an upper bound. Saying an algorithm is O(n²) means "it grows no faster than quadratically." There are also Ω (lower bound) and Θ (tight bound), but in interview contexts, "Big-O" is almost always used to mean "tight worst case," and that's the convention this doc follows.

The growth-rate hierarchy

Memorize this ordering. From fastest (best) to slowest (worst):

Big-O	Name	n=10	n=1,000	n=1,000,000	Example
O(1)	Constant	1	1	1	Array index, HashMap get
O(log n)	Logarithmic	3	10	20	Binary search, balanced BST lookup
O(n)	Linear	10	1,000	10⁶	Single pass through array
O(n log n)	Linearithmic	33	10,000	2×10⁷	Merge sort, heap sort, efficient sorts
O(n²)	Quadratic	100	10⁶	10¹²	Nested loops, bubble/insertion sort
O(n³)	Cubic	1,000	10⁹	10¹⁸	Triple loop, naive matrix multiply, Floyd-Warshall
O(2ⁿ)	Exponential	1,024	~10³⁰⁰	infeasible	Subsets, naive Fibonacci, brute backtracking
O(n!)	Factorial	3.6M	infeasible	infeasible	Permutations, brute TSP

Reading complexity from code

A few mechanical rules let you derive Big-O without thinking too hard:

1. Sequential code adds: O(a) + O(b) → O(max(a,b)).
2. Nested loops multiply: a loop of n inside a loop of n is O(n²).
3. Halving the problem each step adds a log n factor.
4. Recursion: count nodes in the call tree. Each level's work × depth.
5. Built-ins are not free. list.contains(x) is O(n). str.substring(i,j) in Java is O(j-i). Arrays.sort is O(n log n).

Amortized analysis

Some operations are usually fast but occasionally slow. The amortized cost averages this over a sequence of operations.

Classic example: ArrayList.add(). When the internal array is full, it doubles in size — that single resize costs O(n). But this happens rarely (1 in every n inserts). Spread across n insertions, the total work is roughly 2n, so each add is amortized O(1).

Another: HashMap put(). Usually O(1), but during a resize-and-rehash it's O(n). Amortized: O(1).

Space complexity — the auxiliary part

When we say "O(n) space," we usually mean auxiliary space — extra memory beyond the input. The recursion call stack counts. A recursive DFS on a tree of height h uses O(h) stack space even if it returns no data.

This matters: a "constant space" solution that recurses n times uses O(n) space. Be precise.

What interview limits tell you

The constraint on n in a LeetCode problem is a hint about the expected complexity:

n ≤	Expected complexity	Approach
10	O(n!) or O(2ⁿ)	Backtracking, brute permutations
20	O(2ⁿ)	Bitmask DP, subset enumeration
100	O(n⁴) or O(n³)	DP with multiple dimensions, Floyd-Warshall
500–1,000	O(n²) or O(n³)	2D DP, all-pairs
10,000	O(n²) or O(n log n)	Quadratic DP, careful nested loops
10⁵	O(n log n)	Sort, heap, balanced BST, segment tree
10⁶	O(n) or O(n log n)	Linear scan, hash, two pointers
10⁸+	O(log n) or O(1)	Math, binary search, formula

---

SECTION 02Arrays & Strings

An array is a contiguous block of memory holding fixed-size elements at fixed offsets. The CPU can compute the address of element i as base + i × element_size, which is why indexing is O(1) — it's literally one pointer arithmetic operation, not a search.

A string in most languages (including Java) is an array of characters under the hood, with extra immutability guarantees. Everything in this section about arrays applies to strings.

Operations & complexity

Operation	Time	Why
Access arr[i]	O(1)	Direct address calculation
Search for value (unsorted)	O(n)	Must check each element
Search for value (sorted)	O(log n)	Binary search
Insert/delete at end (ArrayList)	amortized O(1)	Occasional resize
Insert/delete at index i	O(n)	Must shift all elements after i
Insert/delete at front	O(n)	Shifts every element

Fixed array vs ArrayList

// Fixed-size primitive array — fastest, no resize.
int[] a = new int[10];
a[0] = 42;

// Dynamic array — resizable, but boxes primitives.
List<Integer> list = new ArrayList<>();
list.add(42);                 // amortized O(1)
list.add(0, 99);            // O(n) — inserts at front, shifts everything
list.remove(list.size() - 1);  // O(1) — remove from end
list.remove(0);              // O(n) — shifts everything left

// 2D array — array of arrays.
int[][] grid = new int[m][n];
// grid[i][j] is O(1). The row grid[i] is itself an array reference.

String specifics in Java

Strings are immutable. Every + or substring creates a new String, copying chars. That single fact causes more accidentally-O(n²) code than anything else.

// ❌ O(n²) — each += copies the whole accumulated string
String s = "";
for (int i = 0; i < n; i++) s += chars[i];

// ✅ O(n) — StringBuilder appends in amortized O(1)
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(chars[i]);
String result = sb.toString();

When to recognize "array problem"

Three array techniques worth memorizing

Prefix sum

Pre-compute cumulative sums so that sum(i..j) = prefix[j+1] - prefix[i] in O(1). Spend O(n) upfront to answer any number of range-sum queries in O(1) each.

int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++)
    prefix[i + 1] = prefix[i] + arr[i];
// sum of arr[i..j] inclusive = prefix[j+1] - prefix[i]

In-place swap / reverse

Many array problems insist on O(1) extra space. The trick is almost always: swap, reverse, or partition in place.

void reverse(int[] a, int lo, int hi) {
    while (lo < hi) {
        int tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
        lo++; hi--;
    }
}

Sort first, then exploit order

If the problem doesn't require preserving input order, sorting (O(n log n)) often turns an O(n²) problem into O(n log n). Examples: 3Sum, merge intervals, finding duplicates with adjacent-equal check.

---

SECTION 03Hash Tables

A hash table maps keys to values in average O(1) time. It does this by running each key through a hash function that produces an integer, then using that integer modulo the table size to find a bucket.

Hash tables are the single most important data structure in coding interviews. Roughly 30% of "medium" LeetCode problems are solved by the right hash table choice. The reason: they let you check "have I seen this before?" or "what's associated with this key?" in constant time — turning many O(n²) brute force approaches into O(n) ones.

Java HashMap internals — the interview favorite

Java's HashMap uses separate chaining. Each bucket holds a linked list (or a red-black tree once the chain exceeds 8 entries — the treeify threshold). Key facts:

• Initial capacity is 16, load factor 0.75. When size > capacity × loadFactor, it doubles capacity and rehashes every entry.
• Hash is computed as (h = key.hashCode()) ^ (h >>> 16) — XORing high bits into low bits to mix entropy.
• The equals() and hashCode() contract: equal objects must produce equal hash codes. Equal hash codes do NOT imply equal objects (that's a collision). Break this contract and HashMap silently misbehaves.
• null keys are allowed (single bucket). Most other map implementations disallow them.

Operations & complexity

Operation	Average	Worst	Notes
get / contains	O(1)	O(n)	Worst = all keys collide
put	amortized O(1)	O(n)	Worst = full rehash
remove	O(1)	O(n)	—
Iterate all	O(n + capacity)	—	Iterates buckets too — keep capacity reasonable

HashMap vs HashSet vs LinkedHashMap vs TreeMap

Type	Order	Lookup	Use when
HashMap	none	O(1)	You need fast key→value lookup
HashSet	none	O(1)	You just need to test membership
LinkedHashMap	insertion (or access)	O(1)	LRU cache, ordered iteration
TreeMap	sorted by key	O(log n)	Need floor/ceiling/range queries

The three hash table patterns that solve half of all "easy" LeetCode

Pattern A — "Have I seen X before?"

// Two Sum: find i, j such that nums[i] + nums[j] = target.
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int need = target - nums[i];
    if (seen.containsKey(need)) return new int[]{seen.get(need), i};
    seen.put(nums[i], i);
}

Pattern B — Counting / frequency

// Frequency map: count occurrences of each element.
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.merge(c, 1, Integer::sum);
}

Pattern C — Grouping

// Group anagrams: key = sorted string, value = list of words.
Map<String, List<String>> groups = new HashMap<>();
for (String w : words) {
    char[] c = w.toCharArray();
    Arrays.sort(c);
    groups.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(w);
}

---

SECTION 04Linked Lists

A linked list is a chain of nodes, each holding a value and a pointer (reference in Java) to the next node. Unlike arrays, nodes are scattered in memory and accessed by following pointers from the head.

Linked lists are almost never the right answer for storing data in real systems — arrays are faster in practice due to cache locality. But they show up constantly in interviews because they test pointer manipulation, edge case handling, and recursion.

Singly vs doubly linked

A singly linked list has only next. A doubly linked list also has prev, doubling memory per node but allowing backward traversal and O(1) deletion if you have a node reference (no need to find the predecessor by re-walking from head).

Java's LinkedList<E> is doubly linked. It implements both List and Deque.

Operations & complexity

Operation	Singly	Doubly	Array
Access nth element	O(n)	O(n)	O(1)
Insert at head	O(1)	O(1)	O(n)
Insert at tail (with tail pointer)	O(1)	O(1)	amortized O(1)
Delete given a node reference	O(n) (find prev)	O(1)	O(n) (shift)
Search by value	O(n)	O(n)	O(n)

The three techniques that solve almost every linked list problem

1. Dummy head node

Allocating a "fake" node before the real head removes the special case where you're modifying the head itself. Almost every linked list problem that involves deletion or insertion becomes cleaner with this trick.

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy, cur = head;
while (cur != null) {
    if (cur.val == valToDelete) prev.next = cur.next;
    else prev = cur;
    cur = cur.next;
}
return dummy.next;  // works even if original head was deleted

2. Two pointers (slow / fast)

Send a fast pointer two steps for every one step of the slow pointer. Uses:

• Find the middle: when fast reaches the end, slow is at the middle.
• Detect a cycle: if there's a cycle, fast eventually meets slow (Floyd's algorithm).
• Find nth from end: advance fast n steps first, then move both until fast hits null.

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

3. Reverse a linked list (the building block)

Half of all linked list problems boil down to "reverse part of it." Memorize this pattern cold:

ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;  // save
        cur.next = prev;             // reverse pointer
        prev = cur;                  // advance prev
        cur = next;                  // advance cur
    }
    return prev;  // prev is the new head
}

---

SECTION 05Stacks & Queues

A stack is LIFO (last in, first out) — like a stack of plates. A queue is FIFO (first in, first out) — like a line at a coffee shop. Both restrict insertion and removal to specific ends.

Java implementations — what to actually use

// ❌ DON'T use Stack class — legacy, synchronized, slow.
Stack<Integer> old = new Stack<>();

// ✅ Use Deque via ArrayDeque for both stacks AND queues.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);  // stack ops on the "head"
int top = stack.peek();           // 2
int popped = stack.pop();          // 2

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);   // add to the back
int head = queue.poll();           // 1 — removes from the front

Operations & complexity

All core operations (push, pop, peek, offer, poll) are O(1). Search inside a stack or queue is O(n).

The killer pattern: monotonic stack

A monotonic stack keeps elements in a strictly increasing (or decreasing) order. When you push a new element, you pop everything in the way first. This solves a whole family of problems in O(n) that look like they need O(n²):

• Next Greater Element
• Daily Temperatures
• Largest Rectangle in Histogram
• Trapping Rain Water
• Stock Span Problem

// Next Greater Element — for each index, find the next index with a larger value.
int[] nextGreater(int[] nums) {
    int[] ans = new int[nums.length];
    Arrays.fill(ans, -1);
    Deque<Integer> stack = new ArrayDeque<>();  // stores indices
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            ans[stack.pop()] = i;  // nums[i] is the answer for that earlier index
        }
        stack.push(i);
    }
    return ans;
}

Why is this O(n) despite the nested-looking while? Because each index is pushed and popped at most once. Amortized constant work per element.

Monotonic deque — sliding window max

A deque (double-ended queue) lets you push/pop from both ends. Combined with the monotonic property, it solves "max in every sliding window of size k" in O(n).

int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();  // indices, values decreasing
    int[] ans = new int[nums.length - k + 1];
    for (int i = 0; i < nums.length; i++) {
        while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
        dq.offerLast(i);
        if (i >= k - 1) ans[i - k + 1] = nums[dq.peekFirst()];
    }
    return ans;
}

---

SECTION 06Trees & BSTs

A tree is a hierarchical structure: a root node with children, each of which can have children, and so on. Trees have no cycles. A binary tree restricts each node to at most two children, called left and right.

Vocabulary

• Root — the top node, parent of everything.
• Leaf — a node with no children.
• Depth of a node — distance (in edges) from root to that node. Root has depth 0.
• Height of a node — distance from that node to the deepest leaf below it. Leaves have height 0. Height of the tree = height of the root.
• Balanced tree — for every node, the heights of left and right subtrees differ by at most 1. A balanced tree of n nodes has height O(log n).
• Complete tree — every level is full except possibly the last, which is filled left-to-right.

Tree node definition (Java)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

Tree traversals — the four orderings

For the tree in Figure 6.1, each traversal visits nodes in a different order:

Traversal	Order	Result for Fig 6.1	Use case
Preorder	node → left → right	8, 3, 1, 0, 6, 12, 14	Copy tree, serialize
Inorder	left → node → right	0, 1, 3, 6, 7, 8, 12, 14	BST gives sorted output
Postorder	left → right → node	0, 1, 7, 6, 3, 14, 12, 8	Delete tree, evaluate expression
Level-order (BFS)	top to bottom, left to right	8, 3, 12, 1, 6, 14, 0, 7	Print by levels, shortest path

// Inorder traversal (recursive) — gives sorted order for a BST.
void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorder(node.left, out);
    out.add(node.val);
    inorder(node.right, out);
}

// Level-order traversal (iterative with queue).
List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode n = q.poll();
            level.add(n.val);
            if (n.left != null) q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        ans.add(level);
    }
    return ans;
}

BST: search, insert, delete

Operation	Balanced BST	Unbalanced (worst)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

The worst case is a BST that has degenerated into a linked list (inserting sorted values). Self-balancing BSTs like AVL trees and Red-Black trees automatically maintain balance through rotations.

AVL vs Red-Black — the interview answer

	AVL Tree	Red-Black Tree
Balance constraint	Strict: subtree heights differ by ≤ 1	Relaxed: longest path ≤ 2× shortest
Search speed	Slightly faster (more balanced)	Slightly slower
Insert/delete	More rotations, slower	Fewer rotations, faster
Best for	Read-heavy workloads	Write-heavy workloads
Used in	Some databases	Java TreeMap, C++ std::map, Linux kernel

---

SECTION 07Heaps / Priority Queues

A heap is a complete binary tree with the heap property: every parent is ≤ both its children (min-heap) or ≥ both its children (max-heap). The root is therefore the smallest (or largest) element.

Heaps are almost always implemented as arrays, not actual tree nodes. For index i in a 0-indexed array:

• Parent = (i - 1) / 2
• Left child = 2i + 1
• Right child = 2i + 2

Operations & complexity

Operation	Time	What it does
peek() — min/max	O(1)	Return root
poll() — extract min/max	O(log n)	Remove root, sift last element down
offer(x) — insert	O(log n)	Append at end, sift up
Heapify (build from array)	O(n)	Bottom-up sift-down, not n log n!
remove(arbitrary x)	O(n)	Linear search first

Java's PriorityQueue

// Min-heap (default).
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max-heap — pass reverse comparator.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Custom comparator — by frequency ascending, then by value descending.
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
    a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]
);

// O(n) build from existing collection.
PriorityQueue<Integer> built = new PriorityQueue<>(Arrays.asList(5, 2, 9, 1, 7));

The three heap patterns

1. Top-K elements (Kth largest, K most frequent)

Keep a min-heap of size k. For each new element, if the heap has fewer than k items push it; otherwise compare with heap's min and replace if larger. The heap's root is the kth largest. Total: O(n log k) — better than sorting (O(n log n)) when k is small.

int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int n : nums) {
        minHeap.offer(n);
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.peek();
}

2. Merge K sorted streams

Put the head of each list into a min-heap. Repeatedly poll the smallest, append to result, and push that list's next element. Time: O(n log k) for k lists of total n elements.

3. Two heaps (median maintenance)

Keep a max-heap for the lower half and a min-heap for the upper half, balanced so they differ in size by at most 1. The median is the top of one (or average of both tops). All operations O(log n).

---

SECTION 08Tries (Prefix Trees)

A trie is a tree where each edge represents a character. Words are formed by paths from the root. Tries excel at prefix-based operations: autocomplete, spell-check, longest common prefix, word search puzzles.

Operations & complexity

Let L = length of the word, Σ = alphabet size (26 for lowercase English).

Operation	Time	Space (worst)
Insert word	O(L)	O(L · Σ) per new path
Search exact word	O(L)	—
Search prefix	O(L)	—
Total space	—	O(N · L · Σ) upper bound for N words

Java implementation

class Trie {
    private static class Node {
        Node[] children = new Node[26];
        boolean isEnd;
    }
    private final Node root = new Node();

    public void insert(String w) {
        Node cur = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) cur.children[i] = new Node();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }

    public boolean search(String w) {
        Node n = walk(w);
        return n != null && n.isEnd;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    private Node walk(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.children[c - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }
}

---

SECTION 09Graphs

A graph is a set of vertices (nodes) connected by edges. Unlike trees, graphs can have cycles and a node can have any number of "parents." Real-world examples: road networks, social networks, web links, dependency graphs, the internet itself.

Vocabulary

• Directed — edges have direction (A → B but not B → A). E.g., Twitter follows.
• Undirected — edges are bidirectional. E.g., Facebook friends.
• Weighted — edges carry a number (distance, cost, capacity).
• Cyclic / acyclic — has a cycle, or doesn't. DAG = directed acyclic graph.
• Connected component — a maximal set of vertices all reachable from each other.
• Dense vs sparse — many edges (close to V²) vs few edges (close to V).

Two ways to represent a graph

Adjacency list — the Java idiom

// Build adjacency list from edge list.
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
    adj.get(e[0]).add(e[1]);
    adj.get(e[1]).add(e[0]);  // omit for directed graph
}

BFS & DFS — the two fundamental traversals

Both visit every reachable vertex. BFS uses a queue and explores level by level. DFS uses a stack (or recursion) and explores as deep as possible before backtracking. Both run in O(V + E).

BFS template

void bfs(int start, List<List<Integer>> adj) {
    boolean[] visited = new boolean[adj.size()];
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    visited[start] = true;          // mark visited WHEN ENQUEUEING, not when polling
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                queue.offer(v);
            }
        }
    }
}

DFS template (recursive)

void dfs(int u, boolean[] visited, List<List<Integer>> adj) {
    visited[u] = true;
    // process u here
    for (int v : adj.get(u)) {
        if (!visited[v]) dfs(v, visited, adj);
    }
}

BFS vs DFS — when to pick which

	BFS	DFS
Shortest path (unweighted)	✓ Optimal	✗ Wrong
"Is there any path?"	Works	Works (often simpler code)
Detect cycle	Works	Standard choice
Topological sort	Kahn's algorithm	Reverse post-order
Find all connected components	Works	Works
Memory on a tree of height h	O(width)	O(h)

Topological sort (DAG ordering)

Given a DAG of dependencies (e.g., course prerequisites), produce a linear ordering where each node appears before all nodes it points to. Kahn's algorithm uses BFS:

int[] topoSort(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    int[] inDeg = new int[n];
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); inDeg[e[1]]++; }

    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (inDeg[i] == 0) q.offer(i);

    int[] order = new int[n];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u;
        for (int v : adj.get(u))
            if (--inDeg[v] == 0) q.offer(v);
    }
    return idx == n ? order : new int[0];  // empty = cycle exists
}

Shortest path algorithms

Algorithm	Use case	Time
BFS	Unweighted shortest path	O(V + E)
Dijkstra	Weighted, non-negative edges	O((V + E) log V) with binary heap
Bellman-Ford	Weighted, allows negative edges (detects negative cycles)	O(V · E)
Floyd-Warshall	All-pairs shortest paths	O(V³)
A*	Pathfinding with heuristic	Depends on heuristic

Dijkstra in 20 lines

int[] dijkstra(int n, List<int[]>[] adj, int src) {
    // adj[u] = list of {v, weight}
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // {distance, node} — sorted by distance ascending
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, src});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;             // stale entry — skip
        for (int[] e : adj[u]) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}

---

SECTION 10Union-Find (Disjoint Set Union)

Union-Find tracks a collection of disjoint sets and supports two operations:

• find(x) — return the "representative" (root) of x's set.
• union(x, y) — merge the sets containing x and y.

Two elements are in the same set iff they have the same root. This makes Union-Find the go-to structure for "are these connected?" questions, dynamic connectivity, and Kruskal's MST algorithm.

Why it's fast

With two optimizations — path compression (during find, point every visited node directly to the root) and union by rank/size (always attach the smaller tree under the larger) — both operations run in amortized O(α(n)), where α is the inverse Ackermann function. For any n in this universe, α(n) ≤ 4. So in practice: essentially O(1).

Java implementation (the one to memorize)

class DSU {
    private final int[] parent, rank;

    public DSU(int n) {
        parent = new int[n];
        rank   = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;  // each its own parent initially
    }

    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;                // already in same set
        if (rank[rx] < rank[ry])      parent[rx] = ry;
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }       // equal ranks: pick one, bump
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

---

SECTION 11Sorting Algorithms

You will rarely implement a sort from scratch in an interview — Arrays.sort exists. But you must know the trade-offs because the choice of sort affects your overall complexity, and "sort first, then..." is the secret to many medium problems.

The comparison-sort lower bound

Any comparison-based sort needs at least O(n log n) comparisons in the worst case. This is a mathematical fact (proven via the decision-tree argument). So O(n log n) sorts like merge/heap/quick are optimal among comparison sorts. Sorts that beat this — counting sort, radix sort — work only on restricted input (small-integer keys).

The sorting comparison table

Algorithm	Best	Avg	Worst	Space	Stable?	In-place?
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No	Yes
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No
Quick sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Yes
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Yes
Counting	O(n + k)	O(n + k)	O(n + k)	O(n + k)	Yes	No
Radix	O(d·(n+k))	same	same	O(n + k)	Yes	No
Tim sort (Java Arrays.sort for objects)	O(n)	O(n log n)	O(n log n)	O(n)	Yes	No

Stable = equal elements keep their relative order. Important when sorting by a secondary key.
In-place = uses constant extra memory (besides the call stack).

What Java actually uses

• Arrays.sort(int[]) — Dual-Pivot Quicksort (very fast for primitives, not stable, doesn't matter for primitives).
• Arrays.sort(Object[]) and Collections.sort() — Tim Sort (stable, exploits already-sorted runs).
• Arrays.parallelSort() — Parallel merge sort.

Merge sort — the classic divide-and-conquer

Quick sort — the practical workhorse

Pick a pivot, partition the array so smaller elements are on the left and larger on the right, then recurse on both halves. Average case is fast and cache-friendly; the worst case (already-sorted input with poor pivot choice) is O(n²), which is why production implementations randomize the pivot or use median-of-three.

void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
    return i + 1;
}

Quickselect — the cousin you must know

To find the kth smallest/largest element in average O(n): partition like quicksort, but only recurse into the side containing position k. This is the standard "Kth largest element" solution that beats the heap approach.

Counting sort — when you can beat n log n

If your input is integers in a small range [0, k], you can sort in O(n + k) without comparisons by counting occurrences and reconstructing. Trade-off: uses O(n + k) space; useless if k is huge.

---

SECTION 12Searching & Binary Search

Linear search (O(n)) is the brute force. The interesting algorithm is binary search — O(log n) on a sorted array — and its powerful generalization, binary search on the answer space.

The classic binary search

int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;     // avoid overflow
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

The two-template approach (memorize both)

Template A: exact match

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (check(mid)) return mid;
    else if (...) lo = mid + 1;
    else hi = mid - 1;
}
return -1;

Template B: find boundary (leftmost/rightmost satisfying a condition)

// Smallest index where condition(mid) is true.
int lo = 0, hi = n;     // note hi = n, not n-1
while (lo < hi) {        // strict less-than
    int mid = lo + (hi - lo) / 2;
    if (condition(mid)) hi = mid;       // don't skip a candidate
    else lo = mid + 1;
}
return lo;  // or hi — they're equal

Template B is the more powerful one. Use it for: first occurrence in a duplicated sorted array, smallest value ≥ target, first bad version, etc.

Binary search on the answer — the killer pattern

This is the technique that turns hard problems into medium ones. The idea: when the answer is a number in some range [lo, hi], and you can write a function canAchieve(x) that returns true if x is feasible, then binary-search the range for the boundary.

Classic example: Koko Eating Bananas (LC 875). Koko has n piles of bananas and h hours. She eats at speed k bananas/hour. Find the minimum k such that she finishes within h hours.

int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
    while (lo < hi) {
        int k = lo + (hi - lo) / 2;
        if (canFinish(piles, k, h)) hi = k;     // k works, try smaller
        else lo = k + 1;                     // k too slow
    }
    return lo;
}

boolean canFinish(int[] piles, int k, int h) {
    int hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;  // ceil division
    return hours <= h;
}

Total complexity: O(n log m) where m = max pile. We avoid the O(n · m) brute force of trying every speed.

---

SECTION 13Two Pointers & Sliding Window

Two of the most reliably-asked patterns. Both use indices into an array (or string) that move based on logic, replacing nested-loop O(n²) brute force with single-pass O(n).

Pattern 1: Two pointers — converging from both ends

Used when the input is sorted (or you sort it first) and you're looking for a pair, triplet, or any condition involving two elements at different positions.

boolean hasPairWithSum(int[] sorted, int target) {
    int L = 0, R = sorted.length - 1;
    while (L < R) {
        int sum = sorted[L] + sorted[R];
        if (sum == target) return true;
        else if (sum < target) L++;
        else R--;
    }
    return false;
}

Pattern 2: Sliding window — fixed size

Used for "find some property over every contiguous subarray of size k". Compute the property for the first window, then slide: subtract the leaving element, add the entering one. O(n) total.

// Maximum sum of any subarray of size k.
int maxSumK(int[] nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i];
    int best = sum;
    for (int i = k; i < nums.length; i++) {
        sum += nums[i] - nums[i - k];      // slide
        best = Math.max(best, sum);
    }
    return best;
}

Pattern 3: Sliding window — variable size (expand / shrink)

This is the powerful one. The window grows on the right and shrinks from the left based on a validity condition. O(n) total because each index enters and leaves the window at most once.

int longestKDistinct(String s, int k) {
    Map<Character, Integer> count = new HashMap<>();
    int L = 0, best = 0;
    for (int R = 0; R < s.length(); R++) {
        count.merge(s.charAt(R), 1, Integer::sum);
        while (count.size() > k) {                 // invalid → shrink
            char c = s.charAt(L++);
            if (count.merge(c, -1, Integer::sum) == 0)
                count.remove(c);
        }
        best = Math.max(best, R - L + 1);
    }
    return best;
}

---

SECTION 14Recursion & Backtracking

A recursive function solves a problem by calling itself on smaller subproblems. Every recursion needs two things: a base case (the smallest problem, solved directly) and a recursive case (reduce the problem and recurse).

Backtracking is recursion plus a "try, undo, try the next option" pattern. Used for problems that need to explore all (or some) configurations: permutations, combinations, subsets, N-Queens, Sudoku, word search in a grid.

The recursion call tree

Recursion template

ReturnType solve(Params p) {
    // 1. Base case — when to stop and return directly
    if (isBaseCase(p)) return trivialAnswer(p);

    // 2. Recursive case — reduce the problem and combine
    ReturnType sub = solve(reduce(p));
    return combine(p, sub);
}

Complexity of recursive algorithms

Two factors: number of nodes in the call tree × work per node.

• Linear recursion (one call per level): O(n) calls, depth O(n) stack.
• Binary recursion (two calls per level): O(2ⁿ) calls in the worst case.
• Divide and conquer (each call splits work in half, work scales with size): solved by the Master Theorem — typically O(n log n).
• Always count stack space. A recursive DFS to depth d uses O(d) stack regardless of return value size.

Backtracking template — the one to memorize

void backtrack(List<Integer> path, State state) {
    if (isGoal(state)) {
        result.add(new ArrayList<>(path));   // copy! mutable path
        return;
    }
    for (Choice c : getChoices(state)) {
        if (!isValid(c, state)) continue;     // pruning
        path.add(c);            apply(state, c);    // 1. choose
        backtrack(path, state);                     // 2. explore
        path.remove(path.size() - 1);             // 3. un-choose
        undo(state, c);
    }
}

The three steps — choose, explore, un-choose — appear in every backtracking solution. Internalize the rhythm.

Concrete example: permutations

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    backtrack(nums, new ArrayList<>(), new boolean[nums.length], ans);
    return ans;
}

void backtrack(int[] nums, List<Integer> path,
               boolean[] used, List<List<Integer>> ans) {
    if (path.size() == nums.length) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        path.add(nums[i]);   used[i] = true;     // choose
        backtrack(nums, path, used, ans);          // explore
        path.remove(path.size() - 1);            // un-choose
        used[i] = false;
    }
}

Complexity: O(n · n!) time (n! permutations, each costing O(n) to copy). O(n) auxiliary space for the path and used array (excluding output).

Pruning — backtracking's secret weapon

Naive backtracking is exponential. Pruning means cutting branches that can't lead to a solution before exploring them. Examples:

• N-Queens: check column/diagonal conflicts immediately, not after placing all queens.
• Subsets summing to target: sort first; once a partial sum exceeds target, prune.
• Sudoku: at each empty cell, only try digits that don't violate row/col/box.

The complexity savings from good pruning are huge but hard to characterize formally — they show up empirically as huge speedups even though worst-case Big-O is unchanged.

---

SECTION 15DFS & BFS in Depth

Section 9 introduced DFS and BFS for graphs. They're worth a deeper section because the same two algorithms solve a huge variety of problems beyond plain graph traversal: trees, grids, state-space search, mazes, and more.

DFS on trees — the universal template

Almost every tree problem can be solved by a recursive function that returns "something useful" from each subtree:

ReturnType dfs(TreeNode node) {
    if (node == null) return baseValue;
    ReturnType left  = dfs(node.left);
    ReturnType right = dfs(node.right);
    return combine(node, left, right);
}

Examples of what "ReturnType" can be:

• Height of tree: int. combine = max(left, right) + 1.
• Validate BST: a small struct {min, max, isBST}. Combine checks that node.val sits between left.max and right.min.
• Diameter of tree: int (height), with a side-effect global tracking max(left+right).
• Lowest common ancestor: node found in subtree, or null.

BFS on grids — multi-source & shortest path

A 2D grid is a graph in disguise: each cell connects to its 4 (or 8) neighbors. Convert grid coords to graph BFS:

int[][] DIRS = {{-1,0}, {1,0}, {0,-1}, {0,1}};

int shortestPath(int[][] grid, int[] start, int[] target) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> q = new ArrayDeque<>();
    boolean[][] seen = new boolean[rows][cols];
    q.offer(new int[]{start[0], start[1], 0});  // {row, col, distance}
    seen[start[0]][start[1]] = true;
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        if (cur[0] == target[0] && cur[1] == target[1]) return cur[2];
        for (int[] d : DIRS) {
            int nr = cur[0] + d[0], nc = cur[1] + d[1];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (seen[nr][nc] || grid[nr][nc] == 1) continue;  // wall
            seen[nr][nc] = true;
            q.offer(new int[]{nr, nc, cur[2] + 1});
        }
    }
    return -1;
}

Multi-source BFS

Instead of starting from one node, push all sources into the queue initially. The BFS expands outward from every source simultaneously — useful for problems like "rotten oranges" (how long until all oranges are rotten if rot spreads from multiple initial rotten ones) or "walls and gates" (distance to nearest gate for every empty cell).

// Push all initial sources before starting BFS.
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        if (grid[i][j] == ROTTEN) {
            q.offer(new int[]{i, j, 0});
            seen[i][j] = true;
        }
    }
}
// Then run a normal BFS — it spreads from every source at once.

"Number of islands" — DFS template for grid connectivity

int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                count++;
                sink(grid, i, j);
            }
        }
    }
    return count;
}

void sink(char[][] g, int r, int c) {
    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';   // mark visited by sinking the land
    sink(g, r + 1, c); sink(g, r - 1, c);
    sink(g, r, c + 1); sink(g, r, c - 1);
}

Complexity: O(R · C) time, since each cell is sunk at most once. O(R · C) stack depth in the worst case (one huge connected region).

---

SECTION 16Dynamic Programming

Dynamic Programming (DP) is recursion plus memoization — when the recursive call tree has overlapping subproblems, we cache results so each subproblem is computed only once. This turns exponential algorithms into polynomial ones.

The two requirements

A problem is solvable by DP if and only if it has:

1. Optimal substructure — the optimal answer can be built from optimal answers to subproblems.
2. Overlapping subproblems — the same subproblem appears in multiple paths through the recursion.

Without overlap, you have plain recursion (or divide-and-conquer). Without optimal substructure, you have a search problem (backtracking).

Top-down vs bottom-up

	Top-down (memoization)	Bottom-up (tabulation)
Style	Recursive + cache	Iterative fill of a table
Pros	Closer to the natural recurrence; only computes needed states	No recursion stack; often faster constants; easy to optimize space
Cons	Stack overflow risk on deep recursion	Sometimes computes states you don't need
When to prefer	State space is sparse / irregular	Dense state space, performance matters

Fibonacci — the canonical example

// O(2ⁿ) — naive recursion
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// O(n) time, O(n) space — top-down with memo
int fib(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

// O(n) time, O(n) space — bottom-up
int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

// O(n) time, O(1) space — rolling variables
int fib(int n) {
    if (n <= 1) return n;
    int prev = 0, cur = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + cur;
        prev = cur; cur = next;
    }
    return cur;
}

Notice how each version improves on the last by either eliminating redundant work (memo) or compressing state (rolling). This progression — naive → memoized → tabulated → space-optimized — is the standard DP problem-solving workflow.

The DP problem-solving template

1. Define the state. What does dp[i] or dp[i][j] mean? Make this rigorous — "the answer for the first i items considering capacity j."
2. Write the recurrence. How does dp[i] relate to smaller states? Usually: try each choice, take min/max/sum.
3. Establish base cases. The smallest valid states.
4. Choose iteration order. Bottom-up requires you to fill states in an order such that all their dependencies are already computed.
5. Optimize space. If dp[i] only depends on dp[i-1] (or a few prior rows), collapse to O(1) extra space.

The DP families you'll encounter

1D DP — climbing stairs / house robber family

House Robber: given an array of values (each house's loot), pick a non-adjacent subset of max total.

int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;
    for (int n : nums) {
        int cur = Math.max(prev1, prev2 + n);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

State: dp[i] = max loot considering first i houses. Choice: rob house i (add nums[i] to dp[i-2]) or skip (dp[i-1]). Complexity: O(n) time, O(1) space.

2D DP — grid paths / unique paths

Unique Paths: count paths from top-left to bottom-right of an m×n grid, moving only right or down.

int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    return dp[m-1][n-1];
}

Complexity: O(m · n) time and space. Can be reduced to O(min(m,n)) space using a single row.

Knapsack family

0/1 Knapsack: items with weight and value; pick a subset (each used at most once) to maximize value subject to a weight limit W.

// dp[i][w] = max value using first i items with capacity w.
int knapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];   // skip item i
            if (wt[i-1] <= w)
                dp[i][w] = Math.max(dp[i][w], dp[i-1][w - wt[i-1]] + val[i-1]);
        }
    }
    return dp[n][W];
}

Complexity: O(n · W). This is pseudo-polynomial — polynomial in W's value, but exponential in W's number of bits.

Variants:

• Unbounded knapsack: each item can be used any number of times. Inner loop iterates forward; dp[i][w] can use dp[i][w-wt] (same row).
• Coin change (min coins): classic unbounded knapsack variant.
• Subset sum / partition equal subset: 0/1 knapsack with boolean DP.

String DP — edit distance & LCS

Longest Common Subsequence (LCS): given two strings, find the length of their longest common subsequence (not contiguous).

int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i-1) == b.charAt(j-1))
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}

Edit distance (Levenshtein): minimum operations (insert/delete/replace) to transform string a into string b. Same structure: dp[i][j] based on whether last characters match.

Both: O(m · n) time and space.

Longest Increasing Subsequence (LIS)

// O(n²) DP — for each i, look back at all j < i.
int lis(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int best = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i])
                dp[i] = Math.max(dp[i], dp[j] + 1);
        best = Math.max(best, dp[i]);
    }
    return best;
}

There's also an O(n log n) solution using binary search + "patience sorting" — worth knowing the existence of, but the O(n²) version is enough for most interview contexts.

Interval DP — burst balloons, matrix chain

State dp[i][j] represents the answer for the subarray [i, j]. You compute it by picking some "split point" k between i and j and combining dp[i][k] and dp[k+1][j]. Complexity: typically O(n³).

Common DP state-design heuristics

If the problem mentions…	The state is often…
"first i elements" / "first i houses"	dp[i]
Two sequences/strings	dp[i][j] (positions in each)
"At most k operations"	dp[i][k]
Position in grid	dp[i][j]
Subarray/substring problems	dp[i][j] (left and right endpoints)
Subset of items (n ≤ 20)	dp[mask] with bitmask
Tree problem with two states per node	dp[node][0] / dp[node][1]

---

SECTION 17Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, hoping that this sequence of local optima yields a global optimum. When it works, it's clean and fast. When it doesn't, it's wrong — silently.

When does greedy work?

Greedy is correct when the problem has the greedy choice property: a globally optimal solution can be reached by making the locally optimal choice at each step. Proving this usually requires an exchange argument: show that if any non-greedy solution exists, you can swap one of its choices for the greedy one without making it worse.

Greedy is wrong when: local optimum doesn't compose to global optimum. Example: 0/1 Knapsack with weights {3, 5, 6} values {3, 5, 9}, capacity 7. Greedy by value/weight ratio picks item 3 first (best ratio), then nothing fits, total = 9. But picking items 1+2 gives total = 8 — wait, actually 9 wins. Let me pick a clearer one: capacity 5, weights {2,3,4}, values {3,4,5}. Greedy by value/weight: item 1 (ratio 1.5), then item 2 (ratio 1.33) → total weight 5, total value 7. Optimal: items 2+? = 4. Greedy wins here. The point: you can't know greedy works without proving it.

Classic greedy problems

Activity Selection / Interval Scheduling

Given intervals (start, end), select the maximum number of non-overlapping intervals. Greedy rule: always pick the interval with the earliest end time that doesn't conflict.

int maxNonOverlapping(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);  // sort by end time
    int count = 0, lastEnd = Integer.MIN_VALUE;
    for (int[] iv : intervals) {
        if (iv[0] >= lastEnd) {
            count++;
            lastEnd = iv[1];
        }
    }
    return count;
}

Why earliest end? Because it leaves the most room for future intervals. The exchange argument: any optimal solution must include some interval; if it doesn't include the one with the earliest end, swap it in — you don't lose anything because that interval ends earliest.

Complexity: O(n log n) for the sort, O(n) for the pass.

Jump Game

Given nums[i] = max jump length from position i, can you reach the last index? Greedy: track the farthest reachable index as you scan.

boolean canJump(int[] nums) {
    int reach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > reach) return false;          // can't even get here
        reach = Math.max(reach, i + nums[i]);
    }
    return true;
}

Other classic greedy problems

• Minimum platforms / meeting rooms II: sort starts and ends, two pointers.
• Gas station: if total gas ≥ total cost, the answer exists; find it by tracking running deficit.
• Huffman coding: repeatedly merge the two least-frequent symbols (priority queue based).
• Kruskal's MST: sort edges by weight, add to tree if it doesn't form a cycle (DSU).
• Prim's MST: grow the tree by always adding the cheapest edge connected to it (priority queue).

---

SECTION 18Divide & Conquer

Divide and conquer (D&C) solves a problem by:

1. Divide the problem into smaller subproblems.
2. Conquer each subproblem recursively.
3. Combine the subproblem solutions.

The pattern shows up everywhere: merge sort, quick sort, binary search, FFT, matrix multiplication, computational geometry. It overlaps with DP when subproblems overlap; D&C is the right term when they don't.

The Master Theorem (interview cheat version)

For recurrences of the form T(n) = a · T(n/b) + f(n) where:

• a = number of recursive calls
• n/b = size of each subproblem
• f(n) = work done outside the recursive calls

Compare f(n) to nlogba:

Case	Condition	Result
1	f(n) grows slower than nlogba	T(n) = Θ(nlogba)
2	f(n) grows at the same rate	T(n) = Θ(nlogba · log n)
3	f(n) grows faster (with regularity)	T(n) = Θ(f(n))

Worked examples

Merge sort: T(n) = 2 · T(n/2) + O(n). Here a=2, b=2, so n^log₂2 = n. f(n) = n grows at the same rate → Case 2 → O(n log n).

Binary search: T(n) = 1 · T(n/2) + O(1). a=1, b=2, n^log₂1 = n⁰ = 1. f(n)=1 grows at the same rate → Case 2 → O(log n).

Karatsuba multiplication: T(n) = 3 · T(n/2) + O(n). a=3, b=2, n^log₂3 ≈ n^1.585. f(n)=n grows slower → Case 1 → O(n^1.585).

Maximum subarray (Kadane vs D&C)

Kadane's algorithm solves max subarray in O(n) using DP (covered later). The D&C solution is interesting because it shows the pattern clearly:

int maxSub(int[] a, int lo, int hi) {
    if (lo == hi) return a[lo];
    int mid = lo + (hi - lo) / 2;
    int leftMax  = maxSub(a, lo, mid);
    int rightMax = maxSub(a, mid + 1, hi);
    int crossMax = maxCrossing(a, lo, mid, hi);  // must span midpoint
    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

The crossing case is O(n), recursion gives the recurrence T(n) = 2T(n/2) + O(n) → O(n log n). Worse than Kadane's O(n), but elegant.

---

SECTION 19Bit Manipulation

Bit manipulation problems exploit the binary representation of integers. They're rarely asked at FAANG except as a "did you take systems class" filter, but the few that appear repeat. Memorize the operators and the half-dozen identities and you're done.

The operators

Operator	Symbol	What it does
AND	&	Bit set in both
OR	|	Bit set in either
XOR	^	Bit set in exactly one
NOT	~	Flip all bits
Left shift	<<	Multiply by 2ᵏ
Right shift	>>	Divide by 2ᵏ, sign-extends
Unsigned right shift	>>>	Divide by 2ᵏ, zero-fills (Java specific)

The identities to memorize

Goal	Trick
Check if bit i is set	(n >> i) & 1 or n & (1 << i)
Set bit i	n | (1 << i)
Clear bit i	n & ~(1 << i)
Toggle bit i	n ^ (1 << i)
Check if n is a power of 2	n > 0 && (n & (n - 1)) == 0
Drop lowest set bit	n & (n - 1)
Isolate lowest set bit	n & -n
Count set bits	Integer.bitCount(n)
x XOR x = 0	useful for finding the unique element
x XOR 0 = x	useful as accumulator initial value

The classic XOR trick — single number

Given an array where every element appears twice except one, find the lone element. XOR everything: pairs cancel out (x ⊕ x = 0), the single survivor remains.

int singleNumber(int[] nums) {
    int x = 0;
    for (int n : nums) x ^= n;
    return x;
}

O(n) time, O(1) space. Beats the HashMap approach on both axes.

Counting set bits (Brian Kernighan's algorithm)

int popcount(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);   // drops the lowest set bit
        count++;
    }
    return count;
}

Runs in O(k) where k = number of set bits, not O(log n) as in the naive loop-each-bit approach.

Bitmask DP — when subsets fit in an int

If n ≤ 20, you can represent any subset of n items as an integer (each bit = is item i included). State dp[mask] over all 2ⁿ subsets is feasible. This unlocks problems like Traveling Salesman (n ≤ 20), partition to k equal subsets, and various scheduling problems.

// Iterate all subsets of size 5 from items 0..n-1.
for (int mask = 0; mask < (1 << n); mask++) {
    if (Integer.bitCount(mask) != 5) continue;
    // process this 5-element subset
    for (int i = 0; i < n; i++) {
        if ((mask >> i & 1) == 1) {
            // item i is included
        }
    }
}

---

SECTION 20Pattern Recognition Cheat Sheet

This is the section to come back to. The other 19 sections build the vocabulary. This one is the dictionary that maps problem statements to the right tool.

The skill of "what should I apply here?" is built in two layers: first, the surface signals (keywords in the problem, shape of input, what the output is); second, the structural signals (constraints, time/space requirements, properties of the data). The tables below capture both.

Layer 1 — Signals from problem keywords

If the problem says…	First thing to consider
"sorted array", "find target"	Binary search
"pair / triplet sums to X"	Hash map (unsorted) or two pointers (sorted)
"contiguous subarray / substring"	Sliding window or prefix sum
"longest / shortest substring with property"	Variable sliding window
"every window of size k"	Fixed sliding window (+ monotonic deque if max/min)
"next greater / smaller element"	Monotonic stack
"matching parentheses / brackets"	Stack
"reverse a list / part of a list"	Linked list reverse template
"find duplicates / first non-repeating"	Hash set / map
"group anagrams / by some property"	Hash map of lists
"top K / Kth largest / most frequent"	Heap of size K, or quickselect
"merge K sorted lists / streams"	Min-heap k-way merge
"running median"	Two heaps
"prefix search / autocomplete"	Trie
"are X and Y connected?" / "count components"	Union-Find or DFS/BFS
"shortest path, unweighted"	BFS
"shortest path, weighted (positive)"	Dijkstra
"course prerequisites / build order"	Topological sort
"all permutations / combinations / subsets"	Backtracking
"number of ways to..." / "count ways"	DP
"max / min XYZ" with choices at each step	DP (or greedy if obviously safe)
"edit distance" / "longest common subseq"	2D string DP
"intervals: merge / overlap / minimum rooms"	Sort by start or end, sweep
"every element twice except one"	XOR
"find peak / minimum in rotated array"	Modified binary search
"min X such that Y is feasible"	Binary search on the answer
"detect cycle in linked list"	Slow/fast pointers (Floyd's)
"number of islands" / "regions in grid"	DFS / BFS on grid
"shortest grid path", "rotten oranges"	(Multi-source) BFS on grid

Layer 2 — Signals from constraints

When you read the constraints, immediately translate them into a complexity budget:

If n is bounded by…	Expected complexity	Typical approach
n ≤ 10	O(n!)	Brute force permutations, backtracking with little pruning
n ≤ 20	O(2ⁿ)	Bitmask DP, subset enumeration
n ≤ 100	O(n³) or O(n⁴)	Interval DP, Floyd-Warshall, 3D DP
n ≤ 1,000	O(n²)	2D DP, LCS, LIS naive, two nested loops
n ≤ 10⁴ – 10⁵	O(n log n)	Sort, heap, BST, binary search per element
n ≤ 10⁶ – 10⁷	O(n)	Hash map, two pointers, sliding window, single scan
n ≤ 10⁹+	O(log n) or O(1)	Math, binary search on answer, formula

Layer 3 — Decision flow for unfamiliar problems

When you don't immediately spot a pattern, walk this flow:

Layer 4 — The "where am I redoing work?" lens

The single most useful question to ask when your brute force is too slow:

Layer 5 — Common problem archetypes & their patterns

Problem archetype	Most-used patterns
Sum / sum-target problems (2Sum, 3Sum, subarray sum equals K)	Hash map + complement, two pointers on sorted, prefix sum + hash
Substring problems (longest unique, longest k-distinct, anagram check)	Sliding window (variable), frequency map
Interval problems (merge, insert, meeting rooms)	Sort by start (or end), then sweep with greedy
Linked list problems	Dummy head, slow/fast pointers, reverse template
Tree problems	Recursive DFS returning info, level-order BFS
Tree path-sum / diameter	DFS returning height + side-effect on global answer
BST problems	Inorder traversal (sorted output), recursive split on root.val
Grid problems (islands, rotten oranges, surrounded regions)	DFS/BFS over neighbors, multi-source BFS
Graph reachability / components	DFS, BFS, or Union-Find
Graph ordering / scheduling	Topological sort (Kahn's BFS)
Shortest path	BFS (unweighted), Dijkstra (weighted positive), Bellman-Ford (negative)
"Min number of X to..." (jumps, coins, transformations)	BFS over state space, or DP
"Number of ways to..."	DP almost always
"Longest / shortest substring" with constraint	Sliding window
"Kth largest / smallest"	Heap of size K, or quickselect
"Search in 2D matrix"	Binary search treating matrix as 1D, or staircase search from corner
String matching	KMP (if asked), rolling hash (Rabin-Karp), or built-in

Layer 6 — Approaching a problem step by step

This is the practical workflow for any new problem. Follow it religiously for the first 50 problems, then it becomes automatic:

1. Read the problem twice. First for the story, second to extract: input shape, output shape, examples.
2. Look at the constraints. Translate n ≤ X into a complexity budget. This eliminates approaches before you waste time on them.
3. State the brute force out loud. Even if it's O(n!), naming it gives you a baseline to beat. Many "hard" problems are easy brute force + one optimization.
4. Identify the pattern. Match against Layer 1 (keywords), Layer 5 (archetypes), or the decision flow.
5. Ask "where am I redoing work?" Apply the right data structure to eliminate the duplication.
6. Sketch the algorithm in plain English (or pseudocode) before writing Java.
7. Trace through the smallest non-trivial example by hand. Catches off-by-ones before you write a loop.
8. Write the code. Use templates: BFS template, DFS template, sliding window template, binary search template.
9. Walk through edge cases. Empty input, single element, all duplicates, max value, negative numbers, n=1.
10. State the final complexity. Both time and space.

Final advice: practice with a recognition mindset

---

End of reference. Read the section relevant to today's practice problem. Then attempt the problem. Then come back and check what you missed.