DSA in Java — Concept Notes

1. How to Approach a DSA Problem

The eight-step framework

Budget roughly: 5 minutes for steps 1–2, 5–10 minutes for 3–5, 15–20 minutes to code, 5 minutes to dry-run and test. If you jump straight to step 6, you will often solve the wrong problem.

Step 1 — Clarify

Problems are left vague on purpose. The interviewer wants to see you ask. Good questions:

• Input: What type and size? Can it be empty? Can values be negative, zero, duplicate? Is the array sorted?
• Output: Return indices or values? Any valid answer or all of them? What if there is no answer — return -1, empty list, or throw?
• Constraints: How big is n? (This tells you the target complexity — see section 2.) Does it fit in memory? Can I modify the input?

Step 2 — Examples and edge cases

Write a normal example and then attack the corners. An edge case is an input at the boundary of what is allowed, where code usually breaks:

Step 3 — Brute force first

Say the most obvious correct solution out loud, with its complexity: "The simplest thing is to try every pair, which is O(n²)." This proves you understand the problem, gives you a fallback answer, and gives you something to improve. You usually do not code it — ask "should I code this or look for something faster?"

Steps 4–5 — Find the bottleneck, then optimise

Look at the brute force and ask: what work am I repeating? Most optimisations are one of these moves:

A very common trade: spend memory to save time. A HashMap costs O(n) extra space but turns an O(n) search into an O(1) lookup.

Step 6 — Code

• Use clear names: left, right, seen, maxLen — not a, b, x.
• Pull repeated logic into a helper (isValid(r, c), swap(arr, i, j)).
• Handle the edge cases you listed at the top of the method.
• If you are unsure of a library method, say so and pick a sensible name: "I'll assume a helper that returns the neighbours."

Steps 7–8 — Dry-run and test

Do not say "I think it works." Pick a small example and trace the variables line by line, out loud. Then run through your edge cases. Finding your own bug is a positive signal — it shows you test your work. Finish by restating the time and space complexity.

How to talk while coding

• Narrate intent, not syntax. Say "now I shrink the window from the left until it's valid again," not "i plus plus."
• Announce trade-offs. "I'll use extra O(n) space for the map to get linear time."
• Check in at decision points. "Does that approach sound good before I code it?"
• It is fine to go quiet for 20–30 seconds to think — just say "let me think about this for a moment" first.

What to do when you are stuck

1. Go back to a tiny example and solve it by hand. Watch what your brain does — that is often the algorithm.
2. Ask "what if the input were sorted?" or "what if I had a HashMap of everything?"
3. Walk the pattern table above: two pointers? sliding window? BFS? heap? DP?
4. Solve a simpler version first (1D before 2D, no duplicates before duplicates, k = 1 before general k).
5. Say what you are thinking. Interviewers give hints to candidates who are visibly reasoning, not to silent ones.
6. If time runs low, code the brute force cleanly. A working O(n²) beats a broken O(n).

Worked example — Two Sum, end to end

Problem: given an array nums and a target, return the indices of the two numbers that add up to target.

1. Clarify. "Is there always exactly one answer? Can I use the same element twice? Can values be negative? Is it sorted?" Assume: exactly one answer, not the same index twice, negatives allowed, not sorted.

2. Examples. [2,7,11,15], 9 → [0,1]. [3,2,4], 6 → [1,2] (note: not [0,0] — cannot reuse index 0). [3,3], 6 → [0,1] (duplicates).

3. Brute force. Try every pair (i, j) with j > i. That is about n²/2 pairs, so O(n²) time and O(1) space.

// Brute force: try every pair. O(n^2) time, O(1) space.
static int[] twoSumBrute(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) return new int[]{i, j};
        }
    }
    return new int[]{-1, -1};              // no pair found
}

4. Bottleneck. For each nums[i], the inner loop is really asking one question: "does the number target - nums[i] exist somewhere I've already been?" That is a lookup, and we are doing it with a slow linear scan.

5. Optimise. Remember every number we have passed in a HashMap from value to index. Then the lookup is O(1) on average, and one pass is enough.

import java.util.*;

class Solution {
    // One pass with a HashMap. O(n) time, O(n) space.
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();   // value -> index
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];                 // the partner we want
            if (seen.containsKey(need)) {
                return new int[]{seen.get(need), i};
            }
            seen.put(nums[i], i);                        // store AFTER checking
        }
        return new int[]{-1, -1};
    }
}

Why "store after checking"? If we stored first, then for [3,2,4], target 6 the element 3 would find itself (6 - 3 = 3) and return [0,0]. Checking first means we only ever pair with an earlier index.

7. Dry-run on nums = [2,7,11,15], target = 9:

8. Test. Running the code gives: [2,7,11,15], 9 → [0, 1]; [3,2,4], 6 → [1, 2]; [3,3], 6 → [0, 1] (the second 3 finds the first); [1,2], 7 → [-1, -1] (no answer).

Complexity: O(n) time — one pass, each map operation O(1) on average. O(n) space — the map may hold every element.

2. Big-O & Complexity

What Big-O really means

Formally, f(n) = O(g(n)) means that for large enough n, f(n) is at most some constant times g(n). In practice this gives two rules:

• Drop constants. 3n + 5 steps is O(n). Two separate passes over the array is still O(n).
• Keep only the biggest term. n² + 100n + 7 is O(n²), because when n is a million, the n² part dwarfs everything else.

Related words you may hear: Big-Omega (Ω) is a lower bound ("at least this much"), Big-Theta (Θ) is a tight bound (both). In interviews, people say "Big-O" and mean the tight worst-case bound.

How to count — the patterns

// O(n): one loop over the input
static int sum(int[] a) {
    int total = 0;
    for (int x : a) total += x;          // runs n times
    return total;
}

// O(n^2): a loop inside a loop, both over n
static int countPairs(int[] a) {
    int count = 0;
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)   // n-1, n-2, ... 1 -> n(n-1)/2
            count++;
    return count;
}

// O(log n): the problem halves every step
static int halvings(int n) {
    int steps = 0;
    while (n > 1) {
        n /= 2;                           // n, n/2, n/4, ... 1
        steps++;
    }
    return steps;
}

// O(n log n): n outer iterations, each doing log n work
static int nLogN(int n) {
    int ops = 0;
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j *= 2)    // doubles -> log n times
            ops++;
    return ops;
}

// Two SEPARATE loops over different inputs: O(n + m), not O(n * m)
static int twoLoops(int[] a, int[] b) {
    int ops = 0;
    for (int x : a) ops++;
    for (int y : b) ops++;
    return ops;
}

Running these on an 8-element array: countPairs does 28 steps (= 8·7/2), nLogN(8) does 24 (= 8·3), and halvings(1_000_000) takes only 19 steps. That last number is why O(log n) feels almost free.

• Sequential blocks add: loop A then loop B is O(A + B).
• Nested blocks multiply: loop A containing loop B is O(A × B).
• Halving or doubling the loop variable gives a log.
• Different inputs get different letters: looping over a string of length n and a list of length m is O(n + m) or O(n·m) — never just "O(n)".
• Hidden loops count: list.contains(x), s.substring(...), String + in a loop, Arrays.sort all cost more than O(1).

Why log n is so small — binary search

// Binary search: O(log n) time, O(1) space
static int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;     // avoids (lo + hi) overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Counting recursion

For recursive code, ask two questions: how many calls happen in total, and how much work does each call do outside its recursive calls? Multiply them.

• One call per level, n levels, O(1) work each (factorial) → O(n).
• One call on half the input, O(1) work each (binary search) → O(log n).
• Two calls on n - 1 (naive Fibonacci) → the calls double each level → O(2ⁿ).
• Two calls on half, O(n) merge work (merge sort) → log n levels, O(n) per level → O(n log n).

A useful rule: a recursion with b branches and depth d makes about b^d calls.

Best, average and worst case

The same algorithm can take very different time depending on the input:

When nobody says which, give the worst case, and mention the average if it is different (for hashing and quicksort, always mention it).

Amortised complexity — ArrayList growth

Amortised means "averaged over a long sequence of operations." Some single operations are expensive, but they are rare enough that the average cost per operation stays small.

An ArrayList is backed by a fixed-size array. When it is full, add allocates a new array about 1.5 times bigger and copies everything over — an O(n) step. But after that, the next many adds are O(1) again. Because the capacity grows by a multiplied amount, the total copying over n adds is a geometric series that adds up to a constant times n.

Simulating 1,000,000 adds with Java's 1.5x growth rule (starting at capacity 10) gives 2,430,972 element copies in total — about 2.4 copies per add. A constant, so add is amortised O(1).

Space complexity (and the hidden stack)

Space complexity counts the extra memory your algorithm uses, not the input itself (say so if you are unsure — some interviewers count the input). Watch for:

• New arrays, lists, maps, sets: O(size).
• Copies: substring, toCharArray, new ArrayList<>(other) are all O(length).
• The recursion stack: every active call holds a stack frame. A recursion that goes n levels deep uses O(n) space even if it creates no objects.

// Recursion that sums an array: O(n) time AND O(n) space (n stack frames)
static int sumRec(int[] a, int i) {
    if (i == a.length) return 0;
    return a[i] + sumRec(a, i + 1);
}

The iterative sum above does the same job in O(1) space. Recursive DFS on a tree uses O(h) space where h is the height: O(log n) for a balanced tree but O(n) for a skewed one.

Common complexity classes

Input size → which complexity fits

A typical judge (and a typical interviewer's mental model) allows about 10⁸ simple operations per second. So the constraint on n tells you the complexity they expect — a huge hint that is often ignored:

The Master Theorem in easy words

Many divide-and-conquer algorithms have a running time like

T(n) = a · T(n / b) + f(n)
  a    = how many sub-problems each call makes
  n/b  = how big each sub-problem is
  f(n) = the work done in this call itself (splitting + combining)

Picture the recursion as a tree. The top level does f(n) work. The bottom level has a huge number of tiny leaves. The Master Theorem simply asks: which part of the tree does most of the work? Compare f(n) with n^log_b(a) (the number of leaves):

3. Recursion & the Call Stack

The two rules

// factorial: n! = n * (n-1) * ... * 1.  O(n) time, O(n) stack space
static long factorial(int n) {
    if (n <= 1) return 1;              // base case: answer directly
    return n * factorial(n - 1);       // recursive case: smaller input
}
// factorial(5)  = 120
// factorial(20) = 2432902008176640000  (factorial(21) overflows long)

1. Every path must reach a base case. Forget it, or never shrink the input, and you recurse forever.
2. Each call must move toward the base case (n - 1, n / 2, index + 1, a smaller subtree).

Trust the recursion (the "leap of faith"): when writing factorial(n), assume factorial(n - 1) already works and only ask "how do I use it to build my answer?" Do not try to trace every level in your head while writing — trace afterwards to check.

What the call stack actually does

The JVM keeps a call stack for each thread. Every time a method is called, a new stack frame is pushed on top. The frame holds that call's parameters, local variables, and where to return to. When the method returns, its frame is popped and the caller continues exactly where it paused.

So recursion is not magic: factorial(3) pauses in the middle of 3 * ?, waiting for factorial(2) to finish, which pauses waiting for factorial(1).

Recursion trees — naive Fibonacci

When a method calls itself more than once, draw a recursion tree: each node is one call, its children are the calls it makes.

// naive fib: O(2^n) time, O(n) stack space
static long fib(int n) {
    if (n <= 1) return n;                // fib(0) = 0, fib(1) = 1
    return fib(n - 1) + fib(n - 2);
}

Each call branches into 2, and the tree is up to n levels deep, so there are up to about 2ⁿ calls: O(2ⁿ) time. Counting for real: fib(10) makes 177 calls, and fib(30) makes 2,692,537. But the space is only O(n): at any moment only one root-to-leaf path is on the stack, and the deepest path has n frames.

Memoisation preview

The tree above repeats the same subproblems. Memoisation means caching each answer the first time you compute it and returning the cached value next time. Each fib(k) is then computed once:

// memoised fib: O(n) time, O(n) space (memo array + stack)
static long fibMemo(int n, long[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];            // already solved: reuse
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}
// fibMemo(50, new long[51]) = 12586269025, instantly.
// The naive version would need billions of calls.

This is the doorway to dynamic programming: "recursion + a cache" (top-down) or "fill a table in a loop" (bottom-up). It gets its own part later.

Head vs tail recursion

Where you do the work relative to the recursive call changes the order of results:

// Head recursion: recurse FIRST, work on the way back up
static void printHead(int n) {
    if (n == 0) return;
    printHead(n - 1);
    System.out.print(n + " ");            // prints: 1 2 3
}

// Tail recursion: work FIRST, the recursive call is the very last thing
static void printTail(int n) {
    if (n == 0) return;
    System.out.print(n + " ");            // prints: 3 2 1
    printTail(n - 1);
}

A tail call means nothing is left to do after the call returns, so in theory the frame could be reused. Some languages (Scheme, Scala with @tailrec, Kotlin tailrec) do this tail-call optimisation. Java does not. A tail-recursive method in Java still uses O(n) stack.

StackOverflowError and converting to iteration

The stack has a fixed size (roughly 512 KB to 1 MB per thread by default, adjustable with -Xss). Recurse too deep and the JVM throws StackOverflowError. On a default JVM, an empty infinite recursion died after about 67,000 frames in a quick test; real methods with more locals die sooner. So deep recursion on 10⁵–10⁶ elements (a long linked list, a skewed tree, DFS on a big grid) can crash.

// Tail-recursive sum with an accumulator -- still overflows in Java for n = 1,000,000
static long sumTail(int n, long acc) {
    if (n == 0) return acc;
    return sumTail(n - 1, acc + n);
}

// Same logic as a loop: O(n) time, O(1) space, cannot overflow the stack
static long sumIter(int n) {
    long acc = 0;
    while (n > 0) { acc += n; n--; }
    return acc;
}
// sumTail(100, 0) = 5050, sumIter(100) = 5050
// sumTail(1_000_000, 0) -> StackOverflowError
// sumIter(1_000_000)    -> 500000500000

How to convert recursion to iteration:

• Tail recursion → a plain loop. The parameters become loop variables (as above).
• General recursion (tree DFS, backtracking) → use your own explicit stack: Deque<Node> stack = new ArrayDeque<>(). Push the starting state, then loop: pop, process, push the children. Your stack lives on the heap, which is much bigger.
• Recursion with memo → a bottom-up DP table filled in a loop.

Classic examples

Fast power — compute xⁿ by squaring half the answer instead of multiplying n times:

// x^n in O(log n) time, O(log n) stack
static double myPow(double x, long n) {
    if (n < 0) return 1 / myPow(x, -n);   // long n: -Integer.MIN_VALUE would overflow an int
    if (n == 0) return 1;                  // base case
    double half = myPow(x, n / 2);         // solve half the problem ONCE
    return (n % 2 == 0) ? half * half : half * half * x;
}
// myPow(2, 10) = 1024.0, myPow(2, -2) = 0.25

The key is calling myPow(x, n / 2) once and storing it. Writing myPow(x, n/2) * myPow(x, n/2) makes two calls per level and falls back to O(n).

Reverse a string — swap the ends, then recurse on the middle:

// O(n) time, O(n) stack (n/2 frames)
static void reverse(char[] s, int left, int right) {
    if (left >= right) return;             // base case: 0 or 1 chars left
    char tmp = s[left]; s[left] = s[right]; s[right] = tmp;
    reverse(s, left + 1, right - 1);
}
// "hello" -> "olleh"

All subsets (preview of backtracking) — for each element, make two choices: take it or skip it:

// O(n * 2^n) time (2^n subsets, each copied in O(n)), O(n) stack
static void subsets(int[] nums, int i, List<Integer> current, List<List<Integer>> out) {
    if (i == nums.length) {                // decided for every element
        out.add(new ArrayList<>(current)); // copy! current keeps changing
        return;
    }
    current.add(nums[i]);                  // choice 1: take nums[i]
    subsets(nums, i + 1, current, out);
    current.remove(current.size() - 1);    // undo the choice (backtrack)
    subsets(nums, i + 1, current, out);    // choice 2: skip nums[i]
}
// [1,2,3] -> [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

4. Java Toolkit for DSA

Arrays

int[] a = {5, 3, 9, 1, 7};
Arrays.sort(a);                                  // [1, 3, 5, 7, 9]  O(n log n)
int[] dp = new int[5];
Arrays.fill(dp, -1);                             // [-1, -1, -1, -1, -1]
int[] part = Arrays.copyOfRange(a, 1, 4);        // [3, 5, 7]  (end index is EXCLUSIVE)
List<String> names = Arrays.asList("bob", "amy", "cat");  // fixed-size list view
int[][] grid = new int[3][4];                    // 3 rows, 4 cols, all 0
System.out.println(Arrays.toString(a));          // printing needs toString / deepToString

// Descending order needs boxed Integer[], not int[]
Integer[] boxed = {5, 3, 9, 1};
Arrays.sort(boxed, Collections.reverseOrder());  // [9, 5, 3, 1]

// Sort 2D array (e.g. intervals) by first element
int[][] intervals = {{5, 6}, {1, 3}, {2, 4}};
Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));  // [[1, 3], [2, 4], [5, 6]]

int total = Arrays.stream(a).sum();              // 25
int max = Arrays.stream(a).max().getAsInt();     // 9

• Arrays.sort(int[]) uses dual-pivot quicksort (O(n log n) average, not stable — fine for primitives). Arrays.sort(Object[]) uses TimSort, which is stable (equal elements keep their order) and guaranteed O(n log n).
• Arrays.asList returns a fixed-size view: add/remove throw UnsupportedOperationException. Wrap it: new ArrayList<>(Arrays.asList(...)). And Arrays.asList(intArray) gives a list with one element (the array itself) — it does not box.
• List.of(...) is fully immutable and rejects null.

String vs StringBuilder

A Java String is immutable: it can never change. s += "x" builds a brand-new string and copies all the old characters. In a loop that is O(n²) total. StringBuilder is a growable char buffer: append is amortised O(1).

String s = "hello";
s.charAt(1);          // 'e'   O(1)
s.length();           // 5     (method for String; field .length for arrays; .size() for collections)
s.substring(1, 3);    // "el"  O(k) -- makes a copy, end exclusive
char[] cs = s.toCharArray();
Arrays.sort(cs);
new String(cs);       // "ehllo" -- sorted letters (anagram key)
String.valueOf(42);   // "42"
s.equals("hello");    // compare CONTENT with equals, never ==

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 3; i++) sb.append(i).append(',');
sb.setLength(sb.length() - 1);   // drop last comma -> "0,1,2"
sb.reverse();                    // "2,1,0"  (reverses in place)
sb.insert(0, 'x'); sb.deleteCharAt(0); sb.setCharAt(0, 'y');
String result = sb.toString();

new String("hi") == new String("hi") is false (two different objects) while .equals is true. Always use equals for strings.

char arithmetic

A char is really a small number (its Unicode code). Subtracting 'a' turns a lowercase letter into an index 0–25 — the standard way to count letters with an int[26] instead of a map.

'd' - 'a'            // 3       letter -> index
(char) ('a' + 3)     // 'd'     index -> letter (cast back!)
'7' - '0'            // 7       digit char -> int
Character.isDigit('7'); Character.isLetter('x'); Character.isLetterOrDigit(c);
Character.toUpperCase('q');     // 'Q'

int[] freq = new int[26];
for (char ch : "banana".toCharArray()) freq[ch - 'a']++;
// freq[0] ('a') = 3, freq['n' - 'a'] = 2

ArrayList

List<Integer> list = new ArrayList<>(List.of(10, 20, 30));
list.add(40);                      // append, amortised O(1)
list.add(0, 5);                    // insert at index: O(n) -- shifts everything
list.get(2); list.set(2, 99);      // O(1)
list.remove(Integer.valueOf(20));  // remove by VALUE, O(n)
list.remove(0);                    // remove by INDEX, O(n)
list.contains(30);                 // O(n) linear scan!

Stack and queue: use ArrayDeque

ArrayDeque (a resizable circular array) is the right tool for both a stack and a queue. It is faster than LinkedList (no node object per element, better cache use) and does not allow null.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.push(3);
stack.peek();   // 3
stack.pop();    // 3  -> stack is [2, 1]

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2); queue.offer(3);
queue.peek();   // 1
queue.poll();   // 1  -> queue is [2, 3]

// Deque (both ends): offerFirst/offerLast, pollFirst/pollLast, peekFirst/peekLast
// Empty behaviour: pop()/remove() THROW; poll()/peek() return null

Why not java.util.Stack? It is an old class that extends Vector: every method is synchronized (slow, pointless for one thread), and because it is a Vector you can insert into the middle, which breaks the stack idea. Java's own docs recommend Deque instead. Mentioning this is a small but good signal.

When is LinkedList useful? Rarely in interviews. It allows null and implements both List and Deque, but get(i) is O(n). Use ArrayDeque for queues and ArrayList for lists.

HashMap and HashSet

// Counting: three equivalent styles
Map<String, Integer> count = new HashMap<>();
for (String w : "a b a c b a".split(" ")) count.merge(w, 1, Integer::sum);   // {a=3, b=2, c=1}
map.put(k, map.getOrDefault(k, 0) + 1);                   // classic

// Grouping: create the list the first time a key is seen
Map<String, List<String>> groups = new HashMap<>();
for (String w : List.of("eat", "tea", "tan", "ate")) {
    char[] k = w.toCharArray(); Arrays.sort(k);
    groups.computeIfAbsent(new String(k), key -> new ArrayList<>()).add(w);
}
// {aet=[eat, tea, ate], ant=[tan]}

// Iterate keys and values together
for (Map.Entry<String, Integer> e : count.entrySet()) {
    System.out.println(e.getKey() + ":" + e.getValue());
}
// also: map.keySet(), map.values(), map.containsKey(k), map.remove(k), map.putIfAbsent(k, v)

Set<Integer> set = new HashSet<>();
set.add(5);        // true  (was new)
set.add(5);        // false (already there) -- handy for "seen before?" in one call
set.contains(5);   // true

• HashMap iteration order is not defined. Use LinkedHashMap for insertion order (also the basis of an LRU cache), TreeMap for sorted order.
• Keys must have correct equals and hashCode. int[] does not — two arrays with the same contents are different keys. Use a String key, a List<Integer>, a record, or encode a pair as (long) r * cols + c.

TreeMap and TreeSet — sorted, with "nearest" queries

A red-black tree (a self-balancing binary search tree) under the hood: every operation is O(log n) and keys stay sorted. Use them when you need "the closest key to x" or ordered iteration.

TreeMap<Integer, String> tm = new TreeMap<>(Map.of(10, "a", 20, "b", 30, "c"));
tm.floorKey(25);     // 20    largest key <= 25
tm.ceilingKey(25);   // 30    smallest key >= 25
tm.lowerKey(10);     // null  largest key strictly < 10
tm.higherKey(30);    // null  smallest key strictly > 30
tm.firstKey(); tm.lastKey();   // 10, 30
tm.headMap(20);      // {10=a}          keys < 20
tm.tailMap(20);      // {20=b, 30=c}    keys >= 20
// also: floorEntry, ceilingEntry, pollFirstEntry, descendingMap

TreeSet<Integer> ts = new TreeSet<>(List.of(4, 1, 9, 6));   // [1, 4, 6, 9]
ts.floor(5);         // 4
ts.ceiling(5);       // 6
ts.pollFirst();      // 1 (removes it)

Always check for null — the "nearest" methods return null when nothing qualifies, and unboxing that into an int throws NullPointerException.

PriorityQueue — a heap

A binary heap: peek gives the smallest element in O(1); offer and poll are O(log n). By default it is a min-heap.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int v : new int[]{5, 1, 8, 3}) { minHeap.offer(v); maxHeap.offer(v); }
minHeap.poll();   // 1
maxHeap.poll();   // 8

// Heap of arrays: {node, distance}, ordered by distance (Dijkstra style)
PriorityQueue<int[]> pq = new PriorityQueue<>((p, q) -> Integer.compare(p[1], q[1]));
pq.offer(new int[]{0, 7}); pq.offer(new int[]{1, 2}); pq.offer(new int[]{2, 5});
pq.poll();        // [1, 2] -- smallest distance first

• Iterating or printing a PriorityQueue does not give sorted order — only poll does.
• remove(Object) and contains are O(n).
• Building from a collection, new PriorityQueue<>(list), is O(n) (heapify), faster than n offers.

Collections helpers and Comparator chains

List<Integer> nums = new ArrayList<>(List.of(3, 1, 2));
Collections.sort(nums);        // [1, 2, 3]
Collections.reverse(nums);     // [3, 2, 1]
Collections.max(nums);         // 3
Collections.min(nums);         // 1
Collections.frequency(List.of(1, 1, 2), 1);   // 2
Collections.swap(nums, 0, 2);  // also: Collections.nCopies, Collections.emptyList

record Person(String name, int age) {}
List<Person> people = new ArrayList<>(List.of(
    new Person("Zoe", 30), new Person("Adam", 25), new Person("Bob", 30)));
// age descending, then name ascending
people.sort(Comparator.comparingInt(Person::age).reversed()
                      .thenComparing(Person::name));
// [Bob 30, Zoe 30, Adam 25]

List<String> words = new ArrayList<>(List.of("pear", "fig", "apple", "kiwi"));
// shortest first; ties broken by reverse alphabetical
words.sort(Comparator.comparing(String::length)
                     .thenComparing(Comparator.reverseOrder()));
// [fig, pear, kiwi, apple]

Integer overflow

An int is 32 bits: range about ±2.1 billion (Integer.MAX_VALUE = 2147483647). Going past it silently wraps around to negative — no error.

int big = Integer.MAX_VALUE;
big + 1;                  // -2147483648   wrapped around!
(long) big + 1;           // 2147483648    cast BEFORE the math
int m = 100_000;
m * m;                    // 1410065408    wrong (true answer is 10^10)
(long) m * m;             // 10000000000   right
Math.addExact(big, 1);    // throws ArithmeticException("integer overflow")
int mid = lo + (hi - lo) / 2;   // safe midpoint; (lo + hi) / 2 can overflow

Use long for sums of many values, products, and anything counted "modulo 10⁹ + 7" (multiply as long, then take %). (long) (m * m) is still wrong — the overflow already happened inside the brackets.

The Integer caching trap

Integer p1 = 127, p2 = 127, q1 = 128, q2 = 128;
p1 == p2;          // true   -- same cached object
q1 == q2;          // false  -- two different objects!
q1.equals(q2);     // true

Map<Character, Integer> m1 = ..., m2 = ...;   // both map 'a' -> 1000
m1.get('a') == m2.get('a');       // false  -- compares object identity
m1.get('a').equals(m2.get('a'));  // true

Java caches Integer objects for values −128 to 127, so == happens to work for small numbers in your tests and then fails on large ones. Whenever values come out of a collection, compare with .equals or unbox first (int x = map.get(k);). This bug is famous in "Minimum Window Substring"-style problems that compare two count maps.

int vs Integer in collections

• Collections hold objects only, so List<int> is illegal; use List<Integer>. Java autoboxes for you, but each Integer is an object (≈16 bytes vs 4) — an int[] is much faster and smaller when the size is known.
• Unboxing a null throws NullPointerException: int c = map.get(missingKey); crashes. Use getOrDefault.
• List<Integer>.remove(1) removes index 1; remove(Integer.valueOf(1)) removes the value 1. From [1, 2, 3]: remove(1) gives [1, 3], then remove(Integer.valueOf(1)) gives [3].

Fast input (for online judges)

Scanner is convenient but slow for 10⁵+ numbers. Use BufferedReader with StringTokenizer:

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
StringTokenizer st = new StringTokenizer(br.readLine());
long total = 0;
for (int i = 0; i < n; i++) total += Integer.parseInt(st.nextToken());
// For lots of output, collect in a StringBuilder and print once
// (or use PrintWriter) instead of calling System.out.println in a loop.

Operation cost cheat sheet

5. Bit Manipulation

Binary basics

In binary each position is a power of 2, counted from the right starting at position 0. So 1101 = 1·8 + 1·4 + 0·2 + 1·1 = 13.

Integer.toBinaryString(13);      // "1101"
Integer.parseInt("1101", 2);     // 13
int n = 0b1010;                  // binary literal = 10
// bit i has value 1 << i:  1 << 0 = 1, 1 << 3 = 8, 1 << 10 = 1024

Two's complement — how negatives are stored

Java's int is 32 bits and signed. The leftmost bit is the sign bit: 0 for non-negative, 1 for negative. Negatives use two's complement: to get -x, flip every bit of x and add 1. So -x == ~x + 1.

Why this design? Addition works the same for positive and negative numbers, and there is only one zero. It also explains ~5 == -6, which we confirmed by running it.

The operators

• Shift amounts are taken mod 32 for int: 1 << 32 is 1, not 0. And 1 << 31 is -2147483648 (the sign bit). Use 1L << k for 64-bit masks (1L << 32 = 4294967296).
• Precedence trap: &, ^, | bind weaker than ==. n & 1 == 0 does not compile in Java (it parses as n & (1 == 0)). Always write (n & 1) == 0.
• Odd/even: (n & 1) is 1 for odd, 0 for even — it works for negatives too, while -7 % 2 is -1, not 1.

Single-bit tricks

// i = bit position, 0 = rightmost.  All O(1).
static boolean isSet(int n, int i) { return (n & (1 << i)) != 0; }  // check
static int setBit(int n, int i)    { return n | (1 << i); }          // turn on
static int clearBit(int n, int i)  { return n & ~(1 << i); }         // turn off
static int toggleBit(int n, int i) { return n ^ (1 << i); }          // flip

// n = 0b1010 (10)
isSet(10, 1);      // true
isSet(10, 2);      // false
setBit(10, 0);     // 11  (1011)
clearBit(10, 3);   // 2   (0010)
toggleBit(10, 1);  // 8   (1000)

Pattern: build a mask with a single 1 at position i (1 << i), then AND to test, OR to set, AND-with-NOT to clear, XOR to flip.

The two most useful tricks: n & (n - 1) and n & -n

Subtracting 1 from a number flips its lowest 1 bit to 0 and all the 0s below it to 1. So n & (n - 1) wipes out exactly the lowest set bit. And because -n = ~n + 1, n & -n keeps only the lowest set bit.

// Power of two: exactly one bit set. O(1)
static boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
// 64 -> true, 96 -> false, 0 -> false, Integer.MIN_VALUE -> false (n > 0 matters!)

static int lowestSetBit(int n) { return n & -n; }    // 12 -> 4

// Brian Kernighan's bit count: loops once per SET bit. O(number of 1s), at most 32
static int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;        // drop the lowest set bit
        count++;
    }
    return count;
}
// countBits(13) = 3, countBits(-1) = 32  (while n != 0, so negatives work)
// Built-in: Integer.bitCount(13) = 3

Other handy built-ins: Integer.numberOfTrailingZeros(8) = 3, Integer.numberOfLeadingZeros(8) = 28, Integer.highestOneBit(100) = 64, Integer.reverse(x), and Long versions of each. Say you would use the built-in in production, and write the loop if asked.

XOR tricks

XOR has three properties that power a surprising number of problems:

• a ^ a = 0 — a number cancels itself.
• a ^ 0 = a — zero changes nothing.
• Order does not matter (commutative and associative) — so you can XOR a whole list in any order and every pair cancels.

Single Number — every value appears twice except one. Find it in O(1) space:

// O(n) time, O(1) space
static int singleNumber(int[] nums) {
    int x = 0;
    for (int v : nums) x ^= v;   // pairs cancel: a ^ a = 0
    return x;
}
// [4, 1, 2, 1, 2] -> 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4

Missing Number — nums holds n distinct values from 0..n with one missing. XOR every index and every value; everything present appears twice and cancels, leaving the missing one:

// O(n) time, O(1) space. (Sum formula n(n+1)/2 also works but can overflow for huge n.)
static int missingNumber(int[] nums) {
    int x = nums.length;              // include n itself
    for (int i = 0; i < nums.length; i++) x ^= i ^ nums[i];
    return x;
}
// [3, 0, 1] -> 2

Swap without a temp variable — a party trick; know it, but prefer a temp in real code (it breaks if both refer to the same array slot, because x ^ x = 0):

int a = 3, b = 7;
a ^= b; b ^= a; a ^= b;     // now a = 7, b = 3

Single Number III — two values appear once, everything else twice. XOR of all gives a ^ b. Any 1 bit in that result is a position where a and b differ; split the numbers into two groups by that bit and XOR each group:

// O(n) time, O(1) space
static int[] singleNumberIII(int[] nums) {
    int xor = 0;
    for (int v : nums) xor ^= v;       // = a ^ b, non-zero because a != b
    int diff = xor & -xor;             // lowest bit where a and b differ
    int a = 0, b = 0;
    for (int v : nums) {
        if ((v & diff) == 0) a ^= v;   // group 1
        else b ^= v;                   // group 2
    }
    return new int[]{a, b};
}
// [1, 2, 1, 3, 2, 5] -> [5, 3]

Subsets via bitmask

For n items, each of the numbers 0 to 2ⁿ - 1 is a different pattern of n bits. Read bit i as "is item i in the subset?" and you get every subset exactly once — no recursion needed.

// O(n * 2^n) time, O(n * 2^n) for the output
static List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> out = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {          // 0 .. 2^n - 1
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) subset.add(nums[i]); // bit i on -> take nums[i]
        }
        out.add(subset);
    }
    return out;
}
// [1,2,3] -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

This is also why problems with n ≤ 20 hint at bitmasks: 2²⁰ is about a million states. The same idea powers bitmask DP, where the mask records "which items are already used" (for example, visiting-all-cities problems).

More classic problems

Counting Bits — return the number of 1s for every number 0..n. Reuse earlier answers: i >> 1 is i with its last bit dropped, so its count is already known; add back the last bit.

// O(n) time, O(n) output
static int[] countBitsUpTo(int n) {
    int[] ans = new int[n + 1];
    for (int i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1);
    return ans;
}
// n = 5 -> [0, 1, 1, 2, 1, 2]

Reverse Bits — mirror all 32 bits. Take the lowest bit of n, push it into the result from the right, repeat 32 times. Use >>> so negative inputs do not drag in sign bits:

// O(32) = O(1) time, O(1) space
static int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);  // append n's lowest bit to result
        n >>>= 1;                          // unsigned shift: no sign fill
    }
    return result;
}
// reverseBits(0b1011) = -805306368 = 11010000...0 (binary), same as Integer.reverse(0b1011)

Letter case — in ASCII, upper and lower case letters differ only in bit 5 (value 32, the space character): (char) ('A' | ' ') = 'a' and (char) ('a' & '_') = 'A'. Cute, but Character.toLowerCase is clearer in real code.

Summary table

6. Arrays & Strings

How an array sits in memory

When you write new int[7], Java asks for one contiguous (unbroken) block of memory big enough for 7 ints. An int is 4 bytes, so that is 28 bytes in a row. To find element i, the machine does one small sum: start address + i × element size. That single sum is why reading a[i] is O(1) no matter how big the array is.

A side benefit: when the CPU reads one element, it pulls the neighbouring bytes into its fast cache too. Walking an array from left to right is therefore much faster in practice than hopping around a linked list, even when both are O(n) on paper.

Static vs dynamic arrays

A plain Java array (int[], String[]) is static: its length is fixed when you create it. An ArrayList is a dynamic array: a static array hidden inside an object that swaps it for a bigger one when it fills up.

Why is add still called O(1)? Because the expensive copy happens rarely. With doubling, filling an array to n elements copies 1 + 2 + 4 + … + n/2 elements in total, which is less than n. Spread over n adds, that is less than one extra copy per add. This is called amortised O(1): one call can be slow, but the average over many calls is constant. Java's ArrayList grows by 1.5x instead of 2x (saves memory, still amortised O(1)); the first add on a new list allocates capacity 10.

Building a dynamic array from scratch

Interviewers sometimes ask "implement an ArrayList". The whole idea fits in a few lines:

class IntList {
    private int[] data = new int[4];
    private int size = 0;

    void add(int x) {                       // amortised O(1)
        if (size == data.length) {
            data = Arrays.copyOf(data, data.length * 2);  // O(n) copy, rare
        }
        data[size++] = x;
    }
    int get(int i) {                        // O(1)
        if (i < 0 || i >= size) throw new IndexOutOfBoundsException(i);
        return data[i];
    }
    void removeAt(int i) {                  // O(n): shift left
        if (i < 0 || i >= size) throw new IndexOutOfBoundsException(i);
        System.arraycopy(data, i + 1, data, i, size - i - 1);
        size--;
    }
    int size() { return size; }
}
// Adding 10, 20, ..., 90 makes capacity go 4 4 4 4 8 8 8 8 16

Operations and their cost

2D arrays

In Java, int[][] grid = new int[3][4] is really an array of 3 references, each pointing to its own int[4]. Rows are separate objects, so rows can even have different lengths (a jagged array). grid.length is the number of rows, grid[0].length the number of columns.

int[][] grid = new int[3][4];          // 3 rows, 4 columns, all 0
grid[1][2] = 7;                        // row 1, column 2
int[][] jagged = {{1}, {2, 3}, {4, 5, 6}};
System.out.println(Arrays.deepToString(jagged));   // [[1], [2, 3], [4, 5, 6]]

// The four neighbours of (r, c) — you will write this in every grid problem
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] d : dirs) {
    int nr = r + d[0], nc = c + d[1];
    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) { /* visit */ }
}

Loop row by row (for r … for c …), not column by column: each row is contiguous, so row order is cache-friendly.

Strings: immutable, so use StringBuilder

A Java String is immutable: no method ever changes it. Methods like concat, replace and toUpperCase return a new string. This makes strings safe to share and cache (and to use as HashMap keys), but it has a cost: building a string with += in a loop copies the whole string every time, which is O(n²) total.

String s = "hi";
s.concat(" there");          // result thrown away
System.out.println(s);       // hi
s = s.concat(" there");      // reassign to keep it
System.out.println(s);       // hi there

// Build strings in a loop with StringBuilder: append is amortised O(1)
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 5; i++) sb.append(i).append(',');
sb.setLength(sb.length() - 1);    // drop the last comma
System.out.println(sb.reverse()); // 4,3,2,1,0

// Compare contents with equals, never ==
String x = "java", y = "java", z = new String("java");
System.out.println((x == y) + " " + (x == z) + " " + x.equals(z));  // true false true

x == y is true only because identical string literals share one object in the string pool. new String(...) makes a separate object, so == (which compares references, i.e. "same object?") fails. Always use equals.

Counting characters with int[26]

When the input is only lowercase letters, a 26-slot array beats a HashMap: c - 'a' turns 'a' into 0, 'b' into 1, and so on. It is faster, uses fixed O(1) space, and is less code.

int[] freq = new int[26];
for (char c : "banana".toCharArray()) freq[c - 'a']++;
// freq[0] ('a') = 3, freq[1] ('b') = 1, freq['n' - 'a'] = 2

Use int[128] for any ASCII character, and a HashMap<Character, Integer> for full Unicode.

Common techniques (the toolbox)

Each of these gets its own section in the patterns part of these notes.

When to use what

• int[] — size known up front, primitives, maximum speed (no boxing: int stays a raw number instead of an Integer object).
• ArrayList — size grows, you mostly add at the end and read by index. The default list in Java.
• Not an array — if you insert/remove at the front a lot, use ArrayDeque; if you look things up by value, use a HashSet/HashMap.

Common pitfalls

• Off-by-one: the last index is length - 1. Loops are i < n, not i <= n.
• length vs length() vs size(): arrays use the field a.length, strings the method s.length(), collections list.size().
• Arrays.asList is fixed-size: calling add on it throws UnsupportedOperationException. Wrap it: new ArrayList<>(Arrays.asList(...)).
• list.remove(1) on a List<Integer> removes index 1, not the value 1. Use list.remove(Integer.valueOf(1)) for the value.
• Printing an array with System.out.println(a) prints something like [I@1b6d3586. Use Arrays.toString(a).
• Integer overflow when summing or multiplying: use long when values can exceed about 2.1 billion.

Problem: Rotate Array (right by k)

Given [1,2,3,4,5,6,7] and k = 3, produce [5,6,7,1,2,3,4] in place.

void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n;                         // k can be larger than n
    reverse(nums, 0, n - 1);        // 1 2 3 4 5 6 7 -> 7 6 5 4 3 2 1
    reverse(nums, 0, k - 1);        // -> 5 6 7 | 4 3 2 1
    reverse(nums, k, n - 1);        // -> 5 6 7 | 1 2 3 4
}
void reverse(int[] a, int i, int j) {
    while (i < j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
        i++; j--;
    }
}

Time O(n) (every element is swapped at most twice). Space O(1). Why it works: reversing the whole array puts the last k elements at the front but backwards; reversing each part separately fixes the order inside each part.

Problem: Product of Array Except Self

Return ans[i] = product of every element except nums[i], without division. [1,2,3,4] gives [24,12,8,6].

int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    ans[0] = 1;
    for (int i = 1; i < n; i++) {           // ans[i] = product of everything left of i
        ans[i] = ans[i - 1] * nums[i - 1];
    }
    int right = 1;                          // running product of everything right of i
    for (int i = n - 1; i >= 0; i--) {
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
}
// [1, 2, 3, 4]      -> [24, 12, 8, 6]
// [-1, 1, 0, -3, 3] -> [0, 0, 9, 0, 0]

Time O(n). Space O(1) extra (the output array does not count). Why it works: "everything except me" is exactly "product on my left" times "product on my right", and both can be built in one pass each.

Problem: Longest Common Prefix

String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String first = strs[0];
    for (int i = 0; i < first.length(); i++) {       // column by column
        char c = first.charAt(i);
        for (int j = 1; j < strs.length; j++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c) {
                return first.substring(0, i);
            }
        }
    }
    return first;
}
// ["flower","flow","flight"] -> "fl"
// ["dog","racecar","car"]    -> ""

Time O(S), where S is the total number of characters (in the worst case every character is checked once). Space O(1) apart from the answer. Why it works: scanning column by column stops at the very first position where any string disagrees or runs out, which is exactly where the shared prefix ends.

Problem: Valid Anagram

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) if (c != 0) return false;
    return true;
}
// ("anagram", "nagaram") -> true,  ("rat", "car") -> false

Time O(n). Space O(1) (26 counters, whatever n is). Why it works: two strings are anagrams exactly when every letter appears the same number of times, so adding for one string and subtracting for the other must leave all zeros. (Sorting both and comparing also works, in O(n log n).)

7. Hashing

The three pieces

1. Hash function — turns a key into an integer. Same key must always give the same number. A good one spreads different keys evenly. In Java this is the key's hashCode() method.
2. Buckets — the array of slots. The slot for a key is hash % capacity (Java uses hash & (capacity - 1), which is the same thing when capacity is a power of 2, and faster).
3. Collision handling — two different keys can land in the same bucket. This is not a bug; it is guaranteed to happen (infinitely many possible keys, finitely many buckets). The table needs a plan for it.

Collisions: chaining vs open addressing

Load factor and resizing

The load factor is entries / buckets. As it rises, chains get longer and lookups slow down. So when it passes a threshold (Java: 0.75), the table resizes: it allocates twice as many buckets and re-inserts every entry, because each entry's bucket index depends on the capacity. A resize is O(n), but it happens rarely (each time the size doubles), so put is still amortised O(1) — the same argument as ArrayList growth.

If you know you will store about a million entries, create the map with enough room to skip all the intermediate resizes: new HashMap<>(1_400_000) (expected size / 0.75), or HashMap.newHashMap(1_000_000) on Java 19+.

How Java's HashMap actually works

• Internally it is an array Node<K,V>[] table, lazily created with 16 buckets on the first put. Capacity is always a power of 2.
• Hash spreading: it computes h ^ (h >>> 16) so the high bits of hashCode() also influence the bucket (otherwise with 16 buckets only the lowest 4 bits would matter).
• Bucket index = (capacity - 1) & hash.
• get: go to the bucket, walk it, and for each node check hash == hash && key.equals(k).
• Treeification: if one bucket's chain grows past 8 nodes, i.e. when the 9th is added, and the table has at least 64 buckets, that chain is converted into a red-black tree, so a bad bucket costs O(log n) instead of O(n). It turns back into a list if it shrinks to 6. (If the table is smaller than 64, Java resizes instead.) This protects against many keys with colliding hashes, including deliberate attacks.
• Resize at size > capacity × 0.75, doubling the capacity. Each entry either stays at index i or moves to i + oldCapacity — Java checks one bit to decide.
• One null key is allowed (it goes to bucket 0). Iteration order is not defined and can change after a resize.
• Not thread-safe. Use ConcurrentHashMap across threads.

Build a hash map from scratch (separate chaining)

class MyHashMap<K, V> {
    private static class Node<K, V> {
        final K key; V value; Node<K, V> next;
        Node(K key, V value, Node<K, V> next) { this.key = key; this.value = value; this.next = next; }
    }
    private Node<K, V>[] buckets;
    private int size = 0;
    private static final double LOAD_FACTOR = 0.75;

    @SuppressWarnings("unchecked")
    MyHashMap() { buckets = (Node<K, V>[]) new Node[16]; }

    private int indexFor(Object key, int length) {
        int h = (key == null) ? 0 : key.hashCode();
        h ^= (h >>> 16);                  // mix high bits into low bits (like Java)
        return h & (length - 1);          // same as h % length when length is a power of 2
    }

    V get(K key) {                        // O(1) average
        for (Node<K, V> n = buckets[indexFor(key, buckets.length)]; n != null; n = n.next) {
            if (Objects.equals(n.key, key)) return n.value;
        }
        return null;
    }

    void put(K key, V value) {            // O(1) average, amortised
        int i = indexFor(key, buckets.length);
        for (Node<K, V> n = buckets[i]; n != null; n = n.next) {
            if (Objects.equals(n.key, key)) { n.value = value; return; }  // update
        }
        buckets[i] = new Node<>(key, value, buckets[i]);                   // insert at head
        if (++size > buckets.length * LOAD_FACTOR) resize();
    }

    @SuppressWarnings("unchecked")
    private void resize() {               // O(n), but rare -> amortised O(1)
        Node<K, V>[] old = buckets;
        buckets = (Node<K, V>[]) new Node[old.length * 2];
        for (Node<K, V> head : old) {
            for (Node<K, V> n = head; n != null; n = n.next) {
                int i = indexFor(n.key, buckets.length);
                buckets[i] = new Node<>(n.key, n.value, buckets[i]);
            }
        }
    }
}
// After 13 puts, the 13th pushes size past 16 * 0.75 = 12, so capacity becomes 32.

Operations and their cost

The equals / hashCode contract

HashMap finds a key in two steps: hashCode() picks the bucket, then equals() finds the exact key inside it. So the rule is: if a.equals(b) is true, then a.hashCode() == b.hashCode() must also be true. (The reverse is not required: different keys may share a hash — that is just a collision. For example "Aa".hashCode() and "BB".hashCode() are both 2112.)

Override equals but forget hashCode, and two "equal" objects get different identity-based hash codes, land in different buckets, and never find each other:

class BadPoint {
    final int x, y;
    BadPoint(int x, int y) { this.x = x; this.y = y; }
    @Override public boolean equals(Object o) {
        return o instanceof BadPoint p && p.x == x && p.y == y;
    }
    // hashCode NOT overridden -> uses identity hash
}

Set<BadPoint> bad = new HashSet<>();
bad.add(new BadPoint(1, 2));
System.out.println(bad.contains(new BadPoint(1, 2)));   // false  (bug!)

// Fix: a record generates correct equals AND hashCode for you
record Point(int x, int y) {}
Set<Point> good = new HashSet<>();
good.add(new Point(1, 2));
System.out.println(good.contains(new Point(1, 2)));     // true

Without records, write @Override public int hashCode() { return Objects.hash(x, y); } using the same fields that equals uses.

HashSet, LinkedHashMap, TreeMap

HashSet is literally a HashMap where the set elements are the keys and every value is the same dummy object. Same costs, same rules. set.add(x) returns false if x was already there — handy for duplicate detection.

Handy Map methods that make interview code short: getOrDefault(k, 0), merge(k, 1, Integer::sum) (counting), computeIfAbsent(k, x -> new ArrayList<>()).add(v) (grouping), putIfAbsent.

When to use hashing

• "Have I seen this before?" — HashSet. Turns an O(n) inner search into O(1), so many O(n²) brute forces become O(n).
• "How many times?" — HashMap<T, Integer> of counts.
• "Group things by some property" — HashMap<Key, List<T>>.
• Don't use it when you need order (use TreeMap), or when keys are small integers in a known range (a plain array is faster and simpler).

Common pitfalls

• Mutable keys: if you change a key object after putting it in, its hash changes and the map can no longer find it. A List key that you add to afterwards makes contains return false, even though the set's size is still 1. Use immutable keys (String, Integer, records).
• Comparing Integer values with ==: map.get("x") == map.get("y") compares object references. It happens to work for -128 to 127 (Java caches those), and silently fails for 1000. Use equals or unbox to int first.
• get returns null for a missing key; unboxing that into int throws NullPointerException. Use getOrDefault.
• Using arrays as keys: int[] uses identity equality. Convert to a String or List<Integer> first.
• Assuming iteration order of a HashMap. It is not insertion order.

Problem: Two Sum

Return indices of the two numbers that add up to target.

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index
    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);
    }
    return new int[0];
}
// [2, 7, 11, 15], 9 -> [0, 1]
// [3, 2, 4], 6      -> [1, 2]

Time O(n). Space O(n). Why it works: for each number, its partner (target - x) is fully determined, so instead of searching for it we ask the map "have I already seen it?" in O(1). Checking before inserting stops a number pairing with itself.

Problem: Group Anagrams

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        String key = Arrays.toString(count);          // e.g. "[1, 0, 0, ...]"
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}
// ["eat","tea","tan","ate","nat","bat"]
//   -> [bat], [eat, tea, ate], [tan, nat]   (group order may vary)

Time O(n · k), where k is the longest word length (the key has fixed length 26). Space O(n · k). Why it works: all anagrams have identical letter counts, so the count array is a perfect "signature" to group by. (Sorting each word as the key also works: O(n · k log k).)

Problem: Longest Consecutive Sequence

In an unsorted array, find the length of the longest run of consecutive integers, in O(n).

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);
    int best = 0;
    for (int x : set) {
        if (set.contains(x - 1)) continue;       // not the start of a run
        int len = 1;
        while (set.contains(x + len)) len++;     // walk the run
        best = Math.max(best, len);
    }
    return best;
}
// [100, 4, 200, 1, 3, 2]          -> 4   (1, 2, 3, 4)
// [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]  -> 9

Time O(n): the inner while only runs from the start of each run, so every number is walked over at most once in total. Space O(n). Why it works: only counting from numbers that have no left neighbour means each run is measured exactly once, from its first element.

Problem: Subarray Sum Equals K (prefix sums preview)

Count the contiguous subarrays whose sum is exactly k. Numbers can be negative, so a sliding window does not work.

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);                       // empty prefix
    int sum = 0, count = 0;
    for (int x : nums) {
        sum += x;
        count += prefixCount.getOrDefault(sum - k, 0);
        prefixCount.merge(sum, 1, Integer::sum);
    }
    return count;
}
// [1, 1, 1], k = 2                  -> 2
// [1, 2, 3], k = 3                  -> 2   ([1,2] and [3])
// [3, 4, 7, 2, -3, 1, 4, 2], k = 7  -> 4

Time O(n). Space O(n). Why it works: the sum of the subarray from j+1 to i is prefix[i] - prefix[j]. That equals k exactly when an earlier prefix equals prefix[i] - k, so we just count how many earlier prefixes had that value. The put(0, 1) covers subarrays that start at index 0.

8. Linked Lists

How it sits in memory

Singly, doubly, circular

In interviews, "linked list" almost always means singly linked with this node class (the LeetCode one):

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Insert and delete = rewiring pointers

To insert or delete, you need a reference to the node before the spot. Then it is two pointer changes, in the right order:

The dummy head trick: inserting or deleting at the head is a special case, because there is no "node before". Put a fake node (a dummy or sentinel) in front of the head. Now every real node has a node before it, the special case disappears, and at the end you return dummy.next. Use it any time the head might change.

Implement a linked list from scratch

class MyLinkedList {
    private final ListNode dummy = new ListNode(0);   // sentinel before the real head
    private ListNode tail = dummy;
    private int size = 0;

    void addFirst(int val) {                 // O(1)
        dummy.next = new ListNode(val, dummy.next);
        if (tail == dummy) tail = dummy.next;
        size++;
    }
    void addLast(int val) {                  // O(1) thanks to tail pointer
        tail.next = new ListNode(val);
        tail = tail.next;
        size++;
    }
    void addAt(int index, int val) {         // O(n): walk to index-1
        if (index < 0 || index > size) throw new IndexOutOfBoundsException(index);
        if (index == size) { addLast(val); return; }
        ListNode prev = dummy;
        for (int i = 0; i < index; i++) prev = prev.next;
        prev.next = new ListNode(val, prev.next);
        size++;
    }
    boolean remove(int val) {                // O(n): find the node BEFORE the target
        for (ListNode prev = dummy; prev.next != null; prev = prev.next) {
            if (prev.next.val == val) {
                if (prev.next == tail) tail = prev;
                prev.next = prev.next.next;  // unlink
                size--;
                return true;
            }
        }
        return false;
    }
    int indexOf(int val) {                   // O(n)
        int i = 0;
        for (ListNode cur = dummy.next; cur != null; cur = cur.next, i++) {
            if (cur.val == val) return i;
        }
        return -1;
    }
}
// addLast(2), addLast(3), addFirst(1), addAt(3, 4), addAt(1, 9)
//   -> 1 -> 9 -> 2 -> 3 -> 4   (size 5)

With a doubly linked list, if you already hold a node, removing it needs no search at all — this is how an LRU cache removes entries in O(1):

void unlink(DNode node) {          // assumes dummy head and tail, so prev/next are never null
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

Operations and their cost

Java built-in: LinkedList (and why you rarely want it)

java.util.LinkedList is a doubly linked list that implements both List and Deque: addFirst, addLast, removeFirst, getFirst are all O(1). But its get(i) is O(n), and every element is a separate object, so it is slow and memory-hungry in practice. For a stack or queue, ArrayDeque is faster; for a list, ArrayList. In interviews, linked-list questions give you ListNode and expect you to move pointers yourself.

When to use a linked list

• You hold references to nodes and must remove/insert them in O(1): LRU cache (HashMap + doubly linked list), adjacency lists, free lists in allocators.
• You need to splice lists together or split them without copying.
• Otherwise, prefer an array-based structure — random access and cache locality usually win.

Common pitfalls

• NullPointerException: check cur != null before cur.next, and fast != null && fast.next != null before fast.next.next.
• Losing the rest of the list: save next before you overwrite cur.next.
• Moving head itself while walking, then returning it — use a separate cur variable.
• Forgetting the head can change — use a dummy node.
• Creating cycles by accident (for example forgetting to set the new tail's next to null), which makes printing loop forever.
• Draw it. Three boxes and arrows on paper catch most bugs before you write code.

Problem: Reverse Linked List (iterative and recursive)

// Iterative: O(n) time, O(1) space
ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;   // 1. save the rest
        cur.next = prev;            // 2. flip the pointer
        prev = cur;                 // 3. step prev forward
        cur = next;                 // 4. step cur forward
    }
    return prev;                    // prev is the new head
}

// Recursive: O(n) time, O(n) space (call stack)
ListNode reverseRec(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseRec(head.next);  // reverse the rest
    head.next.next = head;                      // node after me points back to me
    head.next = null;                           // I become the tail
    return newHead;
}
// 1 -> 2 -> 3 -> 4 -> 5  becomes  5 -> 4 -> 3 -> 2 -> 1  (both versions)

Why it works: iteratively, everything left of cur is already reversed and prev is its head, so each step grows the reversed part by one. Recursively, trust the call to reverse the rest; head.next is now the tail of that reversed part, so hang head after it. The recursive version can overflow the stack on very long lists (tens of thousands of nodes).

Problem: Merge Two Sorted Lists

ListNode mergeTwoLists(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;   // attach whatever is left
    return dummy.next;
}
// 1->2->4  +  1->3->4  ->  1 -> 1 -> 2 -> 3 -> 4 -> 4

Time O(n + m). Space O(1) — it reuses the existing nodes. Why it works: the smallest remaining element is always at the front of one of the two lists, so taking the smaller front each time builds the merged list in order (the same step as merge sort).

Problem: Remove Nth Node From End

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i <= n; i++) fast = fast.next;   // gap of n+1 nodes
    while (fast != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;                       // slow is just before the target
    return dummy.next;
}
// 1->2->3->4->5, n = 2  ->  1 -> 2 -> 3 -> 5
// 1, n = 1              ->  null   (the dummy handles removing the head)

Time O(n), one pass. Space O(1). Why it works: if fast starts n+1 steps ahead and both move together, then when fast falls off the end, slow is exactly n+1 from the end — the node just before the one to delete.

Problem: Linked List Cycle (preview of fast and slow pointers)

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 -> 2 -> 0 -> -4 -> (back to 2)  -> true
// 1 -> 2                           -> false

Time O(n). Space O(1) (a HashSet of visited nodes also works but costs O(n)). Why it works: inside a loop, the fast pointer gains one step on the slow one each move, so the gap shrinks by 1 every time and they must meet; with no loop, fast simply reaches null. The fast and slow pointers section covers finding where the cycle starts.

Problem: Add Two Numbers

Digits are stored in reverse order (ones digit first). Return their sum as a list: 342 + 465 = 807 is 2->4->3 + 5->6->4 = 7->0->8.

ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), tail = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        carry = sum / 10;
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
    }
    return dummy.next;
}
// 2->4->3 + 5->6->4  ->  7 -> 0 -> 8
// 9->9->9 + 1        ->  0 -> 0 -> 0 -> 1

Time O(max(n, m)). Space O(max(n, m)) for the result list. Why it works: it is school addition, right to left with a carry — and the reversed storage means the list already starts at the rightmost digit. Keeping carry != 0 in the loop condition adds the final extra digit.

9. Stacks

Two ways to build one

Array-backed: keep an array and an index top. Push writes at top and moves it up; pop moves it down. Grow the array when full (amortised O(1), like ArrayList). Fast and cache-friendly.

class ArrayStack {
    private int[] data = new int[8];
    private int top = 0;                      // index of the next free slot

    void push(int x) {                        // amortised O(1)
        if (top == data.length) data = Arrays.copyOf(data, top * 2);
        data[top++] = x;
    }
    int pop() {                               // O(1)
        if (top == 0) throw new RuntimeException("stack underflow");
        return data[--top];
    }
    int peek() {
        if (top == 0) throw new RuntimeException("stack is empty");
        return data[top - 1];
    }
    boolean isEmpty() { return top == 0; }
}

Linked: the head of a singly linked list is the top. Push = add a new head, pop = move head forward. Always true O(1) (no resizing), but one object per element.

class LinkedStack {
    private static class Node { int val; Node next; Node(int v, Node n) { val = v; next = n; } }
    private Node head;                        // head IS the top

    void push(int x) { head = new Node(x, head); }        // O(1)
    int pop() {                                            // O(1)
        if (head == null) throw new RuntimeException("stack underflow");
        int v = head.val;
        head = head.next;
        return v;
    }
    int peek() {
        if (head == null) throw new RuntimeException("stack is empty");
        return head.val;
    }
    boolean isEmpty() { return head == null; }
}

Operations and their cost

Java built-in: use ArrayDeque, not Stack

The old java.util.Stack class extends Vector: every method is synchronized (slow) and it lets you insert in the middle, which breaks the idea of a stack. The Java docs themselves recommend Deque:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.push(3);   // push adds at the FRONT of the deque
System.out.println(stack);                     // [3, 2, 1]  (top first)
stack.peek();      // 3  (null if empty)
stack.pop();       // 3  (throws NoSuchElementException if empty)
stack.isEmpty();   // false

Note: ArrayDeque does not allow null elements. peek() returns null on an empty deque, while pop() throws.

The call stack: where you already use a stack

Every time a method is called, the JVM pushes a stack frame (its local variables and where to return to). When the method returns, its frame is popped. That is why recursion works — and why very deep recursion throws StackOverflowError.

This link matters: any recursive algorithm can be rewritten with your own explicit stack (for example iterative DFS), which avoids stack overflow on deep inputs.

When to use a stack

• Matching pairs / nesting: brackets, HTML tags, nested k[...] encodings.
• Undo and back-button history.
• Expression evaluation: postfix (RPN), infix with operator precedence.
• DFS without recursion.
• "Next greater / smaller element" problems — the monotonic stack (a stack kept sorted), covered in its own section.

Common pitfalls

• Popping an empty stack: always check isEmpty() first — it is often part of the answer (a ) with nothing to match means invalid).
• Forgetting leftovers: after the loop, a non-empty stack usually means unmatched items.
• Operand order for - and /: the first pop is the right operand.
• Mixing deque ends: with ArrayDeque, use push/pop/peek consistently. Mixing in offer/poll (other end) turns it into something else.
• Storing indices instead of values is often what the problem needs (for distances, like daily temperatures).

Problem: Valid Parentheses

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');           // push the EXPECTED closer
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();                      // leftovers = unclosed openers
}
// "()[]{}" -> true   "([)]" -> false   "{[]}" -> true   "((" -> false

Time O(n). Space O(n). Why it works: the most recently opened bracket must be the first one closed — exactly LIFO. Pushing the expected closer makes the check a single comparison.

Problem: Min Stack

Support push, pop, top and getMin, all in O(1).

class MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();   // {value, minSoFar}

    void push(int val) {
        int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, min});
    }
    void pop()   { stack.pop(); }
    int top()    { return stack.peek()[0]; }
    int getMin() { return stack.peek()[1]; }
}
// push(-2), push(0), push(-3): getMin() = -3
// pop(): top() = 0, getMin() = -2

Time O(1) for every operation. Space O(n). Why it works: a stack only ever removes from the top, so the minimum "below and including" each element never changes while that element is there — store it alongside.

Problem: Evaluate Reverse Polish Notation

In RPN (postfix), operators come after their operands: ["2","1","+","3","*"] means (2 + 1) × 3 = 9.

int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String t : tokens) {
        switch (t) {
            case "+" -> stack.push(stack.pop() + stack.pop());
            case "*" -> stack.push(stack.pop() * stack.pop());
            case "-" -> { int b = stack.pop(), a = stack.pop(); stack.push(a - b); }
            case "/" -> { int b = stack.pop(), a = stack.pop(); stack.push(a / b); }
            default  -> stack.push(Integer.parseInt(t));
        }
    }
    return stack.pop();
}
// ["2","1","+","3","*"]   -> 9
// ["4","13","5","/","+"]  -> 6    (13 / 5 = 2, integer division toward zero)
// ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] -> 22

Time O(n). Space O(n). Why it works: in postfix, an operator always applies to the two most recent unused values, which are exactly the top two of the stack. For - and / the first pop is the right-hand operand.

Problem: Daily Temperatures (monotonic stack preview)

For each day, how many days until a warmer one? 0 if never.

int[] dailyTemperatures(int[] temps) {
    int n = temps.length;
    int[] ans = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();   // indices, temps strictly decreasing
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
            int j = stack.pop();                 // day j finally found a warmer day: i
            ans[j] = i - j;
        }
        stack.push(i);
    }
    return ans;                                  // days left on stack keep 0
}
// [73, 74, 75, 71, 69, 72, 76, 73] -> [1, 1, 4, 2, 1, 1, 0, 0]

Time O(n): each index is pushed once and popped at most once. Space O(n). Why it works: the stack holds days still waiting for a warmer day, coldest on top. A new warmer day answers every waiting day colder than it, and those are exactly the ones on top.

Problem: Decode String

"3[a2[c]]" decodes to "accaccacc".

String decodeString(String s) {
    Deque<Integer> counts = new ArrayDeque<>();
    Deque<StringBuilder> outer = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');              // numbers can have many digits
        } else if (c == '[') {
            counts.push(k);                      // save state, start fresh inside
            outer.push(cur);
            cur = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            int times = counts.pop();
            StringBuilder prev = outer.pop();
            prev.append(cur.toString().repeat(times));
            cur = prev;                          // back to the outer level
        } else {
            cur.append(c);
        }
    }
    return cur.toString();
}
// "3[a]2[bc]"     -> "aaabcbc"
// "3[a2[c]]"      -> "accaccacc"
// "2[abc]3[cd]ef" -> "abcabccdcdcdef"
// "10[x]"         -> "xxxxxxxxxx"

Time O(output length), since every output character is built once per nesting level it sits in. Space O(output length). Why it works: [ means "pause what I was building and start a new inner piece", ] means "finish the inner piece and resume the outer one" — pausing and resuming in nested order is exactly what a stack does.

10. Queues & Deques

Implementing a queue: the circular array

With a plain array, removing from the front would mean shifting everything left (O(n)). A linked list with head and tail pointers gives O(1) at both ends, but the classic array trick is the circular buffer (ring buffer): keep a head index that moves forward on every dequeue, and let both ends wrap around to index 0 when they pass the end, using % capacity. Nothing ever shifts.

Tracking size separately avoids the classic ambiguity: if you only keep head and tail, then head == tail could mean empty or full.

This is also the answer to Design Circular Queue (LeetCode 622) — the method names below are the ones that problem uses:

class MyCircularQueue {
    private final int[] data;
    private int head = 0;     // index of the front element
    private int size = 0;     // number of elements stored

    MyCircularQueue(int k) { data = new int[k]; }

    boolean enQueue(int value) {                         // O(1)
        if (isFull()) return false;
        int tail = (head + size) % data.length;          // first free slot, wrapping around
        data[tail] = value;
        size++;
        return true;
    }
    boolean deQueue() {                                  // O(1)
        if (isEmpty()) return false;
        head = (head + 1) % data.length;                 // front moves forward, wraps
        size--;
        return true;
    }
    int Front() { return isEmpty() ? -1 : data[head]; }
    int Rear()  { return isEmpty() ? -1 : data[(head + size - 1) % data.length]; }
    boolean isEmpty() { return size == 0; }
    boolean isFull()  { return size == data.length; }
}
// capacity 3: enQueue 1, 2, 3 -> true true true; enQueue(4) -> false (full)
// Rear() = 3; deQueue() -> true; enQueue(4) -> true (wrapped into slot 0)
// Rear() = 4, Front() = 2

Time O(1) for every operation. Space O(k). Why it works: % capacity turns the straight array into a loop, so freed slots at the start are reused instead of shifting elements.

Operations and their cost

Java built-ins: Queue, Deque, ArrayDeque

Queue and Deque are interfaces. ArrayDeque (a growable circular array) is the default implementation for both — faster than LinkedList. Each operation comes in two flavours: one that throws on failure and one that returns a special value (null or false). Interview code normally uses the second.

Queue<Integer> q = new ArrayDeque<>();
q.offer(1); q.offer(2); q.offer(3);
q.peek();   // 1
q.poll();   // 1, queue is now [2, 3]
new ArrayDeque<Integer>().poll();   // null (remove() would throw)

Deque<Integer> d = new ArrayDeque<>();
d.offerFirst(2); d.offerLast(3); d.offerFirst(1);   // [1, 2, 3]
d.pollLast();    // 3
d.peekFirst();   // 1

Other queues you should know exist: PriorityQueue (next section — not FIFO, smallest first), LinkedList (allows null, slower), and BlockingQueue implementations such as ArrayBlockingQueue for producer-consumer threads.

When to use a queue or deque

• Queue: process things in arrival order — BFS, task scheduling, buffering between a producer and a consumer, rate limiting (a queue of timestamps).
• Deque: when you need both ends — sliding window max/min (monotonic deque), palindrome checks, 0-1 BFS, "undo with a size limit" (drop from the old end).
• If you only need one end, it is really a stack — still use ArrayDeque.

Common pitfalls

• Mixing ends: push adds at the front, offer at the back. Using push + poll gives a stack, not a queue.
• ArrayDeque rejects null — offer(null) throws NullPointerException.
• Unchecked poll() returns null; unboxing it to int throws.
• Using q.size() as a loop bound while adding: in level-order BFS, save the size in a variable before the inner loop.
• In your own ring buffer, forgetting the % on one of the index updates.

Problem: Implement Queue using Stacks

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();   // new items land here
    private final Deque<Integer> out = new ArrayDeque<>();  // items leave from here

    void push(int x) { in.push(x); }                        // O(1)
    int pop()  { shift(); return out.pop(); }               // amortised O(1)
    int peek() { shift(); return out.peek(); }
    boolean empty() { return in.isEmpty() && out.isEmpty(); }

    private void shift() {
        if (out.isEmpty()) {                                // only refill when empty
            while (!in.isEmpty()) out.push(in.pop());       // reverses the order
        }
    }
}
// push 1, push 2: peek() = 1, pop() = 1; push 3: pop() = 2, pop() = 3, empty() = true

Time push O(1); pop/peek amortised O(1) — each element moves from in to out exactly once. Space O(n). Why it works: pouring one stack into another reverses the order, turning last-in-first-out into first-in-first-out; only pouring when out is empty keeps older items ahead of newer ones.

Problem: Sliding Window Maximum (monotonic deque)

For every window of size k, report the maximum. [1,3,-1,-3,5,3,6,7], k = 3 gives [3,3,5,5,6,7].

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();     // indices; their values are decreasing
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();       // fell out of window
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast(); // useless now
        dq.offerLast(i);
        if (i >= k - 1) ans[i - k + 1] = nums[dq.peekFirst()];              // front = max
    }
    return ans;
}
// [1, 3, -1, -3, 5, 3, 6, 7], k = 3 -> [3, 3, 5, 5, 6, 7]
// [9, 8, 7, 6], k = 2               -> [9, 8, 7]

Time O(n): each index enters and leaves the deque at most once. Space O(k). Why it works: a number that is smaller than a newer number can never be a window maximum again (the newer one outlives it), so it is thrown away. What remains is decreasing, so the front is always the max.

Problem: BFS preview — shortest path in a grid

Minimum steps from the top-left to the bottom-right of a grid (0 = open, 1 = wall), moving up/down/left/right.

int shortestPath(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    if (grid[0][0] == 1) return -1;
    boolean[][] seen = new boolean[rows][cols];
    Queue<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{0, 0});
    seen[0][0] = true;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int steps = 0; !q.isEmpty(); steps++) {
        for (int size = q.size(); size > 0; size--) {       // one "ring" (level) at a time
            int[] cell = q.poll();
            if (cell[0] == rows - 1 && cell[1] == cols - 1) return steps;
            for (int[] d : dirs) {
                int r = cell[0] + d[0], c = cell[1] + d[1];
                if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 0 && !seen[r][c]) {
                    seen[r][c] = true;                       // mark when ENQUEUED
                    q.offer(new int[]{r, c});
                }
            }
        }
    }
    return -1;
}
// {{0,0,0},{1,1,0},{0,0,0}} -> 4
// {{0,1},{1,0}}             -> -1

Time O(rows × cols). Space O(rows × cols). Why it works: the FIFO queue processes all cells 1 step away, then all cells 2 steps away, and so on, like ripples in water — so the first time we reach the target is by a shortest path. The graph sections cover BFS fully.

11. Heaps & Priority Queues

A complete binary tree stored in an array

A heap is a complete binary tree: every level is full except possibly the last, which fills from left to right. Because there are no gaps, the tree fits perfectly in an array, level by level, with no pointers at all. Parent and children are found with index maths:

A complete tree with n nodes has height about log₂ n. Every heap operation walks at most one path from root to leaf, which is where O(log n) comes from.

Sift up (insert) and sift down (remove the top)

• Insert (offer): put the new value at the end of the array (the next free spot in the bottom level), then sift up: while it is smaller than its parent, swap with the parent.
• Remove the min (poll): the answer is heap[0]. Move the last element into the root to keep the tree complete, then sift down: while it is bigger than its smaller child, swap with that child.

Implement a min-heap from scratch

class MinHeap {
    private int[] heap;
    private int size = 0;

    MinHeap(int capacity) { heap = new int[capacity]; }

    // Build from an existing array in O(n) (heapify)
    MinHeap(int[] values) {
        heap = Arrays.copyOf(values, Math.max(1, values.length));
        size = values.length;
        for (int i = size / 2 - 1; i >= 0; i--) siftDown(i);   // last parent down to root
    }

    void offer(int x) {                                  // O(log n)
        if (size == heap.length) heap = Arrays.copyOf(heap, size * 2);
        heap[size] = x;                                  // put at the end ...
        siftUp(size++);                                  // ... and bubble up
    }
    int peek() {                                         // O(1)
        if (size == 0) throw new NoSuchElementException();
        return heap[0];
    }
    int poll() {                                         // O(log n)
        if (size == 0) throw new NoSuchElementException();
        int min = heap[0];
        heap[0] = heap[--size];                          // move last element to root ...
        siftDown(0);                                     // ... and sink it
        return min;
    }

    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[parent] <= heap[i]) break;          // order is fine
            swap(i, parent);
            i = parent;
        }
    }
    private void siftDown(int i) {
        while (true) {
            int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
            if (left < size && heap[left] < heap[smallest]) smallest = left;
            if (right < size && heap[right] < heap[smallest]) smallest = right;
            if (smallest == i) break;                    // both children bigger: done
            swap(i, smallest);
            i = smallest;
        }
    }
    private void swap(int a, int b) { int t = heap[a]; heap[a] = heap[b]; heap[b] = t; }
}
// offer 5, 3, 8, 1, 9, 2 -> array [1, 3, 2, 5, 9, 8]; polling gives 1 2 3 5 8 9
// new MinHeap(new int[]{9, 4, 7, 1, 8, 2, 3}) -> array [1, 4, 2, 9, 8, 7, 3]

Heapify in O(n), not O(n log n)

Building a heap by calling offer n times costs O(n log n). Heapify is faster: treat the array as a tree already, and call siftDown on every parent from the last one (n/2 - 1) back to the root. Leaves (half of all nodes) need no work.

Why O(n)? A node can only sink as far as the levels below it. Half the nodes are leaves (sink 0), a quarter sit one level up (sink at most 1), an eighth at most 2, and so on: n/4·1 + n/8·2 + n/16·3 + … which adds up to less than n. Most nodes are near the bottom, where sifting down is cheap.

Operations and their cost

Java built-in: PriorityQueue

PriorityQueue is a binary min-heap by default. For a max-heap or custom ordering, pass a Comparator (a rule that says which of two items comes first).

PriorityQueue<Integer> minPq = new PriorityQueue<>(List.of(5, 1, 9));
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
maxPq.addAll(List.of(5, 1, 9));
System.out.println(minPq.peek() + " " + maxPq.peek());      // 1 9

// Objects: order by priority, then by name to break ties
record Task(String name, int priority) {}
PriorityQueue<Task> tasks = new PriorityQueue<>(
        Comparator.comparingInt(Task::priority).thenComparing(Task::name));
tasks.offer(new Task("write", 2));
tasks.offer(new Task("deploy", 1));
tasks.offer(new Task("alert", 1));
// polling gives: alert, deploy, write

// int[] pairs: sort by the second element
PriorityQueue<int[]> pairs = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));

Heap sort

Build a max-heap in place (O(n)), then repeatedly swap the root (the largest) to the end of the array and sift the new root down within the shrinking heap. The sorted part grows from the back.

void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) sink(a, i, n);   // build max-heap: O(n)
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;           // largest goes to the back
        sink(a, 0, end);                                   // fix the shrunk heap
    }
}
void sink(int[] a, int i, int n) {
    while (2 * i + 1 < n) {
        int child = 2 * i + 1;
        if (child + 1 < n && a[child + 1] > a[child]) child++;  // bigger child
        if (a[i] >= a[child]) break;
        int t = a[i]; a[i] = a[child]; a[child] = t;
        i = child;
    }
}
// [5, 1, 9, 3, 7, 2] -> [1, 2, 3, 5, 7, 9]

Time O(n log n) always (no bad worst case like quicksort). Space O(1). Not stable (equal items may swap order), and slower than quicksort in practice because it jumps around the array.

When to use a heap

• You repeatedly need the current smallest/largest while items keep arriving: scheduling, Dijkstra's shortest path, event simulation.
• Top K / Kth largest: keep a heap of size k — O(n log k) instead of sorting everything in O(n log n).
• Merging K sorted things: a heap of the K current fronts.
• Running median: two heaps.
• Not for searching a specific value (O(n)), and not when you need everything in sorted order at once (just sort) or need ordered iteration (use TreeMap/TreeSet).

Common pitfalls

• Iterating or printing a PriorityQueue is not sorted. Offering 5, 1, 4, 2, 3 and printing gives [1, 2, 4, 5, 3] — the raw heap array. Only repeated poll() gives sorted order (1 2 3 4 5).
• Overflow in comparators: (a, b) -> a - b breaks for large values — Integer.MIN_VALUE - 1 overflows to 2147483647, a positive number, so the order is wrong. Use Integer.compare(a, b) or Comparator.comparingInt.
• Changing an object's priority while it is inside the heap does not re-sort it. Remove it, change it, re-insert — or insert a new entry and skip stale ones when polled ("lazy deletion", common in Dijkstra).
• Min vs max confusion for "k largest": you keep a min-heap of size k, so the smallest of the top k sits on top and is easy to evict.
• PriorityQueue is not thread-safe; use PriorityBlockingQueue across threads.

Problem: Kth Largest Element in an Array

int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();   // holds the k largest seen
    for (int x : nums) {
        minHeap.offer(x);
        if (minHeap.size() > k) minHeap.poll();               // drop the smallest
    }
    return minHeap.peek();                                    // smallest of the top k
}
// [3, 2, 1, 5, 6, 4], k = 2          -> 5
// [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 -> 4

Time O(n log k). Space O(k). Why it works: the heap always holds the k largest values seen so far; the smallest of those is, by definition, the kth largest. (Quickselect gets O(n) on average — mention it as a follow-up.)

Problem: Merge K Sorted Lists

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
    for (ListNode head : lists) if (head != null) pq.offer(head);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();            // smallest head among all lists
        tail.next = node;
        tail = node;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}
// [1->4->5, 1->3->4, 2->6] -> 1 1 2 3 4 4 5 6

Time O(N log k), where N is the total number of nodes and k the number of lists. Space O(k) for the heap. Why it works: the next node of the merged list must be the smallest of the k current fronts; the heap gives that in O(log k), and when a front is used its successor takes its place.

Problem: Top K Frequent Elements

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);
    // min-heap by frequency, size k
    PriorityQueue<Map.Entry<Integer, Integer>> pq =
            new PriorityQueue<>(Map.Entry.comparingByValue());
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        pq.offer(e);
        if (pq.size() > k) pq.poll();
    }
    int[] ans = new int[k];
    for (int i = k - 1; i >= 0; i--) ans[i] = pq.poll().getKey();   // most frequent first
    return ans;
}
// [1, 1, 1, 2, 2, 3], k = 2 -> [1, 2]

Time O(n log k): counting is O(n), then each of up to n distinct values costs O(log k). Space O(n) for the counts. Why it works: the same "keep the k best in a min-heap" idea as kth largest, just ranked by count instead of value. (Bucket sort by frequency gets O(n).)

Problem: Find Median from Data Stream (two heaps preview)

class MedianFinder {
    private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    private final PriorityQueue<Integer> high = new PriorityQueue<>();                          // min-heap

    void addNum(int num) {                         // O(log n)
        low.offer(num);
        high.offer(low.poll());                    // largest of low moves to high
        if (high.size() > low.size()) low.offer(high.poll());  // keep low >= high in size
    }
    double findMedian() {                          // O(1)
        if (low.size() > high.size()) return low.peek();
        return (low.peek() + high.peek()) / 2.0;
    }
}
// addNum(1), addNum(2): findMedian() = 1.5
// addNum(3):            findMedian() = 2.0

Time addNum O(log n), findMedian O(1). Space O(n). Why it works: every number in low is ≤ every number in high, and the sizes differ by at most one, so the middle value(s) are exactly the two tops. The two-heaps section goes further.

12. Binary Trees

Terminology

The node class

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

In memory each node is a separate object on the heap holding a value and two references. There is no array and no index — you can only reach a node by walking down from the root. That is why "find a value" in a plain binary tree is O(n): you may have to visit every node.

Traversals — the four ways to visit every node

The name tells you when the root is visited compared to its children:

• Preorder (root, left, right) — visit the node before its children. Use it to copy or serialize a tree: you meet the parent before you need to build its children.
• Inorder (left, root, right) — on a Binary Search Tree this gives values in sorted order.
• Postorder (left, right, root) — children finish before the parent. Use it when a node needs answers from its children (height, diameter, deleting a tree).
• Level order (BFS) — row by row, top to bottom. Use it for "per level" questions and shortest distance from the root.

void preorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    out.add(node.val);            // root
    preorder(node.left, out);     // left
    preorder(node.right, out);    // right
}
void inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorder(node.left, out);      // left
    out.add(node.val);            // root
    inorder(node.right, out);     // right
}
void postorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    postorder(node.left, out);    // left
    postorder(node.right, out);   // right
    out.add(node.val);            // root
}

All three are O(n) time (each node visited once) and O(h) extra space for the call stack, where h is the height: O(log n) for a balanced tree, O(n) for a skewed one. A skewed tree with 100,000 nodes can throw StackOverflowError in Java, which is the main reason interviewers ask for iterative versions.

Iterative traversals with an explicit stack

Recursion uses the call stack for you. Iterative code just makes that stack visible, using ArrayDeque (never the old Stack class, which is synchronized and slow).

// Preorder: pop, visit, push right then left (so left is processed first)
List<Integer> preorderIter(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.add(node.val);
        if (node.right != null) stack.push(node.right); // push right first
        if (node.left != null) stack.push(node.left);   // so left pops first
    }
    return out;
}

// Inorder: slide left pushing nodes, pop one, visit, then go right
List<Integer> inorderIter(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {          // go as far left as possible
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();             // leftmost unvisited node
        out.add(cur.val);
        cur = cur.right;               // then its right subtree
    }
    return out;
}

// Postorder: do "root, right, left" and reverse it -> "left, right, root"
List<Integer> postorderIter(TreeNode root) {
    LinkedList<Integer> out = new LinkedList<>();
    if (root == null) return out;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        out.addFirst(node.val);        // prepend = reverse for free
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return out;
}

Level order with a queue

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) return levels;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();             // nodes on this level
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        levels.add(level);
    }
    return levels;   // sample tree: [[1], [2, 3], [4, 5, 6]]
}

The trick is int size = queue.size() before the inner loop: it freezes how many nodes belong to the current level, even while you add the next level's nodes to the back. Time O(n), space O(w) where w is the widest level (up to about n/2 for the last level of a perfect tree).

Morris traversal (O(1) extra space)

Morris inorder avoids both recursion and a stack. For each node with a left subtree, it finds the inorder predecessor (the rightmost node of the left subtree) and temporarily points that node's right back up to the current node — a "thread". Following the thread later is how it climbs back up without a stack. On the second visit it removes the thread, so the tree is restored.

List<Integer> morrisInorder(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            out.add(cur.val);
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;            // find inorder predecessor
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {            // first visit: build thread
                pred.right = cur;
                cur = cur.left;
            } else {                             // second visit: remove thread
                pred.right = null;
                out.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return out;
}

Time O(n) (each edge is walked at most a few times), space O(1). It is rarely required, but mentioning it when asked "can you do it without extra space?" scores points. Downside: it modifies the tree while running, so it is not safe with concurrent readers.

Operations complexity (plain binary tree, n nodes, height h)

Java built-ins: Java has no general binary tree class. TreeMap/TreeSet are balanced binary search trees (section 14) and PriorityQueue is a binary heap in an array. In interviews you write TreeNode yourself.

Problem 1 — Maximum depth

// Number of nodes on the longest root-to-leaf path
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}   // sample tree: 3

Why it works: the depth of a tree is one (for this node) plus the deeper of its two subtrees. The empty tree has depth 0, which stops the recursion. O(n) time, O(h) space.

Problem 2 — Invert a binary tree

TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
}   // sample tree level order becomes [[1], [3, 2], [6, 5, 4]]

Why it works: a mirror image is "swap my two children, and mirror each of them". Save left in tmp first, or you would overwrite it before using it. O(n) time, O(h) space.

Problem 3 — Diameter of a binary tree

The diameter is the number of edges on the longest path between any two nodes. That path may not go through the root.

class Solution {
    private int best = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return best;
    }
    // returns height in nodes; updates best with the longest path through node
    private int height(TreeNode node) {
        if (node == null) return 0;
        int l = height(node.left);
        int r = height(node.right);
        best = Math.max(best, l + r);   // path bends at this node
        return 1 + Math.max(l, r);
    }
}   // sample tree: 4 (path 4-2-1-3-6)

Why it works: every path has one highest node where it "bends". The longest path bending at a node is (height of left) + (height of right) edges. Postorder computes both heights once, so one pass checks every bend point. O(n) time instead of the naive O(n²) that recomputes heights.

Problem 4 — Lowest common ancestor (LCA)

The LCA of p and q is the deepest node that has both p and q in its subtree (a node counts as its own descendant).

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root; // p and q split here
    return left != null ? left : right;             // both on one side
}   // sample: lca(4,5)=2, lca(4,6)=1, lca(2,4)=2

Why it works: each call reports "I found p or q (or their LCA) in my subtree" by returning a non-null node. The first node where both sides report something is where the paths to p and q split — the LCA. If a node is p itself, returning it right away is correct even when q is below it, because then p is the LCA. O(n) time, O(h) space.

Problem 5 — Serialize and deserialize

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        write(root, sb);
        return sb.toString();
    }
    private void write(TreeNode node, StringBuilder sb) {
        if (node == null) { sb.append("#,"); return; }   // mark nulls
        sb.append(node.val).append(',');
        write(node.left, sb);
        write(node.right, sb);
    }
    public TreeNode deserialize(String data) {
        Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(",")));
        return read(tokens);
    }
    private TreeNode read(Deque<String> tokens) {
        String t = tokens.poll();
        if (t.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(t));
        node.left = read(tokens);      // same order as write: root, left, right
        node.right = read(tokens);
        return node;
    }
}   // sample tree -> "1,2,4,#,#,5,#,#,3,#,6,#,#,"

Why it works: preorder alone cannot rebuild a tree (many shapes share the same order), but preorder with null markers can: the markers tell the reader exactly where each subtree ends. Reading consumes tokens in the same root-left-right order they were written. O(n) time and space for both directions.

Pitfalls

• Forgetting the null base case — nearly every tree bug is a NullPointerException.
• Mixing up depth (counted from the top) and height (counted from the bottom), or edges vs nodes. Say which one you mean.
• Recomputing heights inside a recursion (O(n²)). Return the height from the same pass instead.
• Deep recursion on skewed input — offer the iterative version.
• Using a static field for the answer and forgetting to reset it between test cases. Prefer an instance field or an int[] holder.

13. Binary Search Trees

Search and insert

TreeNode search(TreeNode root, int key) {
    TreeNode cur = root;
    while (cur != null && cur.val != key) {
        cur = key < cur.val ? cur.left : cur.right;   // discard half
    }
    return cur;   // null if not found
}

TreeNode insert(TreeNode root, int key) {
    if (root == null) return new TreeNode(key);       // empty spot found
    if (key < root.val) root.left = insert(root.left, key);
    else if (key > root.val) root.right = insert(root.right, key);
    return root;                                      // duplicates ignored
}

Insert walks down exactly like search. When it falls off the tree (reaches null), that empty spot is where the new key belongs. The pattern root.left = insert(root.left, key) — "rebuild the link on the way back up" — is worth memorising: delete uses it too. Both are O(h) time.

Delete — the three cases

1. Leaf (no children): just remove it — return null to the parent.
2. One child: the child takes the node's place — return the child to the parent.
3. Two children: find the inorder successor (the smallest value in the right subtree — go right once, then left as far as possible). Copy its value into this node, then delete the successor from the right subtree. The successor has no left child, so that second delete is always case 1 or 2.

TreeNode delete(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) {
        root.left = delete(root.left, key);
    } else if (key > root.val) {
        root.right = delete(root.right, key);
    } else {
        // Case 1 and 2: zero or one child -> replace node by the other side
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // Case 3: two children -> copy inorder successor, delete it from right
        TreeNode succ = root.right;
        while (succ.left != null) succ = succ.left;   // smallest in right subtree
        root.val = succ.val;
        root.right = delete(root.right, succ.val);
    }
    return root;
}

Notice the leaf case needs no special code: if left is null we return right, which is also null for a leaf. Time O(h). (Using the inorder predecessor — largest value on the left — works equally well.)

Inorder = sorted

Inorder visits left subtree, node, right subtree. In a BST that is "everything smaller, me, everything larger" at every level, so the output is sorted. This one fact solves a family of problems: validate a BST (the inorder must be strictly increasing), kth smallest (stop at the kth visit), two-sum in a BST, recover a BST with two swapped nodes (find the two places where the order breaks).

Operations complexity

Degenerate BST — why balancing matters

A plain BST has no control over its shape: the shape depends on insert order. Insert 1, 2, 3, 4, 5, 6, 7 in order and every node goes to the right of the last one:

Now search is O(n), no better than a list. Real data is often sorted or nearly sorted (timestamps, auto-increment IDs), so this is not a rare edge case. Self-balancing trees (AVL, red-black — next section) fix the shape after every insert and delete, guaranteeing O(log n). That is what Java's TreeMap uses.

Problem 1 — Validate a BST (min/max bounds)

boolean isValidBST(TreeNode root) {
    return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
// every value in this subtree must be strictly between low and high
boolean valid(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return valid(node.left, low, node.val)       // left: tighten upper bound
        && valid(node.right, node.val, high);    // right: tighten lower bound
}

Why it works: checking only left.val < node.val < right.val is the classic wrong answer. The tree 5 → right 6 → left 4 passes that local check, but 4 sits in the right subtree of 5, so it is invalid (our code returns false). Passing down the allowed range catches it: when you go left, the current value becomes the new upper limit; going right, it becomes the new lower limit. long bounds make a node holding Integer.MAX_VALUE work. O(n) time, O(h) space.

Problem 2 — Kth smallest element

int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        if (--k == 0) return cur.val;     // k-th node in sorted order
        cur = cur.right;
    }
    throw new IllegalArgumentException("k is larger than the tree");
}   // sample BST, k = 3 -> 4

Why it works: iterative inorder produces values in sorted order, so the kth pop is the kth smallest. It stops early: O(h + k) time, O(h) space. Follow-up "the tree changes often and kth is asked often": store a subtree size in each node, then pick left or right by comparing k to the left size — O(h) per query.

Problem 3 — Lowest common ancestor in a BST

TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode cur = root;
    while (cur != null) {
        if (p.val < cur.val && q.val < cur.val) cur = cur.left;        // both left
        else if (p.val > cur.val && q.val > cur.val) cur = cur.right;  // both right
        else return cur;                                               // they split here
    }
    return null;
}   // sample BST: lca(4,7)=6, lca(1,7)=3, lca(13,10)=10

Why it works: while both values are on the same side, the LCA must be on that side too. The first node where they split (or one of them equals the node) is the LCA. Uses the ordering, so it is O(h) time and O(1) space — better than the O(n) general-tree version in section 12.

Problem 4 — Convert a sorted array to a balanced BST

TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
TreeNode build(int[] nums, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2;          // middle element becomes the root
    TreeNode node = new TreeNode(nums[mid]);
    node.left = build(nums, lo, mid - 1);
    node.right = build(nums, mid + 1, hi);
    return node;
}   // [1..7] -> root 4, height 3 (in nodes)

Why it works: picking the middle puts half the values on each side, so the two subtree sizes differ by at most one at every level — the tree is height-balanced. Everything left of mid is smaller, everything right is larger, so the BST rule holds. O(n) time, O(log n) recursion space.

When to use a BST, and pitfalls

• Use an (always balanced) BST when you need order: sorted iteration, min/max, "next larger than x", range queries. If you only need lookup by exact key, a HashMap is faster (O(1)).
• Pitfall: validating with parent-child comparisons only (see Problem 1).
• Pitfall: forgetting to assign the return value — insert(root.left, key) without root.left = loses the new node.
• Pitfall: duplicates. Decide a rule up front (ignore, count field, or always go right) and say it out loud.
• Pitfall: assuming O(log n) for a plain BST. It is O(h), and h can be n.

14. Balanced Trees & TreeMap

Why balance matters

Every BST operation costs O(height). With n = 1,000,000 keys a balanced tree has height about 20; a degenerate one has height 1,000,000. Balanced trees keep a small invariant (a rule that is always true) that forces the height to stay O(log n), and they restore the rule after each change using rotations.

Rotations — the one move every balanced tree uses

A rotation changes which node is the parent in a small group of nodes, without breaking the BST order. In a right rotation, the left child x moves up and its old parent y moves down to the right. The middle subtree B (values between x and y) switches from x's right to y's left. Only three links change, so a rotation is O(1).

AVL trees in easy words

An AVL tree (named after its inventors Adelson-Velsky and Landis) stores a height in each node and keeps this rule: at every node, the left and right subtree heights differ by at most 1. The difference is called the balance factor. After an insert, walk back up; the first node whose balance factor becomes +2 or −2 is fixed with one of four cases:

class Node {
    int key, height = 1;
    Node left, right;
    Node(int k) { key = k; }
}
int h(Node n) { return n == null ? 0 : n.height; }
void update(Node n) { n.height = 1 + Math.max(h(n.left), h(n.right)); }
int balance(Node n) { return h(n.left) - h(n.right); }

Node rotateRight(Node y) {
    Node x = y.left;
    Node b = x.right;
    x.right = y;          // y comes down to the right
    y.left = b;           // B changes parent (still between x and y)
    update(y);            // y is now lower: update it first
    update(x);
    return x;             // new root of this subtree
}
Node rotateLeft(Node x) {
    Node y = x.right;
    Node b = y.left;
    y.left = x;
    x.right = b;
    update(x);
    update(y);
    return y;
}

Node insert(Node node, int key) {
    if (node == null) return new Node(key);
    if (key < node.key) node.left = insert(node.left, key);
    else if (key > node.key) node.right = insert(node.right, key);
    else return node;
    update(node);
    int bal = balance(node);
    if (bal > 1 && key < node.left.key) return rotateRight(node);             // LL
    if (bal < -1 && key > node.right.key) return rotateLeft(node);            // RR
    if (bal > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }   // LR
    if (bal < -1) { node.right = rotateRight(node.right); return rotateLeft(node); } // RL
    return node;
}   // inserting 1..7 in order gives root 4, height 3 (not 7)

Insert is O(log n): one walk down, one walk up, at most two rotations. You are unlikely to be asked for this code, but "explain how AVL fixes itself" is a fair question.

Red-black trees in easy words

A red-black tree paints each node red or black and keeps these rules:

1. Every node is red or black; the root is black.
2. Null leaves count as black.
3. No red node has a red child (no two reds in a row).
4. Every path from a node down to a null leaf passes the same number of black nodes (the "black height").

Why that keeps it balanced: the shortest possible path is all black; the longest alternates red and black. Rule 4 says both have the same number of blacks, and rule 3 says reds cannot pile up, so the longest path is at most twice the shortest. Height is at most 2 log₂(n + 1). On insert the new node is red; if that breaks rule 3, the tree fixes it by recolouring and at most two rotations.

B-trees — why databases use them

A B-tree is a balanced search tree where each node holds many sorted keys (often hundreds) and has one more child than keys. All leaves sit at the same depth. A B+ tree, used by MySQL InnoDB and PostgreSQL indexes, keeps all real data in the leaves and links the leaves together for fast range scans.

The reason is the disk. Reading from disk or SSD happens in pages (for example 16 KB in InnoDB), and each page read is thousands of times slower than a memory access. A binary tree with a billion keys is about 30 levels deep — 30 page reads. A B-tree with ~500 keys per node reaches a billion keys in about 4 levels, and the top levels stay cached in memory, so a lookup often needs just 1–2 real disk reads. Same O(log n) in theory; a much smaller log base in practice.

Java TreeMap and TreeSet API

TreeMap<K,V> keeps keys sorted (natural order or a Comparator). TreeSet<E> is the same thing with only keys. Both implement NavigableMap/NavigableSet, which adds the "nearest key" methods that make them useful.

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "a"); map.put(20, "b"); map.put(30, "c"); map.put(40, "d");

map.floorKey(25);      // 20   largest key <= 25
map.ceilingKey(25);    // 30   smallest key >= 25
map.floorKey(20);      // 20   "or equal" methods include the key itself
map.lowerKey(20);      // 10   strictly less
map.higherKey(20);     // 30   strictly greater
map.floorKey(5);       // null nothing <= 5, always null-check
map.firstKey();        // 10
map.lastKey();         // 40
map.headMap(30);       // {10=a, 20=b}         keys < 30
map.tailMap(30);       // {30=c, 40=d}         keys >= 30
map.subMap(15, 35);    // {20=b, 30=c}         15 <= key < 35
map.subMap(20, true, 40, true);  // {20=b, 30=c, 40=d}  both ends inclusive
map.descendingMap();   // {40=d, 30=c, 20=b, 10=a}
map.pollFirstEntry();  // removes and returns 10=a

TreeSet<Integer> set = new TreeSet<>(List.of(5, 1, 9, 3));   // [1, 3, 5, 9]
set.floor(4);          // 3
set.higher(5);         // 9
set.pollFirst();       // 1 (removed)
set.pollLast();        // 9 (removed) -> set is now [3, 5]

Memory aid: floor/ceiling include equal, lower/higher do not. Methods ending in Key return just the key; the Entry versions (floorEntry, ceilingEntry) return key and value. headMap/subMap return live views, not copies, and cost O(log n) to create.

Operations complexity

When to use: reach for TreeMap when a problem says "closest", "next bigger", "previous smaller", "in a range", "sorted while changing", or needs both min and max with deletes of arbitrary elements (a heap cannot remove an arbitrary element fast; a TreeMap of counts can).

Problem 1 — My Calendar I (booking overlap)

Book an event [start, end) only if it does not overlap an existing booking.

class MyCalendar {
    private final TreeMap<Integer, Integer> bookings = new TreeMap<>(); // start -> end

    public boolean book(int start, int end) {           // half-open [start, end)
        Integer prevStart = bookings.floorKey(start);    // latest booking starting at or before start
        if (prevStart != null && bookings.get(prevStart) > start) return false;
        Integer nextStart = bookings.ceilingKey(start);  // earliest booking starting at or after start
        if (nextStart != null && nextStart < end) return false;
        bookings.put(start, end);
        return true;
    }
}
// book(10,20)=true, book(15,25)=false, book(20,30)=true, book(5,10)=true, book(5,11)=false

Why it works: the bookings never overlap, so sorted by start they are also sorted by end. Only two bookings can possibly clash with the new one: the one just before it (does it end after we start?) and the one just after it (does it start before we end?). floorKey and ceilingKey find both in O(log n), so each book is O(log n) and space is O(n). A list scan would be O(n) per call.

Problem 2 — Contains Duplicate III

Are there indices i != j with |i − j| <= indexDiff and |nums[i] − nums[j]| <= valueDiff?

boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
    TreeSet<Long> window = new TreeSet<>();
    for (int i = 0; i < nums.length; i++) {
        long x = nums[i];
        Long ceil = window.ceiling(x - valueDiff);     // smallest value >= x - valueDiff
        if (ceil != null && ceil <= x + valueDiff) return true;
        window.add(x);
        if (i >= indexDiff) window.remove((long) nums[i - indexDiff]); // keep last indexDiff values
    }
    return false;
}
// [1,2,3,1], 3, 0 -> true     [1,5,9,1,5,9], 2, 3 -> false

Why it works: a sliding window keeps only the last indexDiff values, which handles the index condition. For the value condition we need "is any value in [x − valueDiff, x + valueDiff]?" — ceiling(x − valueDiff) returns the smallest candidate in that range, and if even that one is above x + valueDiff, none fits. Using long avoids overflow when values are near Integer.MAX_VALUE. Time O(n log k), space O(k) where k = indexDiff. (A bucket approach reaches O(n), but the TreeSet version is what most interviewers expect first.)

Problem 3 — Stock Price Fluctuation

Updates arrive as (timestamp, price) and may correct an earlier timestamp. Support current(), maximum(), minimum().

class StockPrice {
    private final Map<Integer, Integer> priceAt = new HashMap<>();      // timestamp -> price
    private final TreeMap<Integer, Integer> count = new TreeMap<>();    // price -> how many timestamps
    private int latest = 0;

    public void update(int timestamp, int price) {
        Integer old = priceAt.put(timestamp, price);
        if (old != null) {                                  // correction: remove old price once
            if (count.merge(old, -1, Integer::sum) == 0) count.remove(old);
        }
        count.merge(price, 1, Integer::sum);
        latest = Math.max(latest, timestamp);
    }
    public int current() { return priceAt.get(latest); }
    public int maximum() { return count.lastKey(); }
    public int minimum() { return count.firstKey(); }
}
// update(1,10), update(2,5): current 5, max 10
// update(1,3) corrects t=1: max 5.  update(4,2): min 2, current 2

Why it works: the hard part is corrections: the old price must disappear from the max/min structure. A TreeMap used as a multiset (value to count) removes one copy of any price in O(log n) and gives min and max as firstKey/lastKey. Update is O(log n), current is O(1), max/min are O(log n). The alternative — two heaps with lazy deletion (pop stale tops whose price no longer matches) — also works but is harder to get right.

Pitfalls

• floorKey and friends return null, not an exception, when nothing qualifies. Store the result in an Integer, not an int, or auto-unboxing throws NullPointerException.
• TreeSet is a set: duplicates are silently dropped. Use a TreeMap<value, count> as a multiset.
• A Comparator that returns 0 for different objects makes the tree treat them as equal — one of them vanishes. Break ties (for example by id).
• Comparing boxed Integer keys with == only works for small values (-128 to 127 are cached). Use equals or unbox.
• Modifying the map while iterating over it (other than through the iterator) throws ConcurrentModificationException.

15. Tries

Node design: array vs map

In interviews, use the array unless the problem says the characters can be anything.

Implementation — insert, search, startsWith

class Trie {
    private static class Node {
        Node[] children = new Node[26];   // one slot per letter 'a'..'z'
        boolean isEnd;                    // a word ends here
    }
    private final Node root = new Node();

    public void insert(String word) {
        Node cur = root;
        for (char c : word.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 word) {
        Node n = walk(word);
        return n != null && n.isEnd;       // path exists AND a word ends here
    }
    public boolean startsWith(String prefix) {
        return walk(prefix) != null;       // path exists is enough
    }
    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;
    }
}
// insert("apple"): search("apple")=true, search("app")=false, startsWith("app")=true
// insert("app"):   search("app")=true

The map version only changes two lines — cur = cur.children.computeIfAbsent(c, k -> new Node()) on insert and cur = cur.children.get(c) on lookup.

Operations complexity (L = length of the word or prefix)

A trie does not beat a HashSet for exact lookups, and it uses more memory. Pick it when the problem is about prefixes, or when you search for many words at once while walking a structure (a grid, a stream of characters) and want to stop as soon as no word can match.

Problem 1 — Implement Trie

That is the class above. Every operation is O(L) time; insert uses O(L) new space in the worst case. Why it works: a path from the root spells a prefix, and the isEnd flag separates "a stored word" from "only a prefix of a stored word".

Problem 2 — Word Search II (the idea, plus code)

Given a letter grid and a list of words, find all words that can be traced through adjacent cells. Running a separate grid search for each word is too slow. Instead, put all words in a trie and run one DFS from each cell, walking the grid and the trie together. The moment the current path is not a prefix of any word, stop.

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        String word;                      // set on the node where a word ends
    }
    public List<String> findWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node cur = root;
            for (char c : w.toCharArray()) {
                if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
                cur = cur.next[c - 'a'];
            }
            cur.word = w;
        }
        List<String> found = new ArrayList<>();
        for (int r = 0; r < board.length; r++)
            for (int c = 0; c < board[0].length; c++)
                dfs(board, r, c, root, found);
        return found;
    }
    private void dfs(char[][] b, int r, int c, Node parent, List<String> found) {
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length) return;
        char ch = b[r][c];
        if (ch == '#' || parent.next[ch - 'a'] == null) return;  // visited, or no word has this prefix
        Node node = parent.next[ch - 'a'];
        if (node.word != null) {
            found.add(node.word);
            node.word = null;                 // report each word once
        }
        b[r][c] = '#';                        // mark visited
        dfs(b, r + 1, c, node, found);
        dfs(b, r - 1, c, node, found);
        dfs(b, r, c + 1, node, found);
        dfs(b, r, c - 1, node, found);
        b[r][c] = ch;                         // restore (backtrack)
    }
}
// board oaan/etae/ihkr/iflv, words [oath, pea, eat, rain] -> [oath, eat]

Why it works: the trie shares work between words with the same prefix and prunes dead paths immediately. Time is O(R · C · 4 · 3^L−1) in the worst case (L = longest word; after the first step each cell has at most 3 unvisited neighbours), but pruning makes it far faster in practice. Space O(total letters in words) for the trie plus O(L) recursion. Clearing node.word avoids duplicates without a Set.

Problem 3 — Autocomplete / search suggestions

After each typed character of searchWord, return up to three product names with that prefix, in lexicographic order.

List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Arrays.sort(products);                    // insert in sorted order
    Node root = new Node();                   // Node { Node[] next = new Node[26]; List<String> top = new ArrayList<>(); }
    for (String p : products) {
        Node cur = root;
        for (char c : p.toCharArray()) {
            if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
            cur = cur.next[c - 'a'];
            if (cur.top.size() < 3) cur.top.add(p);  // first 3 seen are the 3 smallest
        }
    }
    List<List<String>> result = new ArrayList<>();
    Node cur = root;
    for (char c : searchWord.toCharArray()) {
        cur = (cur == null) ? null : cur.next[c - 'a'];
        result.add(cur == null ? List.of() : cur.top);
    }
    return result;
}
// products [mobile, mouse, moneypot, monitor, mousepad], "mouse" ->
// [[mobile, moneypot, monitor], [mobile, moneypot, monitor],
//  [mouse, mousepad], [mouse, mousepad], [mouse, mousepad]]

Why it works: because products are inserted in sorted order, the first three that pass through a node are the three smallest with that prefix, so each node can cache its answer. Build is O(n log n · L) for the sort plus O(total characters) for the trie; each keystroke is then O(1). Space O(total characters) nodes plus up to 3 references per node. Once a prefix has no match, every longer prefix returns an empty list. (A sorted array plus binary search for the prefix also works and uses less memory.)

Problem 4 — Longest word in dictionary

Find the longest word that can be built one character at a time by other words in the list (for "world", the words w, wo, wor, worl must all exist). Ties go to the lexicographically smallest.

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        String word;
    }
    private String best = "";
    public String longestWord(String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node cur = root;
            for (char c : w.toCharArray()) {
                if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
                cur = cur.next[c - 'a'];
            }
            cur.word = w;
        }
        dfs(root);
        return best;
    }
    // only step into children that are complete words themselves
    private void dfs(Node node) {
        for (Node child : node.next) {          // 'a'..'z' order = lexicographic
            if (child != null && child.word != null) {
                if (child.word.length() > best.length()) best = child.word;
                dfs(child);
            }
        }
    }
}
// [a, banana, app, appl, ap, apply, apple] -> "apple"  (apply is equally long but larger)

Why it works: "buildable one letter at a time" means every node on the path is a word end. So the DFS only walks through word-end nodes. Visiting children in a..z order and replacing best only when strictly longer keeps the smallest word on ties. O(total characters) time and space.

Problem 5 — Maximum XOR of two numbers (bit trie)

A trie over bits instead of letters: each number becomes a 31-step path from the highest bit to the lowest, and each node has two children, for bit 0 and bit 1.

int findMaximumXOR(int[] nums) {
    int[][] next = new int[nums.length * 31 + 1][2];  // node -> child for bit 0 / 1 (0 = none)
    int count = 1;                                     // node 0 is the root
    int best = 0;
    for (int x : nums) {
        // insert x, bit 30 down to bit 0
        int cur = 0;
        for (int b = 30; b >= 0; b--) {
            int bit = (x >> b) & 1;
            if (next[cur][bit] == 0) next[cur][bit] = count++;
            cur = next[cur][bit];
        }
        // query: greedily take the opposite bit when possible
        cur = 0;
        int xor = 0;
        for (int b = 30; b >= 0; b--) {
            int bit = (x >> b) & 1;
            int want = bit ^ 1;
            if (next[cur][want] != 0) {
                xor |= (1 << b);
                cur = next[cur][want];
            } else {
                cur = next[cur][bit];
            }
        }
        best = Math.max(best, xor);
    }
    return best;
}
// [3, 10, 5, 25, 2, 8] -> 28   (5 XOR 25)

Why it works: XOR puts a 1 wherever the bits differ, and a 1 in a higher bit is worth more than all lower bits combined (2^b > 2^b − 1). So for each number, walk from the top bit and take the opposite branch whenever it exists — a greedy choice that is always right. Inserting before querying is safe: a number XOR itself is 0, which never beats a real pair. O(31 · n) = O(n) time, O(31 · n) space. Storing nodes in an int[][] instead of objects is faster and a common trick.

Pitfalls

• Forgetting isEnd: then search("app") wrongly returns true after inserting "apple".
• c - 'a' assumes lowercase letters only. Uppercase or digits give negative or out-of-range indices.
• Memory: 26 references × 8 bytes per node adds up fast with a million words. Mention the map or a compressed trie (radix tree, which merges single-child chains) if memory matters.
• In Word Search II, forgetting to restore the cell after the DFS, or reporting the same word twice.

16. Graphs & Traversal

Terminology

We write V for the number of vertices and E for the number of edges. Graph complexities are stated in both, like O(V + E).

Representations

In Java the usual adjacency list is List<List<Integer>> when nodes are 0..n−1, or Map<String, List<String>> when nodes have names. For weighted graphs store int[]{neighbour, weight} pairs.

List<List<Integer>> buildGraph(int n, int[][] edges) {
    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]);   // undirected: add both directions
    }
    return adj;
}   // edges above -> [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3], [6], [5]]

BFS template — and shortest paths in unweighted graphs

// BFS: shortest number of edges from src to every node (-1 = unreachable)
int[] bfs(List<List<Integer>> adj, int src) {
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, -1);                 // -1 doubles as "not visited"
    Queue<Integer> queue = new ArrayDeque<>();
    dist[src] = 0;
    queue.offer(src);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {           // mark when ADDING, not when polling
                dist[v] = dist[u] + 1;
                queue.offer(v);
            }
        }
    }
    return dist;
}   // from 0: [0, 1, 1, 2, 3, -1, -1]

Why BFS gives shortest paths: the queue processes nodes in order of distance — all distance-1 nodes, then all distance-2 nodes, and so on. The first time a node is reached is therefore by a shortest route. This only holds when every edge costs the same; with weights, use Dijkstra (a later section). Time O(V + E): each node enters the queue once and each edge is looked at twice (once from each end). Space O(V).

DFS — recursive and iterative

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

List<Integer> dfsIterative(List<List<Integer>> adj, int src) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(src);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;          // may be pushed more than once
        visited[u] = true;
        order.add(u);
        List<Integer> nbrs = adj.get(u);
        for (int i = nbrs.size() - 1; i >= 0; i--) {   // reverse: same order as recursive
            if (!visited[nbrs.get(i)]) stack.push(nbrs.get(i));
        }
    }
    return order;
}   // both give [0, 1, 3, 2, 4] from node 0

Both are O(V + E) time and O(V) space. Recursive DFS is shorter; iterative DFS avoids StackOverflowError on long paths (Java's default stack handles roughly 10,000 deep calls, fewer with big frames).

Visited handling — the rules that prevent bugs

• BFS: mark when you add to the queue, not when you remove. Otherwise the same node can be added many times by different neighbours before it is processed — correct answer, but wasted work, and in dense graphs it can blow up memory.
• Iterative DFS: mark when you pop and skip already-visited pops (as above) if you want true DFS order.
• Use a boolean[] for numbered nodes, a HashSet for named nodes, or change the input in place (set a grid cell to '0' or '#') if you are allowed to.
• For a graph that may be disconnected, loop over every node and start a new search from each unvisited one.

Connected components and cycle detection (undirected)

The number of connected components is the number of times the outer loop finds an unvisited node. For cycles in an undirected graph, DFS finds one if it reaches an already-visited node that is not the node it just came from (its parent). Going back along the same edge does not count as a cycle.

boolean hasCycle(List<List<Integer>> adj) {
    boolean[] visited = new boolean[adj.size()];
    for (int i = 0; i < adj.size(); i++) {
        if (!visited[i] && cycleDfs(adj, i, -1, visited)) return true;
    }
    return false;
}
boolean cycleDfs(List<List<Integer>> adj, int u, int parent, boolean[] visited) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) {
            if (cycleDfs(adj, v, u, visited)) return true;
        } else if (v != parent) {
            return true;                   // reached an already-seen node another way
        }
    }
    return false;
}   // sample graph: true (0-1-3-2-0).  Tree 0-1, 1-2, 1-3: false

O(V + E). Directed graphs need a different test — the parent trick is wrong there, and you need three states (unvisited, in the current path, done) or Kahn's algorithm. That is covered in the topological sort section. Union-Find (section 17) is another way to detect cycles in undirected graphs.

Bipartite means the nodes can be split into two groups so every edge crosses between the groups. Colour the start node, give each neighbour the opposite colour, and fail if an edge ever joins two nodes of the same colour. A graph is bipartite exactly when it has no odd-length cycle.

Operations complexity

BFS or DFS? BFS for shortest path in steps, "minimum number of moves", or anything spreading level by level. DFS for "explore everything", connectivity, cycle detection, topological order, backtracking over paths. For simple counting (components, islands), both work.

Problem 1 — Number of connected components

int countComponents(int n, int[][] edges) {
    List<List<Integer>> adj = buildGraph(n, edges);
    boolean[] visited = new boolean[n];
    int components = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            components++;                  // new unvisited node = new component
            dfs(adj, i, visited, new ArrayList<>());
        }
    }
    return components;
}   // n=5, edges [[0,1],[1,2],[3,4]] -> 2

Why it works: one DFS marks exactly one whole component. So every time the loop meets an unvisited node, it has found a component nobody has touched yet. O(V + E) time and space. Number of Islands is the same idea on a grid.

Problem 2 — Clone graph

Node cloneGraph(Node node) {                   // Node { int val; List<Node> neighbors; }
    if (node == null) return null;
    Map<Node, Node> copies = new HashMap<>();   // original -> clone (also "visited")
    Queue<Node> queue = new ArrayDeque<>();
    copies.put(node, new Node(node.val));
    queue.offer(node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        for (Node nb : cur.neighbors) {
            if (!copies.containsKey(nb)) {
                copies.put(nb, new Node(nb.val));
                queue.offer(nb);
            }
            copies.get(cur).neighbors.add(copies.get(nb));  // wire clone edge
        }
    }
    return copies.get(node);
}

Why it works: the map does two jobs: it is the visited set, and it lets every edge find the clone of its other end, even if that clone was created earlier. Without it, a cycle (1–2–3–4–1) would be copied forever. O(V + E) time, O(V) space.

Problem 3 — Is graph bipartite?

boolean isBipartite(int[][] graph) {
    int n = graph.length;
    int[] color = new int[n];                 // 0 = uncoloured, 1 / -1 = the two sides
    for (int start = 0; start < n; start++) {
        if (color[start] != 0) continue;      // graph may be disconnected
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        color[start] = 1;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph[u]) {
                if (color[v] == 0) {
                    color[v] = -color[u];     // neighbour gets the other side
                    queue.offer(v);
                } else if (color[v] == color[u]) {
                    return false;             // edge inside one side
                }
            }
        }
    }
    return true;
}   // square 0-1-2-3-0: true.  Square plus diagonal 0-2: false (triangle)

Why it works: within a component, once the start's colour is chosen every other colour is forced — a neighbour must be on the other side. So if a forced colouring ever conflicts, no valid split exists. O(V + E) time, O(V) space.

Problem 4 — Rotting oranges (multi-source BFS)

Grid: 0 empty, 1 fresh, 2 rotten. Every minute, rotten oranges rot their 4 neighbours. Minutes until none are fresh, or −1 if impossible.

int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new ArrayDeque<>();
    int fresh = 0;
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 2) queue.offer(new int[]{r, c});   // ALL sources start together
            else if (grid[r][c] == 1) fresh++;
        }
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int minutes = 0;
    while (!queue.isEmpty() && fresh > 0) {
        int size = queue.size();                  // one level = one minute
        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;             // rot it = mark visited
                    fresh--;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}   // [[2,1,1],[1,1,0],[0,1,1]] -> 4    [[2,1,1],[0,1,1],[1,0,1]] -> -1

Why it works: putting every rotten orange in the queue at the start is like adding one imaginary "super source" joined to all of them. BFS levels then equal minutes, and each fresh orange is reached at its distance to the nearest rotten one. Running a separate BFS per rotten orange would be O((R·C)²); this is O(R · C) time and space. The fresh > 0 check stops the count from adding an extra minute at the end.

Problem 5 — Word ladder

Fewest words in a transformation from beginWord to endWord, changing one letter at a time, where every word must be in the list.

int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) return 0;
    Queue<String> queue = new ArrayDeque<>();
    queue.offer(beginWord);
    dict.remove(beginWord);
    int steps = 1;                                  // counts words, not edges
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            char[] w = queue.poll().toCharArray();
            for (int j = 0; j < w.length; j++) {
                char original = w[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    w[j] = c;
                    String next = new String(w);
                    if (next.equals(endWord)) return steps + 1;
                    if (dict.remove(next)) queue.offer(next);   // remove = mark visited
                }
                w[j] = original;
            }
        }
        steps++;
    }
    return 0;
}   // hit -> cog with [hot,dot,dog,lot,log,cog]: 5 (hit hot dot dog cog)

Why it works: it is an unweighted shortest-path problem on an implicit graph: words are nodes, and two words are joined if they differ by one letter. Instead of comparing every pair of words (O(N² · L)), generate the 25 · L possible neighbours of each word and check them in the set. Removing a word from the set when it is queued marks it visited. Time O(N · L · 26 · L) (the last L is building each string), space O(N · L). Bidirectional BFS (search from both ends and meet in the middle) is the usual follow-up speed-up.

Pitfalls

• Forgetting the visited set: infinite loop on any cycle.
• Marking visited on poll in BFS: duplicates in the queue.
• Forgetting disconnected parts: always loop over all nodes when the question is about the whole graph.
• Undirected edge added only one way when building the adjacency list.
• Using the parent trick for cycle detection when the input has duplicate edges (u–v twice): the second copy is a real 2-cycle that the parent check hides. Check the problem statement.
• Using BFS for shortest path on a weighted graph — it gives the fewest edges, not the lowest total weight.

17. Union-Find (Disjoint Set)

How it is stored

Just two integer arrays. parent[i] is i's parent (a root has parent[i] == i). size[i] (or rank[i]) is only meaningful at a root, and records how big that tree is. No objects, no pointers — which is why it is so fast in practice.

The two tricks that make it fast

• Union by size (or rank) — when merging, attach the smaller tree under the root of the larger one. A node only gets deeper when its tree at least doubles in size, so no tree gets taller than log₂ n. Rank is the same idea using an upper bound on height instead of size.
• Path compression — during find, after you discover the root, make every node you passed point directly at the root. The next find on any of them is one step.

Full Java class

class UnionFind {
    private final int[] parent;
    private final int[] size;      // size of the tree, valid only at roots
    private int components;

    UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;         // everyone starts as their own leader
            size[i] = 1;
        }
    }

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

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                 // already in the same set
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;                            // attach smaller under larger
        size[ra] += size[rb];
        components--;
        return true;
    }

    boolean connected(int a, int b) { return find(a) == find(b); }
    int components() { return components; }
    int sizeOf(int x) { return size[find(x)]; }
}
// n=6; union(0,1), union(1,2), union(3,4):
// connected(0,2)=true, connected(0,3)=false, components()=3, sizeOf(2)=3, union(0,2)=false

Returning a boolean from union is a small design choice that pays off: "false" means the two were already connected, which is exactly the signal for cycle detection. Keeping a components counter answers "how many groups?" in O(1).

The recursive find can go deep before the first compression. If that worries you, use the iterative path halving version, which makes each node point to its grandparent as it walks:

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];   // point to grandparent: halves the path
        x = parent[x];
    }
    return x;
}   // chain parent=[0,0,1,2,3]: find(4) = 0, parent becomes [0, 0, 0, 2, 2]

Near O(1): the inverse Ackermann function in easy words

With both tricks, a sequence of m operations on n items costs O(m · α(n)). α (alpha) is the inverse Ackermann function. The Ackermann function grows unbelievably fast, so its inverse grows unbelievably slowly: α(n) is at most 4 for any n you could ever store — even n equal to the number of atoms in the universe. So in practice each operation is constant time; you say "amortized nearly O(1)" in an interview.

When to use Union-Find

• Connectivity questions where edges arrive over time (online): "after each new link, how many groups?" DFS would have to restart each time; Union-Find just merges.
• Cycle detection in an undirected graph, and Kruskal's minimum spanning tree (add cheapest edges that do not form a cycle).
• Grouping things by a shared attribute (same email, similar strings, equal variables in equations).
• Not a fit when you need to split groups (it only merges), or need the actual path between two nodes (use BFS/DFS).

Problem 1 — Number of provinces

isConnected[i][j] = 1 means city i and city j are directly connected. Count the groups of connected cities.

int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    UnionFind uf = new UnionFind(n);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)          // matrix is symmetric: upper half only
            if (isConnected[i][j] == 1) uf.union(i, j);
    return uf.components();
}   // [[1,1,0],[1,1,0],[0,0,1]] -> 2

Why it works: start with n groups; every successful union merges two groups into one, so the counter ends at the number of connected groups. O(n² · α(n)) time because the input is an n × n matrix, O(n) extra space. A DFS over the matrix works equally well here.

Problem 2 — Redundant connection

A tree with n nodes had one extra edge added. Return the edge that can be removed to make it a tree again (the last such edge in the input).

int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);   // nodes are 1..n
    for (int[] e : edges) {
        if (!uf.union(e[0], e[1])) return e;   // already connected: this edge closes a cycle
    }
    return new int[0];
}   // [[1,2],[1,3],[2,3]] -> [2, 3]     [[1,2],[2,3],[3,4],[1,4],[1,5]] -> [1, 4]

Why it works: if both ends of an edge are already in the same group, there was already a path between them, so this edge creates a cycle. Processing in input order means the first such edge is the last one of the cycle in the list — the one the problem wants. O(n · α(n)) time, O(n) space.

Problem 3 — Accounts merge

Each account is a name followed by emails. Two accounts belong to the same person if they share any email. Merge them and return each person's emails sorted.

List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, Integer> emailId = new HashMap<>();    // email -> first account index
    UnionFind uf = new UnionFind(accounts.size());
    for (int i = 0; i < accounts.size(); i++) {
        List<String> acc = accounts.get(i);
        for (int j = 1; j < acc.size(); j++) {
            Integer owner = emailId.putIfAbsent(acc.get(j), i);
            if (owner != null) uf.union(i, owner);     // shared email: same person
        }
    }
    Map<Integer, TreeSet<String>> groups = new HashMap<>();  // root -> sorted emails
    for (Map.Entry<String, Integer> e : emailId.entrySet()) {
        groups.computeIfAbsent(uf.find(e.getValue()), k -> new TreeSet<>()).add(e.getKey());
    }
    List<List<String>> result = new ArrayList<>();
    for (Map.Entry<Integer, TreeSet<String>> g : groups.entrySet()) {
        List<String> merged = new ArrayList<>();
        merged.add(accounts.get(g.getKey()).get(0));   // name
        merged.addAll(g.getValue());
        result.add(merged);
    }
    return result;
}
// [John: johnsmith, john_newyork] [John: johnsmith, john00] [Mary: mary] [John: johnnybravo]
// -> [John, john00@mail.com, john_newyork@mail.com, johnsmith@mail.com],
//    [John, johnnybravo@mail.com], [Mary, mary@mail.com]   (group order may vary)

Why it works: the union-find nodes are accounts. The first account to mention an email "owns" it; any later account with the same email is unioned with the owner. Afterwards, each email is filed under its owner's root, and the TreeSet sorts the emails. Two accounts with the same name but no shared email (the two Johns) correctly stay separate. Time O(E log E) where E is the total number of emails (the sort dominates), space O(E).

Problem 4 — Number of islands II (the idea)

An m × n grid starts as all water. Land is added one cell at a time; after each addition report the number of islands. Re-running a flood fill after every addition would cost O(m · n) each time. With Union-Find: the new cell becomes its own island (+1), then union it with each land neighbour; every union that actually merges two different sets is −1.

List<Integer> numIslands2(int m, int n, int[][] positions) {
    UnionFind uf = new UnionFind(m * n);
    boolean[] land = new boolean[m * n];
    int islands = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    List<Integer> result = new ArrayList<>();
    for (int[] p : positions) {
        int id = p[0] * n + p[1];                 // 2D cell -> 1D index
        if (!land[id]) {
            land[id] = true;
            islands++;                            // new land starts as its own island
            for (int[] d : dirs) {
                int r = p[0] + d[0], c = p[1] + d[1];
                int nid = r * n + c;
                if (r >= 0 && c >= 0 && r < m && c < n && land[nid] && uf.union(id, nid)) {
                    islands--;                    // merged two islands into one
                }
            }
        }
        result.add(islands);
    }
    return result;
}   // 3x3, add (0,0),(0,1),(1,2),(2,1),(1,1) -> [1, 1, 2, 3, 1]

Why it works: the last cell (1,1) touches three separate islands; it adds 1 and then merges three times, so 3 + 1 − 3 = 1. Each addition is O(α(mn)), so k additions cost O(m · n + k · α(mn)) including setup; space O(m · n). The !land[id] check handles the same cell being added twice. Mapping (row, col) to row * n + col is the standard way to put a grid into a DSU.

Pitfalls

• Comparing parent[a] == parent[b] instead of find(a) == find(b). Only roots identify a group.
• Linking parent[a] = b instead of linking the roots: parent[find(a)] = find(b).
• Reading size[x] for a non-root. Always use size[find(x)].
• Off-by-one when nodes are numbered 1..n: allocate n + 1.
• Forgetting that Union-Find cannot undo a union or remove an item (unless you use the advanced "rollback" variant without path compression).

18. Segment Trees & Fenwick Trees

The problem: prefix sums break with updates

A prefix sum array (section on arrays) answers any range sum in O(1): sum(l, r) = prefix[r + 1] − prefix[l]. But change one element and every prefix after it is wrong — fixing them is O(n). The plain array has the opposite problem: O(1) updates but O(n) range sums.

With q mixed updates and queries, both trees cost O(q log n) in total instead of O(q · n). When you see "update" and "range sum/min/max" in the same problem, think of these two.

Segment tree shape

Like a heap, the tree is stored in a flat array: node k has children 2k and 2k + 1. Allocating 4 * n slots is always enough, even when n is not a power of two.

Segment tree — build, update, query

class SegmentTree {
    private final int n;
    private final int[] tree;          // tree[node] = sum of its range

    SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];         // 4n is always enough
        build(nums, 1, 0, n - 1);
    }
    // node covers nums[lo..hi]; children are 2*node and 2*node+1
    private void build(int[] nums, int node, int lo, int hi) {
        if (lo == hi) { tree[node] = nums[lo]; return; }
        int mid = (lo + hi) / 2;
        build(nums, 2 * node, lo, mid);
        build(nums, 2 * node + 1, mid + 1, hi);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void update(int index, int value) { update(1, 0, n - 1, index, value); }
    private void update(int node, int lo, int hi, int index, int value) {
        if (lo == hi) { tree[node] = value; return; }
        int mid = (lo + hi) / 2;
        if (index <= mid) update(2 * node, lo, mid, index, value);
        else update(2 * node + 1, mid + 1, hi, index, value);
        tree[node] = tree[2 * node] + tree[2 * node + 1];   // fix sums on the way up
    }

    int query(int left, int right) { return query(1, 0, n - 1, left, right); }
    private int query(int node, int lo, int hi, int left, int right) {
        if (right < lo || hi < left) return 0;              // no overlap
        if (left <= lo && hi <= right) return tree[node];   // fully inside: use stored sum
        int mid = (lo + hi) / 2;                            // partial overlap: ask both kids
        return query(2 * node, lo, mid, left, right)
             + query(2 * node + 1, mid + 1, hi, left, right);
    }
}
// [2, 1, 5, 3, 4]: query(1, 3) = 9; update(2, 10); query(1, 3) = 14, query(0, 4) = 20

Why a query is O(log n): the three cases — no overlap (return the neutral value), full overlap (return the stored answer), partial overlap (split) — mean that on each level at most two nodes are partially overlapping and keep splitting. Build visits each of the ~2n nodes once: O(n). Update changes one leaf and its log n ancestors.

To answer min or max instead of sum, change the combine step (+ to Math.min) and the "no overlap" value (0 to Integer.MAX_VALUE). Anything associative works: gcd, product mod p, count, or even "max subarray sum" with a small struct per node. That flexibility is the segment tree's big advantage.

Lazy propagation (the idea)

What if the update is "add 10 to every element from l to r"? Updating each leaf is O(n). Lazy propagation stops at nodes fully inside [l, r], updates their stored sum right away (sum += 10 × length) and leaves a note — "my children still owe +10" — in a lazy[] array. The note is only pushed down to the children when a later operation needs to go below that node. Range updates and range queries both stay O(log n).

// Inside a segment tree with long[] sum, lazy (range add, range sum)
private void apply(int node, int lo, int hi, long v) {
    sum[node] += v * (hi - lo + 1);          // whole range grows by v each
    lazy[node] += v;                         // remember to tell children later
}
private void push(int node, int lo, int hi) {         // hand pending work to children
    if (lazy[node] == 0 || lo == hi) return;
    int mid = (lo + hi) / 2;
    apply(2 * node, lo, mid, lazy[node]);
    apply(2 * node + 1, mid + 1, hi, lazy[node]);
    lazy[node] = 0;
}
private void add(int node, int lo, int hi, int l, int r, long v) {
    if (r < lo || hi < l) return;
    if (l <= lo && hi <= r) { apply(node, lo, hi, v); return; }   // stop here, be lazy
    push(node, lo, hi);
    int mid = (lo + hi) / 2;
    add(2 * node, lo, mid, l, r, v);
    add(2 * node + 1, mid + 1, hi, l, r, v);
    sum[node] = sum[2 * node] + sum[2 * node + 1];
}
// query is the normal query with push(node, lo, hi) called before splitting
// [2, 1, 5, 3, 4], add 10 to [1..3]: sum(0, 4) = 45, sum(2, 2) = 15

Fenwick tree (Binary Indexed Tree)

The whole trick is lowbit: i & -i keeps only the lowest set bit of i. In two's complement, -i flips all bits and adds 1, so it matches i only at that lowest 1 bit. Examples: 12 is 1100, lowbit 4; 6 is 110, lowbit 2; 7 is 111, lowbit 1.

In a Fenwick tree (1-indexed), bit[i] stores the sum of the lowbit(i) elements ending at i — that is, positions i − lowbit(i) + 1 to i. So bit[6] holds positions 5..6, bit[8] holds 1..8, bit[7] holds just 7.

• prefixSum(i): add bit[i], then jump to i − lowbit(i) (strip the lowest bit), until 0. 7 → 6 → 4 → 0.
• add(i, delta): update every block that contains i: bit[i], then jump to i + lowbit(i), until past n. 5 → 6 → 8.

class FenwickTree {
    private final int[] bit;           // 1-indexed: bit[0] unused

    FenwickTree(int n) { bit = new int[n + 1]; }

    // add delta to position i (1-indexed)
    void add(int i, int delta) {
        for (; i < bit.length; i += i & -i) bit[i] += delta;   // climb to covering ranges
    }
    // sum of positions 1..i
    int prefixSum(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];                // strip lowest bit each step
        return s;
    }
    int rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); }
}
// values 2, 1, 5, 3, 4 at positions 1..5: prefixSum(3) = 8, rangeSum(2, 4) = 9

Both loops run at most log₂ n + 1 times, since each step removes or carries one bit. Space is exactly n + 1 ints. Building by calling add n times is O(n log n).

Segment tree or Fenwick tree?

Rule of thumb: sum or count with point updates → Fenwick. Min/max, range updates, or anything custom → segment tree. If the array never changes, neither — use a prefix sum array (or a sparse table for min/max). Java has no built-in version of either; you write them.

Problem 1 — Range Sum Query - Mutable

class NumArray {
    private final int[] nums;
    private final FenwickTree fw;

    NumArray(int[] nums) {
        this.nums = nums.clone();
        fw = new FenwickTree(nums.length);
        for (int i = 0; i < nums.length; i++) fw.add(i + 1, nums[i]);   // shift to 1-indexed
    }
    void update(int index, int val) {
        fw.add(index + 1, val - nums[index]);   // BIT stores sums, so add the difference
        nums[index] = val;
    }
    int sumRange(int left, int right) {
        return fw.rangeSum(left + 1, right + 1);
    }
}
// [1, 3, 5]: sumRange(0, 2) = 9; update(1, 2); sumRange(0, 2) = 8

Why it works: the problem gives "set to value", but a BIT only knows "add delta", so we keep a copy of the array to compute the difference. The +1 shifts LeetCode's 0-indexed positions to the BIT's 1-indexed positions. Constructor O(n log n), update and sumRange O(log n), space O(n). The SegmentTree class above solves it just as well: update(index, val) and query(left, right).

Problem 2 — Count of smaller numbers after self (BIT)

For each nums[i], count how many elements to its right are smaller.

List<Integer> countSmaller(int[] nums) {
    // 1. coordinate compression: map each value to its rank 1..m
    int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();
    FenwickTree fw = new FenwickTree(sorted.length);
    Integer[] result = new Integer[nums.length];
    // 2. walk from the right; the BIT counts values already seen (to our right)
    for (int i = nums.length - 1; i >= 0; i--) {
        int rank = Arrays.binarySearch(sorted, nums[i]) + 1;  // 1-indexed rank
        result[i] = fw.prefixSum(rank - 1);                  // how many seen values are smaller
        fw.add(rank, 1);                                      // record this value
    }
    return Arrays.asList(result);
}   // [5, 2, 6, 1] -> [2, 1, 1, 0]

Why it works: scanning right to left, the BIT holds a count for every value to the right of i (a frequency table indexed by value). "How many are smaller than nums[i]" is then a prefix sum over the ranks below it. Coordinate compression — replacing values by their rank among the distinct sorted values — is needed because values can be negative or up to 10⁹, and a BIT index must be a small positive integer. Using rank − 1 excludes equal values, so duplicates are not counted as smaller. Time O(n log n) (sort, then n binary searches and BIT operations), space O(n). The alternative is a modified merge sort that counts how many right-half elements jump ahead of each left-half element — same complexity. The same BIT pattern counts inversions in an array.

Pitfalls

• Fenwick trees are 1-indexed. Calling add(0, x) loops forever, because 0 & -0 is 0.
• Segment tree array too small: use 4 * n, not 2 * n, for the recursive version.
• Returning the wrong neutral value on "no overlap" — 0 for sum, Integer.MAX_VALUE for min, Integer.MIN_VALUE for max.
• Overflow: sums of many ints can pass 2³¹ − 1. Use long[] when values or counts are large.
• In lazy propagation, forgetting to push before going down in a query as well as in an update.
• Reaching for these when the array never changes — a prefix sum array is simpler and O(1) per query.

19. Sorting

Two words you must know. A sort is stable if equal items keep their original relative order (two people both aged 30 stay in the order they came in). A sort is in-place if it only uses O(1) (or O(log n) stack) extra memory instead of a second array.

All sorts at a glance

* Bubble sort is O(n) only with the "stop if no swaps this pass" check. ** Bucket sort is stable if the sort used inside each bucket is stable. k = range of values, d = number of digits, b = base (10 or 256).

Insertion sort — the card-hand sort

Everything left of i is already sorted. Take a[i] out, shift every bigger item one step right, and drop it into the gap. On a nearly sorted array the inner loop barely runs, which is why it is O(n) in the best case and why real libraries use it for small pieces.

// Time O(n²) worst / O(n) best, Space O(1), stable
static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {   // shift bigger items one step right
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;                   // drop key into the gap
    }
}
// {5, 2, 4, 6, 1, 3}  ->  [1, 2, 3, 4, 5, 6]

Using a[j] > key (strictly greater) is what keeps it stable: an equal item never jumps over another equal item.

Merge sort — split in half, sort each half, merge

Keep cutting the array in half until each piece has one element (a single element is sorted by definition). Then merge pairs of sorted pieces: look at the front of both, take the smaller, repeat. Merging two sorted lists of total size n takes O(n), and there are log n levels of halving, so the total is O(n log n) — always, whatever the input.

// Time O(n log n) always, Space O(n), stable
static void mergeSort(int[] a) {
    if (a.length < 2) return;
    int[] tmp = new int[a.length];        // one buffer, reused by every merge
    sort(a, tmp, 0, a.length - 1);
}

private static void sort(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) return;                 // 0 or 1 element: already sorted
    int mid = lo + (hi - lo) / 2;
    sort(a, tmp, lo, mid);
    sort(a, tmp, mid + 1, hi);
    if (a[mid] <= a[mid + 1]) return;     // halves already in order: skip merge
    merge(a, tmp, lo, mid, hi);
}

private static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        // "<=" takes from the LEFT on ties: this is what makes it stable
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
}
// {38, 27, 43, 3, 9, 82, 10}  ->  [3, 9, 10, 27, 38, 43, 82]

Quicksort — pick a pivot, partition, recurse

Pick one element, the pivot. Partition the array so everything smaller is on its left and everything else on its right. Now the pivot sits in its final sorted position forever. Recurse on the two sides. No merge step is needed — the work is done before the recursion, not after.

If the pivot is always the smallest or biggest element (for example, always taking the last element of an already-sorted array), one side is empty every time and you get O(n²). A random pivot makes that astronomically unlikely, giving expected O(n log n) on any input.

// Time: expected O(n log n), worst O(n²); Space O(log n) expected stack; not stable
static void quickSort(int[] a) { quickSort(a, 0, a.length - 1); }

private static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);         // a[p] is now in its final place
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

// Lomuto: returns final index of the pivot
static int partition(int[] a, int lo, int hi) {
    int r = ThreadLocalRandom.current().nextInt(lo, hi + 1);
    swap(a, r, hi);                       // move random pivot to the end
    int pivot = a[hi];
    int i = lo;                           // a[lo..i-1] are all < pivot
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) swap(a, i++, j);
    }
    swap(a, i, hi);                       // pivot goes right after the "< pivot" block
    return i;
}

static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

Lomuto vs Hoare: Lomuto (above) is easier to write correctly. Hoare's scheme moves two pointers inward from both ends and swaps out-of-place pairs; it does about three times fewer swaps and handles many equal keys better, but the pivot does not end at the returned index, so the recursion is (lo, p) and (p + 1, hi). With lots of duplicates, Lomuto degrades toward O(n²); the fix is a 3-way partition (< pivot, == pivot, > pivot) — the same idea as the Dutch flag problem below.

Counting sort — tally, then place

When values are small whole numbers in 0..k, don't compare at all. Count how many times each value appears, turn counts into end positions with a running sum, then place each item. Walking the input backwards in the last step keeps equal items in their original order, which is what radix sort depends on.

// Time O(n + k), Space O(n + k), stable. Values must be in [0, k].
static int[] countingSort(int[] a, int k) {
    int[] count = new int[k + 1];
    for (int x : a) count[x]++;                              // 1. tally
    for (int v = 1; v <= k; v++) count[v] += count[v - 1];   // 2. prefix sums = end positions
    int[] out = new int[a.length];
    for (int i = a.length - 1; i >= 0; i--) {                // 3. walk backwards = stable
        out[--count[a[i]]] = a[i];
    }
    return out;
}
// {4, 2, 2, 8, 3, 3, 1}, k = 8  ->  [1, 2, 2, 3, 3, 4, 8]

Radix sort runs a stable counting sort once per digit, least significant digit first (base 10 or 256): O(d(n + b)). Bucket sort drops values into n buckets by range, sorts each small bucket, then concatenates — O(n) on average if data is evenly spread, O(n²) if everything lands in one bucket.

What Java's Arrays.sort actually does

Why two different algorithms? Stability. For primitives, two equal ints are indistinguishable, so stability is meaningless and Java picks the fastest in-place option: quicksort. For objects, two "equal" items can differ (two employees with the same salary but different names). If you sort by name and then by salary, you expect the names to stay in order within each salary — that needs a stable sort. TimSort is also great at real-world data, which is often partly sorted, and it uses few comparisons, which matters when each comparison is a (slow) compareTo call.

Sorting with comparators

A Comparator<T> returns a negative number if a comes first, 0 if equal, positive if b comes first. Primitive arrays cannot take a comparator — use Integer[] or sort int[][] rows.

record Person(String name, int age) {}

List<Person> people = new ArrayList<>(List.of(
    new Person("Asha", 30), new Person("Ben", 25), new Person("Cara", 30), new Person("Dev", 25)));

// age descending, then name ascending
people.sort(Comparator.comparingInt(Person::age).reversed().thenComparing(Person::name));
// [Asha 30, Cara 30, Ben 25, Dev 25]

Integer[] boxed = {5, 1, 4};
Arrays.sort(boxed, Collections.reverseOrder());          // [5, 4, 1]

int[][] pts = {{3, 1}, {1, 2}, {1, 1}};                  // by x, then by y
Arrays.sort(pts, (p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));
// [[1, 1], [1, 2], [3, 1]]

Quickselect — the k-th smallest without sorting everything

Partition once, exactly like quicksort. The pivot lands at index p. If p == k, done. Otherwise, the answer is only on one side, so recurse into that side only. Expected work is n + n/2 + n/4 + ... = 2n, which is O(n).

// k-th smallest, k is 0-based. Time: expected O(n), worst O(n²). Space O(1).
static int quickSelect(int[] a, int k) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int p = partition(a, lo, hi);     // same random-pivot Lomuto as above
        if (p == k) return a[p];
        if (p < k) lo = p + 1; else hi = p - 1;
    }
    return a[lo];
}

// LeetCode 215: k-th LARGEST
static int findKthLargest(int[] nums, int k) {
    return quickSelect(nums, nums.length - k);   // k-th largest = (n-k)-th smallest
}
// {3, 2, 1, 5, 6, 4}, k = 2  ->  5

Alternative: a min-heap of size k gives O(n log k) time with a guaranteed bound and works on a stream. Quickselect is faster on average but changes the array.

Problem: Sort Colors (Dutch national flag)

Sort an array of 0s, 1s and 2s in one pass, in place. Keep three regions: [0, low) are 0s, [low, mid) are 1s, (high, end] are 2s; [mid, high] is unknown.

// Time O(n), one pass. Space O(1).
static void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] == 0)      swap(nums, low++, mid++);
        else if (nums[mid] == 1) mid++;
        else                     swap(nums, mid, high--);   // don't move mid: new value unchecked
    }
}
// {2, 0, 2, 1, 1, 0}  ->  [0, 0, 1, 1, 2, 2]

Why this works: each step shrinks the unknown region by one while keeping all three regions correct. When swapping with high, the value that arrives at mid has not been looked at yet, so mid must stay put. When swapping with low, the value arriving is already known to be a 1 (it came from the 1s region), so both pointers advance.

Problem: Merge Intervals (preview)

// Time O(n log n) for the sort, Space O(n) for the output
static int[][] mergeIntervals(int[][] intervals) {
    Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
    List<int[]> out = new ArrayList<>();
    for (int[] cur : intervals) {
        if (out.isEmpty() || out.get(out.size() - 1)[1] < cur[0]) {
            out.add(cur);                                 // gap: start a new interval
        } else {
            int[] last = out.get(out.size() - 1);
            last[1] = Math.max(last[1], cur[1]);          // overlap: stretch the last one
        }
    }
    return out.toArray(new int[0][]);
}
// {{1,3},{8,10},{2,6},{15,18}}  ->  [[1, 6], [8, 10], [15, 18]]

Why this works: after sorting by start, any interval that overlaps the current merged block must come right after it — nothing further down the list can start earlier. So one left-to-right sweep is enough.

Problem: Largest Number

Arrange numbers to form the largest possible number: [3, 30, 34, 5, 9] becomes "9534330". Normal numeric order fails (30 > 3, but "330" > "303"). The trick is a custom comparator: put a before b if the string a + b is bigger than b + a.

// Time O(n log n * L) where L = max digits, Space O(n * L)
static String largestNumber(int[] nums) {
    String[] s = new String[nums.length];
    for (int i = 0; i < nums.length; i++) s[i] = String.valueOf(nums[i]);
    // a goes before b if a+b is bigger than b+a
    Arrays.sort(s, (a, b) -> (b + a).compareTo(a + b));
    if (s[0].equals("0")) return "0";                     // all zeros
    return String.join("", s);
}
// {3, 30, 34, 5, 9}  ->  "9534330";   {0, 0}  ->  "0"

Why this works: this "concatenation order" is transitive (a proven property), so it is a valid total order and sorting by it puts every adjacent pair in the best order — and if no adjacent swap improves the result, the whole thing is optimal. Don't forget the all-zeros edge case.

Problem: Count Inversions (via merge sort)

An inversion is a pair i < j with a[i] > a[j]. It measures "how unsorted" an array is. Brute force is O(n²). During the merge step, when we take an element from the right half, it is smaller than every element still waiting in the left half — that is mid - i + 1 inversions counted in one go.

// Time O(n log n), Space O(n). Returns long: n = 100k can give ~5 * 10^9 inversions.
static long countInversions(int[] a) {
    return countSort(a.clone(), new int[a.length], 0, a.length - 1);
}

private static long countSort(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    long count = countSort(a, tmp, lo, mid) + countSort(a, tmp, mid + 1, hi);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            count += mid - i + 1;     // a[i..mid] are ALL bigger than a[j]
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
    return count;
}
// {8, 4, 2, 1}  ->  6;    {2, 4, 1, 3, 5}  ->  3

Why this works: every inversion is either inside the left half, inside the right half (both counted by recursion), or split across the halves. Because both halves are sorted at merge time, split inversions can be counted in bulk instead of pair by pair.

20. Binary Search

The invariant — what makes binary search correct

An invariant is a statement that is true before every loop iteration. For binary search it is: "if the answer exists, it is inside the range [lo, hi)." Every update must keep that true, and every iteration must make the range strictly smaller. If both hold, the loop ends with lo == hi pointing at the answer. Nearly every binary search bug is a violation of one of those two rules (dropping the answer, or a range that stops shrinking and loops forever).

The one template to remember: lower bound

"Find the first index where a condition becomes true." For a sorted array and the condition a[i] >= target, that index is called the lower bound. Use a half-open range [lo, hi) with hi = a.length, because the answer may be "past the end" (every element is smaller).

// First index where a[i] >= target (a.length if none). Time O(log n), Space O(1)
static int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;           // half-open [lo, hi): answer may be a.length
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= target) hi = mid;  // mid could be the answer: keep it
        else lo = mid + 1;               // mid is too small: throw it away
    }
    return lo;                           // lo == hi == the boundary
}

// First index where a[i] > target. Same shape, only the condition changes.
static int upperBound(int[] a, int target) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// a = {1, 3, 3, 3, 5, 8, 9}
// lowerBound(a, 3) = 1, upperBound(a, 3) = 4, lowerBound(a, 4) = 4, lowerBound(a, 10) = 7

Why mid = lo + (hi - lo) / 2 and not (lo + hi) / 2? If lo = 2,000,000,000 and hi = 2,100,000,000, their sum is bigger than Integer.MAX_VALUE and wraps to a negative number: (lo + hi) / 2 gives -97483648. The subtraction form gives 2050000000. (lo + hi) >>> 1 (unsigned shift) also works.

Why does this loop always end? mid rounds down, so mid < hi always. Setting hi = mid shrinks the range, and lo = mid + 1 shrinks it too. No infinite loop is possible.

Variants built from the same template

Java has built-ins: Arrays.binarySearch(a, key) returns some matching index (not necessarily the first!) or -(insertionPoint) - 1 if missing. TreeMap/TreeSet give floor, ceiling, lower, higher in O(log n).

Problem: First and Last Position (LeetCode 34)

// Time O(log n), Space O(1)
static int[] searchRange(int[] a, int target) {
    int first = lowerBound(a, target);
    if (first == a.length || a[first] != target) return new int[]{-1, -1};
    int last = upperBound(a, target) - 1;
    return new int[]{first, last};
}
// {5, 7, 7, 8, 8, 10}, 8  ->  [3, 4];   target 6  ->  [-1, -1]

Why this works: the first 8 is the first index with value >= 8; the last 8 is just before the first index with value > 8. Two O(log n) searches, never a linear scan over the duplicates (which would be O(n) if the whole array were 8s).

Problem: Search in Rotated Sorted Array (LeetCode 33)

[4, 5, 6, 7, 0, 1, 2] is a sorted array rotated at some point. Cut it at mid: at least one half is always normally sorted. Check if the target lies inside that sorted half's range; if yes go there, otherwise go to the other half.

// Time O(log n), Space O(1). Assumes distinct values.
static int searchRotated(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[lo] <= a[mid]) {                        // left half [lo..mid] is sorted
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                      // right half [mid..hi] is sorted
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}
// {4, 5, 6, 7, 0, 1, 2}, 0  ->  4;   target 3  ->  -1

Why this works: in the sorted half, a simple range check tells us for sure whether the target can be there. If it can't, it can only be in the other half. Note a[lo] <= a[mid] uses <= because when lo == mid the "left half" is a single element, which is sorted. Related: find the minimum of a rotated array — if a[mid] > a[hi] the drop is to the right (lo = mid + 1), else hi = mid.

// Time O(log n). {4, 5, 6, 7, 0, 1, 2}  ->  0
static int findMinRotated(int[] a) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[hi]) lo = mid + 1;   // min is strictly right of mid
        else hi = mid;                      // mid might be the min
    }
    return a[lo];
}

Problem: Find Peak Element (LeetCode 162)

The array is not sorted, yet binary search works. A peak is bigger than its neighbours (edges count as minus infinity). If a[mid] < a[mid + 1], we're walking uphill to the right, so a peak must exist on the right (either it keeps rising to the edge, or it turns down somewhere).

// Time O(log n), Space O(1)
static int findPeakElement(int[] a) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < a[mid + 1]) lo = mid + 1;  // uphill to the right: a peak is there
        else hi = mid;                          // downhill: mid or something left is a peak
    }
    return lo;
}
// {1, 2, 3, 1}  ->  2;    {1, 2, 1, 3, 5, 6, 4}  ->  5

Why this works: the invariant is "a peak exists in [lo, hi]". Binary search needs a rule that tells you which half keeps the answer — not necessarily a sorted array. mid + 1 is safe because lo < hi means mid < hi.

Binary search on the answer

Many "minimise the maximum" or "find the smallest X such that..." problems don't search an array at all. They search the range of possible answers. You need two things: a range [lo, hi] that surely contains the answer, and a feasible(x) check that is monotonic — once it becomes true, it stays true for all bigger x. Then find the first true.

// Smallest x in [lo, hi] with feasible(x) == true. feasible must look like F F F T T T.
// Time O(log(hi - lo) * cost of feasible)
static int firstTrue(int lo, int hi, IntPredicate feasible) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible.test(mid)) hi = mid;   // mid works: answer is mid or smaller
        else lo = mid + 1;                  // mid fails: answer is bigger
    }
    return lo;
}

Problem: Koko Eating Bananas (LeetCode 875)

Koko eats at speed k bananas per hour, one pile at a time; a pile of p takes ceil(p / k) hours. Find the slowest k that finishes within h hours. Faster is always at least as good — monotonic.

// Time O(n log M) where M = max pile, Space O(1)
static 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 (hoursNeeded(piles, k) <= h) hi = k;  // k works: try slower
        else lo = k + 1;                         // too slow: must go faster
    }
    return lo;
}

static long hoursNeeded(int[] piles, int k) {
    long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;   // ceil(p / k) without doubles
    return hours;
}
// {3, 6, 7, 11}, h = 8  ->  4;    {30, 11, 23, 4, 20}, h = 5  ->  30

Problem: Capacity to Ship Packages Within D Days (LeetCode 1011)

// Time O(n log(sum)), Space O(1)
static int shipWithinDays(int[] weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) { lo = Math.max(lo, w); hi += w; }   // must fit the heaviest; one day ships all
    while (lo < hi) {
        int cap = lo + (hi - lo) / 2;
        if (daysNeeded(weights, cap) <= days) hi = cap;
        else lo = cap + 1;
    }
    return lo;
}

static int daysNeeded(int[] weights, int cap) {
    int days = 1, load = 0;
    for (int w : weights) {
        if (load + w > cap) { days++; load = 0; }   // start a new day
        load += w;
    }
    return days;
}
// {1..10}, days = 5  ->  15

Problem: Split Array Largest Sum (LeetCode 410)

Split into k contiguous parts to minimise the largest part's sum. Same shape as shipping: "can I split so every part is <= X using at most k parts?" is monotonic in X, and the greedy check (fill a part until it would overflow) is optimal for a fixed X.

// Time O(n log(sum)), Space O(1). long guards against sum overflow.
static int splitArray(int[] nums, int k) {
    long lo = 0, hi = 0;
    for (int x : nums) { lo = Math.max(lo, x); hi += x; }
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (piecesNeeded(nums, mid) <= k) hi = mid;
        else lo = mid + 1;
    }
    return (int) lo;
}

static int piecesNeeded(int[] nums, long maxSum) {
    int pieces = 1; long sum = 0;
    for (int x : nums) {
        if (sum + x > maxSum) { pieces++; sum = 0; }
        sum += x;
    }
    return pieces;
}
// {7, 2, 5, 10, 8}, k = 2  ->  18   ([7,2,5] and [10,8])

Why these work: the answer lies between "the biggest single item" (no smaller value can ever be feasible) and "the total" (always feasible). The check is monotonic, so binary search finds the exact boundary in about 30–40 checks instead of trying every value.

Problem: Sqrt(x) (LeetCode 69)

// Integer square root, rounded down. Time O(log x), Space O(1)
static int mySqrt(int x) {
    long lo = 0, hi = (long) x + 1;          // search the first m with m*m > x
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (mid * mid > x) hi = mid;         // long: mid*mid never overflows
        else lo = mid + 1;
    }
    return (int) (lo - 1);                   // last m with m*m <= x
}
// 8 -> 2,  16 -> 4,  0 -> 0,  Integer.MAX_VALUE -> 46340

Why this works: "m*m > x" is F F F T T T over m, so the first true minus one is the floor of the square root. Using int for mid * mid would overflow for x near 2^31.

Common bugs

21. Recursion & Backtracking

Choose, explore, un-choose

Picture every run of a backtracking function as a decision tree. The root is the empty solution. Each edge is one choice. Each leaf is either a complete answer or a dead end. The recursion does a depth-first walk of this tree, and the call stack is the current path from the root. Because one shared list (path) is reused for every branch, you must undo each change after the recursive call returns — otherwise the next branch starts with garbage in it.

The generic template

// Shape of every backtracking solution. Fill in the four helpers per problem.
static void backtrack(List<Integer> path, int start) {
    if (isComplete(path)) {                 // 1. goal reached: record a COPY
        result.add(new ArrayList<>(path));
        return;
    }
    for (int choice : choices(start)) {     // 2. try every option at this step
        if (!isValid(path, choice)) continue;   //    prune dead branches early
        path.add(choice);                   // 3. choose
        backtrack(path, choice + 1);        // 4. explore
        path.remove(path.size() - 1);       // 5. un-choose (undo exactly step 3)
    }
}

Three questions design any backtracking solution: What is the state? (the path plus an index or a used[] array). What are the choices at each step? When is it complete, and when is it hopeless?

Pruning — cutting branches early

Pruning does not change the worst-case Big-O on paper, but in practice it is the difference between "instant" and "timeout". Typical prunes: sort the input and break once a candidate is too big (combination sum); check constraints the moment you place something instead of at the end (N-Queens); skip duplicates with if (i > start && nums[i] == nums[i - 1]) continue; after sorting (Subsets II, Combination Sum II); stop if there aren't enough items left to finish.

Problem: Subsets (LeetCode 78)

// Time O(n * 2^n): 2^n subsets, each copied in O(n). Space O(n) recursion (excluding output)
static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    subsetsBt(nums, 0, new ArrayList<>(), res);
    return res;
}

static void subsetsBt(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));              // every node of the tree is a subset
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                       // choose
        subsetsBt(nums, i + 1, path, res);       // explore (only later elements)
        path.remove(path.size() - 1);            // un-choose
    }
}
// {1, 2, 3}  ->  [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Why this works: the start index means we only ever add elements to the right of the last one picked, so each subset is built in exactly one order and appears exactly once. Alternative view: for each element, "take it or skip it" — two choices, n times, 2^n leaves.

Problem: Permutations (LeetCode 46)

// Time O(n * n!): n! leaves, each copied in O(n). Space O(n)
static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    permBt(nums, new boolean[nums.length], new ArrayList<>(), res);
    return res;
}

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

Why this works: order matters for permutations, so every step may pick any unused element (loop from 0, not from start). The used[] array is part of the state, so it must be un-chosen too. Subsets vs permutations in one line: subsets loop from start, permutations loop from 0 with a used check.

Problem: Combination Sum (LeetCode 39)

// Each candidate may be used many times.
// Time O(N^(T/M + 1)) worst case (N candidates, T target, M smallest candidate). Space O(T/M) depth
static List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);                     // sorted lets us break early
    List<List<Integer>> res = new ArrayList<>();
    combBt(candidates, target, 0, new ArrayList<>(), res);
    return res;
}

static void combBt(int[] c, int remain, int start, List<Integer> path, List<List<Integer>> res) {
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < c.length; i++) {
        if (c[i] > remain) break;                // PRUNE: rest are even bigger
        path.add(c[i]);
        combBt(c, remain - c[i], i, path, res);  // i, not i+1: same number may repeat
        path.remove(path.size() - 1);
    }
}
// {2, 3, 6, 7}, 7  ->  [[2, 2, 3], [7]];    {2, 3, 5}, 8  ->  [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Why this works: passing i (not i + 1) lets a number be reused, while never going back to earlier numbers prevents duplicates like [3,2,2]. The sorted break kills entire subtrees at once.

Problem: N-Queens (LeetCode 51)

Place n queens on an n x n board so none attack each other. Put exactly one queen per row, so the only choice is the column. A square (r, c) is attacked if its column, its "/" diagonal (r + c is the same along it) or its "\" diagonal (r - c is the same) is taken. Three boolean arrays make the check O(1).

// Time O(n!) — row 0 has n options, row 1 at most n-1, ...  Space O(n)
static List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queenCol = new int[n];                 // queenCol[r] = column of queen in row r
    boolean[] cols = new boolean[n];
    boolean[] diag = new boolean[2 * n - 1];     // r + c is constant on a "/" diagonal
    boolean[] anti = new boolean[2 * n - 1];     // r - c + n - 1 is constant on a "\" diagonal
    placeRow(0, n, queenCol, cols, diag, anti, res);
    return res;
}

static void placeRow(int r, int n, int[] queenCol, boolean[] cols, boolean[] diag,
                     boolean[] anti, List<List<String>> res) {
    if (r == n) { res.add(draw(queenCol)); return; }
    for (int c = 0; c < n; c++) {
        int d = r + c, a = r - c + n - 1;
        if (cols[c] || diag[d] || anti[a]) continue;      // attacked: prune
        queenCol[r] = c; cols[c] = diag[d] = anti[a] = true;
        placeRow(r + 1, n, queenCol, cols, diag, anti, res);
        cols[c] = diag[d] = anti[a] = false;              // un-choose
    }
}

static List<String> draw(int[] queenCol) {
    int n = queenCol.length;
    List<String> board = new ArrayList<>();
    for (int c : queenCol) {
        char[] row = new char[n];
        Arrays.fill(row, '.');
        row[c] = 'Q';
        board.add(new String(row));
    }
    return board;
}
// n = 4  ->  [[.Q.., ...Q, Q..., ..Q.], [..Q., Q..., ...Q, .Q..]]
// solution counts for n = 1..8: 1 0 0 2 10 4 40 92

Why this works: one-queen-per-row is built into the structure, so row conflicts are impossible. Columns and diagonals are checked on placement, so every complete board reached is valid. queenCol[r] doesn't need un-choosing because it is overwritten on the next try.

Problem: Word Search (LeetCode 79)

// Time O(R * C * 3^L): every start cell, then at most 3 new directions per letter (L = word length)
// Space O(L) recursion
static boolean exist(char[][] board, String word) {
    for (int r = 0; r < board.length; r++)
        for (int c = 0; c < board[0].length; c++)
            if (dfs(board, word, r, c, 0)) return true;
    return false;
}

static boolean dfs(char[][] b, String word, int r, int c, int i) {
    if (i == word.length()) return true;
    if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != word.charAt(i))
        return false;
    char saved = b[r][c];
    b[r][c] = '#';                               // choose: mark as visited
    boolean found = dfs(b, word, r + 1, c, i + 1) || dfs(b, word, r - 1, c, i + 1)
                 || dfs(b, word, r, c + 1, i + 1) || dfs(b, word, r, c - 1, i + 1);
    b[r][c] = saved;                             // un-choose: restore the cell
    return found;
}
// board ABCE / SFCS / ADEE:  "ABCCED" -> true, "SEE" -> true, "ABCB" -> false

Why this works: marking the cell in place (instead of a separate visited set) stops a path from reusing a letter, and restoring it lets other paths use that cell later. The || chain short-circuits, so the search stops the moment one path succeeds.

Problem: Palindrome Partitioning (LeetCode 131)

// Time O(n * 2^n): 2^(n-1) ways to cut, O(n) to check/copy each. Space O(n)
static List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    partBt(s, 0, new ArrayList<>(), res);
    return res;
}

static void partBt(String s, int start, List<String> path, List<List<String>> res) {
    if (start == s.length()) { res.add(new ArrayList<>(path)); return; }
    for (int end = start; end < s.length(); end++) {
        if (!isPal(s, start, end)) continue;     // prune: only cut after a palindrome
        path.add(s.substring(start, end + 1));
        partBt(s, end + 1, path, res);
        path.remove(path.size() - 1);
    }
}

static boolean isPal(String s, int i, int j) {
    while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
    return true;
}
// "aab"  ->  [[a, a, b], [aa, b]]

Why this works: the choice at each step is "where does the next piece end?". Only palindromic pieces are allowed, and when start reaches the end, the whole string is covered. Speed-up: precompute a boolean[][] isPal table with DP in O(n²) so each check is O(1).

Complexity cheat sheet

22. Greedy

When greedy works

Two properties must hold:

• Greedy choice property — there is always an optimal solution that starts with the greedy choice. In other words, taking the "locally best" option never rules out reaching the best overall answer.
• Optimal substructure — after making that choice, what remains is a smaller version of the same problem, and solving it optimally gives an optimal overall answer.

The exchange argument (how you prove it, in easy words): take any optimal solution. If it doesn't use the greedy choice, swap one of its choices for the greedy one and show the result is still valid and no worse. Then an optimal solution with the greedy choice exists, so greedy is safe. Example for activity selection: an optimal schedule's first meeting ends at time E; the greedy first meeting ends at time e <= E (it's the earliest-ending one). Swap them — everything after still fits, because we finish even earlier. Same count, still optimal.

When greedy fails — the coin change counterexample

// Greedy coin change: always take the biggest coin that fits. Time O(number of coins)
static int greedyCoins(int[] coinsDesc, int amount) {
    int count = 0;
    for (int c : coinsDesc) {
        count += amount / c;
        amount %= c;
    }
    return amount == 0 ? count : -1;
}
// greedyCoins({4, 3, 1}, 6) = 3, but the true minimum (coin-change DP) is 2

Lesson: before trusting greedy, try to break it with a tiny counterexample. If you find one, the problem probably needs DP (see the Dynamic Programming section). Same story for the 0/1 knapsack (greedy by value/weight fails) versus the fractional knapsack (greedy by value/weight is optimal, because you can take part of an item).

The usual recipe

1. Decide what to sort by (end time? start time? size? ratio?). This is usually the whole insight.
2. Sweep once, making the locally best decision and keeping a small amount of state.
3. Sanity check with a counterexample hunt, then argue with an exchange argument.

Problem: Activity Selection / Non-overlapping Intervals (LeetCode 435)

Remove the fewest intervals so the rest don't overlap. Equivalent: keep the most non-overlapping intervals. Greedy rule: sort by end time and always keep the interval that finishes first — it leaves the most room for everything after.

// Time O(n log n), Space O(1) beyond the sort
static int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));   // by END time
    int kept = 0;
    int lastEnd = Integer.MIN_VALUE;
    for (int[] in : intervals) {
        if (in[0] >= lastEnd) {          // starts after the last kept one ends
            kept++;
            lastEnd = in[1];
        }
    }
    return intervals.length - kept;
}
// {{1,2},{2,3},{3,4},{1,3}} -> 1;   {{1,2},{1,2},{1,2}} -> 2

Why this works: the exchange argument above. Sorting by start time is the classic wrong answer: one long interval starting first would block many short ones.

Problem: Jump Game (LeetCode 55)

nums[i] is the maximum jump length from index i. Can you reach the last index? Track the farthest index reachable so far. If you ever stand on an index beyond it, you're stuck.

// Time O(n), Space O(1)
static boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;           // we can't even stand here
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}
// {2, 3, 1, 1, 4} -> true;   {3, 2, 1, 0, 4} -> false (everything stops at index 3)

Why this works: every index up to farthest is reachable (you can always jump shorter than the max). So we don't need to know which jumps to take — only how far the reachable region extends.

Problem: Jump Game II (LeetCode 45) — minimum jumps

Think of it as BFS in levels without a queue: all indexes reachable with 1 jump form level 1, those with 2 jumps form level 2, and so on. curEnd is the end of the current level; farthest is how far the next level reaches.

// Time O(n), Space O(1). Assumes the end is reachable.
static int jump(int[] nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {   // stop before last: no jump needed from it
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) {                        // used up this jump's range
            jumps++;
            curEnd = farthest;                    // next "level" of reach
        }
    }
    return jumps;
}
// {2, 3, 1, 1, 4} -> 2;   {2, 3, 0, 1, 4} -> 2;   {0} -> 0

Pitfall: looping to nums.length instead of nums.length - 1 counts one extra jump when a level ends exactly on the last index.

Problem: Gas Station (LeetCode 134)

Circular route; gas[i] fuel at station i, cost[i] to drive to the next. Find the start index that completes the loop (unique if it exists). Two facts: (1) if total gas >= total cost, a solution exists; (2) if you start at s and run dry before reaching i + 1, then no station between s and i can be the start either — so jump the start straight to i + 1.

// Time O(n), Space O(1)
static int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {          // can't reach i+1 from start: no station in [start..i] works
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}
// gas {1,2,3,4,5}, cost {3,4,5,1,2} -> 3;   gas {2,3,4}, cost {3,4,3} -> -1

Why this works: any station k inside [start, i] was reached with a tank >= 0, so starting at k with an empty tank can only be worse — it would also fail at i. That's why one pass is enough.

Problem: Assign Cookies (LeetCode 455)

// Time O(n log n + m log m), Space O(1) beyond sorting
static int findContentChildren(int[] greed, int[] cookies) {
    Arrays.sort(greed);
    Arrays.sort(cookies);
    int child = 0;
    for (int c = 0; c < cookies.length && child < greed.length; c++) {
        if (cookies[c] >= greed[child]) child++;   // smallest cookie that satisfies this child
    }
    return child;
}
// greed {1,2,3}, cookies {1,1} -> 1;   greed {1,2}, cookies {1,2,3} -> 2

Why this works: give the least greedy child the smallest cookie that satisfies them. Using a bigger cookie there would never help — by exchange, it can only take a cookie some greedier child could have used.

Problem: Meeting Rooms II / Minimum Platforms

Given meetings (or train arrival/departure times), find the minimum rooms (platforms) so nothing clashes. The answer is the maximum number of meetings happening at the same moment. Sweep start times in order and free up rooms whose meetings have ended.

// Two sorted arrays + two pointers. Time O(n log n), Space O(n)
static int minMeetingRooms(int[][] meetings) {
    int n = meetings.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = meetings[i][0]; ends[i] = meetings[i][1]; }
    Arrays.sort(starts);
    Arrays.sort(ends);
    int rooms = 0, maxRooms = 0, e = 0;
    for (int s = 0; s < n; s++) {
        while (e < n && ends[e] <= starts[s]) { e++; rooms--; }   // free rooms that ended
        rooms++;
        maxRooms = Math.max(maxRooms, rooms);
    }
    return maxRooms;
}

// Same answer with a min-heap of end times (one entry per busy room). Time O(n log n), Space O(n)
static int minMeetingRoomsHeap(int[][] meetings) {
    Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
    PriorityQueue<Integer> endTimes = new PriorityQueue<>();
    for (int[] m : meetings) {
        if (!endTimes.isEmpty() && endTimes.peek() <= m[0]) endTimes.poll();  // reuse a room
        endTimes.offer(m[1]);
    }
    return endTimes.size();
}
// {{0,30},{5,10},{15,20}} -> 2
// trains {{900,910},{940,1200},{950,1120},{1100,1130},{1500,1900},{1800,2000}} -> 3

Why this works: a room can only be reused once some meeting has ended, and we always reuse the one that ended earliest. The count only grows when every room is busy, so the peak is exactly the minimum needed. Edge case to ask about: if one meeting ends at 10 and another starts at 10, can they share a room? The code says yes (<=). For platforms problems that count "same minute" as a clash, use <.

Huffman coding — the greedy idea

Goal: give each character a binary code so frequent characters get short codes and the total encoded length is minimal (no code is a prefix of another). Greedy rule: repeatedly merge the two rarest nodes into a new node whose frequency is their sum. Each merge pushes those characters one level deeper — one more bit each — so the cost of a merge is a + b, and the total cost is the sum of all merges.

// Total encoded bits. Time O(n log n), Space O(n)
static long huffmanCost(int[] freq) {
    PriorityQueue<Long> pq = new PriorityQueue<>();
    for (int f : freq) pq.offer((long) f);
    long cost = 0;
    while (pq.size() > 1) {
        long a = pq.poll(), b = pq.poll();   // two rarest
        cost += a + b;                       // each merge adds one bit to all symbols below
        pq.offer(a + b);
    }
    return cost;
}
// freq {5, 9, 12, 13, 16, 45} -> 224 bits

Why this works: the two rarest characters should be the deepest leaves (exchange argument: swapping a rarer character deeper never increases cost), and they can be siblings. Merge them and the rest is the same problem, one character smaller. The same "merge two smallest" pattern solves Minimum Cost to Connect Sticks and optimal file merge.

23. Divide & Conquer

Split, solve, combine

The recursion tree and the master theorem

Write the running time as a recurrence: T(n) = a T(n / b) + f(n), meaning "a subproblems, each 1/b the size, plus f(n) work to split and combine". Draw it as a tree and add up the work level by level. For merge sort, a = 2, b = 2, f(n) = n:

The master theorem is a shortcut for T(n) = a T(n / b) + O(n^d). Compare d with log_b a (how fast the number of pieces grows):

The theorem needs equal-sized splits. Quicksort's worst case, T(n) = T(n - 1) + O(n), isn't covered — sum it directly: n + (n-1) + ... = O(n²).

Recap: merge sort and quickselect

Both were written in full in the Sorting section. Merge sort is the textbook D&C: trivial split, O(n) combine, O(n log n) always. Quickselect shows the power of recursing into only one piece: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n) on average, versus O(n log n) to sort first. Count inversions is merge sort with a counter in the combine step — same O(n log n).

Problem: Maximum Subarray (LeetCode 53) — D&C vs Kadane

Find the contiguous subarray with the largest sum. D&C view: the best subarray is either entirely in the left half, entirely in the right half, or crosses the middle. The crossing one is the best suffix of the left half glued to the best prefix of the right half — found in O(n) by walking outward from the middle.

// Divide & conquer. Time O(n log n), Space O(log n) recursion
static int maxSubArrayDC(int[] a) { return best(a, 0, a.length - 1); }

static int best(int[] a, int lo, int hi) {
    if (lo == hi) return a[lo];                    // one element
    int mid = lo + (hi - lo) / 2;
    int left = best(a, lo, mid);                   // answer fully in left half
    int right = best(a, mid + 1, hi);              // answer fully in right half
    // answer crossing the middle: best suffix of left + best prefix of right
    int sum = 0, bestLeft = Integer.MIN_VALUE;
    for (int i = mid; i >= lo; i--) { sum += a[i]; bestLeft = Math.max(bestLeft, sum); }
    sum = 0;
    int bestRight = Integer.MIN_VALUE;
    for (int j = mid + 1; j <= hi; j++) { sum += a[j]; bestRight = Math.max(bestRight, sum); }
    return Math.max(Math.max(left, right), bestLeft + bestRight);
}

// Kadane. Time O(n), Space O(1)
static int maxSubArrayKadane(int[] a) {
    int cur = a[0], best = a[0];
    for (int i = 1; i < a.length; i++) {
        cur = Math.max(a[i], cur + a[i]);   // extend the run, or start fresh here
        best = Math.max(best, cur);
    }
    return best;
}
// {-2, 1, -3, 4, -1, 2, 1, -5, 4}  ->  6 (subarray [4, -1, 2, 1]), both methods
// {-3, -1, -2}  ->  -1 (all negative: best is the single largest element)

Why both work: D&C covers all three places the answer can live. Kadane asks at each index "is the best run ending here the previous run extended, or a fresh start?" — a one-dimensional DP. Kadane wins in an interview (O(n)), but the D&C version is a favourite follow-up ("solve it with divide and conquer") and it generalises to a segment tree that answers max-subarray queries on ranges with updates, where Kadane cannot.

Problem: Pow(x, n) — fast exponentiation (LeetCode 50)

Multiplying x by itself n times is O(n). Instead: x^n = (x^(n/2))² if n is even, and x · (x^(n/2))² if odd. One half-size subproblem per level, so O(log n). The key is computing half once — writing pow(x, n/2) * pow(x, n/2) makes two calls and falls back to O(n).

// Recursive. Time O(log n), Space O(log n)
static double myPow(double x, int n) {
    long N = n;                          // -Integer.MIN_VALUE overflows int: use long
    if (N < 0) { x = 1 / x; N = -N; }
    return pow(x, N);
}

static double pow(double x, long n) {
    if (n == 0) return 1.0;
    double half = pow(x, n / 2);         // solve ONE half-size problem
    return (n % 2 == 0) ? half * half : half * half * x;
}

// Iterative (binary exponentiation). Time O(log n), Space O(1)
static double myPowIter(double x, int n) {
    long N = n;
    if (N < 0) { x = 1 / x; N = -N; }
    double result = 1.0;
    while (N > 0) {
        if ((N & 1) == 1) result *= x;   // this bit of n is set: include x^(2^k)
        x *= x;                          // x, x^2, x^4, x^8, ...
        N >>= 1;
    }
    return result;
}

// Modular version, used everywhere in counting problems ("answer mod 1e9+7")
static long modPow(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}
// myPow(2.0, 10) = 1024.0,  myPow(2.0, -2) = 0.25,  myPow(1.0, Integer.MIN_VALUE) = 1.0
// modPow(2, 10, 1_000_000_007) = 1024

Why this works: write n in binary, for example 13 = 1101₂, so x^13 = x^8 · x^4 · x^1. The loop walks the bits and multiplies in the matching powers of x. Pitfall: n = Integer.MIN_VALUE has no positive int counterpart, so -n overflows — convert to long first. In modPow, keep mod below about 3 · 10^9 so base * base fits in a long.

Closest pair of points — the idea

Given n points in a plane, find the two closest. Brute force checks all pairs: O(n²). D&C:

1. Split: sort by x, cut into left and right halves at the middle x.
2. Solve: find the closest distance d in each half recursively; let d = the smaller one.
3. Combine: the only pairs not yet checked cross the dividing line. Such a pair can only beat d if both points are within d of the line — a thin strip. Sort the strip by y; each point needs checking only against the next few points (at most 7) whose y is within d, because points on the same side are at least d apart and only a handful can fit in a d x 2d box.

// Time O(n log² n) as written (strip re-sorted at each level); O(n log n) if you merge by y
// like merge sort instead of re-sorting. Space O(n)
static double closestPair(int[][] pts) {
    int[][] byX = pts.clone();
    Arrays.sort(byX, (p, q) -> Integer.compare(p[0], q[0]));
    return closest(byX, 0, byX.length - 1);
}

static double closest(int[][] p, int lo, int hi) {
    if (hi - lo < 3) {                                   // tiny: brute force
        double best = Double.MAX_VALUE;
        for (int i = lo; i <= hi; i++)
            for (int j = i + 1; j <= hi; j++) best = Math.min(best, dist(p[i], p[j]));
        return best;
    }
    int mid = lo + (hi - lo) / 2;
    int midX = p[mid][0];
    double d = Math.min(closest(p, lo, mid), closest(p, mid + 1, hi));
    List<int[]> strip = new ArrayList<>();               // points within d of the dividing line
    for (int i = lo; i <= hi; i++) if (Math.abs(p[i][0] - midX) < d) strip.add(p[i]);
    strip.sort((a, b) -> Integer.compare(a[1], b[1]));   // sort strip by y
    for (int i = 0; i < strip.size(); i++)
        for (int j = i + 1; j < strip.size() && strip.get(j)[1] - strip.get(i)[1] < d; j++)
            d = Math.min(d, dist(strip.get(i), strip.get(j)));   // only a few j per i
    return d;
}

static double dist(int[] a, int[] b) {
    long dx = a[0] - b[0], dy = a[1] - b[1];
    return Math.sqrt(dx * dx + dy * dy);
}
// {{2,3},{12,30},{40,50},{5,1},{12,10},{3,4}}  ->  1.4142135623730951  ((2,3) and (3,4))

Rarely asked to code in full, but "how would you beat O(n²)?" is a good D&C discussion question. The inner loop looks nested, but the geometry caps it at a constant number of steps per point.

Problem: Count Inversions (recap)

The full code is in the Sorting section. As D&C: split at the middle; solve = count inversions inside each half (and sort them); combine = during the merge, each time an element is taken from the right half, add mid - i + 1 (the number of left elements still waiting, all bigger). Recurrence 2T(n/2) + O(n), so O(n log n) instead of O(n²). The same "count across the split while merging" trick solves Count of Smaller Numbers After Self (LeetCode 315) and Reverse Pairs (LeetCode 493).

When D&C beats brute force

• The combine step is cheaper than brute-forcing across the split. Inversions: checking all left-right pairs is O(n²), but sorted halves let us count them in O(n).
• You can throw pieces away. Binary search and quickselect recurse into only one piece — that's where O(log n) and O(n) come from.
• Reusing one sub-result. Fast power computes x^(n/2) once and squares it.
• Pieces are independent, so they can run in parallel (Java's ForkJoinPool, Arrays.parallelSort, MapReduce).

When it doesn't help: if the subproblems overlap (Fibonacci: fib(n-1) and fib(n-2) both recompute fib(n-3)), plain D&C is exponential — that is exactly when you switch to memoization / DP. And if the combine step is as expensive as the whole brute force, splitting buys nothing.

24. Dynamic Programming — the Fundamentals

The two properties, explained

• Overlapping subproblems — a plain recursive solution calls itself with the same arguments many times. If every call is different (like merge sort's halves), there is nothing to reuse: that is divide and conquer, not DP.
• Optimal substructure — the best answer for size n is built from best answers for smaller sizes. Shortest path has it (a shortest path's middle part is also shortest). "Longest simple path" does not, which is why it has no DP.

Seeing the repeated work

Climbing stairs: you can climb 1 or 2 steps at a time; how many ways to reach step n? To land on step n, your last move was either from n-1 (a 1-step) or from n-2 (a 2-step). So ways(n) = ways(n-1) + ways(n-2) — the Fibonacci recurrence.

// Plain recursion: correct but O(2^n) time
static int climbNaive(int n) {
    if (n <= 1) return 1;                 // 1 way to stand on step 0 or reach step 1
    return climbNaive(n - 1) + climbNaive(n - 2);
}

The call counts are real: counting calls in the code above gives 15 for n = 5 and 2,692,537 for n = 30. The tree roughly doubles with each extra step, so it is O(2^n). Yet there are only n + 1 different questions (f0 to fn). DP answers each one once.

The 5-step recipe

Use these steps for every DP problem. Say them out loud in an interview — it shows structure even before the code is right.

Top-down (memoisation) vs bottom-up (tabulation)

Top-down: write the natural recursion, then add a cache (the memo). Before computing, check the memo; after computing, store it. Bottom-up: create a table and fill it from the smallest states upward with a loop, so every value you need is already there.

// Top-down: recursion + memo. O(n) time, O(n) space (memo + call stack)
static int climbMemo(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);                       // -1 = "not solved yet"
    return go(n, memo);
}
private static int go(int i, int[] memo) {
    if (i <= 1) return 1;                        // base cases
    if (memo[i] != -1) return memo[i];           // already solved? reuse
    return memo[i] = go(i - 1, memo) + go(i - 2, memo);
}

// Bottom-up: fill a table from small to big. O(n) time, O(n) space
static int climbTab(int n) {
    if (n <= 1) return 1;
    int[] dp = new int[n + 1];
    dp[0] = 1; dp[1] = 1;                        // base cases
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];           // recurrence
    return dp[n];                                // answer
}

// Space-optimised: only the last two values are ever read. O(n) time, O(1) space
static int climbO1(int n) {
    int prev2 = 1, prev1 = 1;                    // dp[i-2], dp[i-1]
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

All three versions return 13 for n = 6 and 1,836,311,903 for n = 45 (the largest n that still fits in an int).

Second example: House Robber (LC 198)

Houses in a row hold money nums[i]. You cannot rob two neighbours. Maximise the total. At each house the choice is rob it (then skip the next) or skip it.

• State: dp[i] = most money from the first i houses.
• Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]) — skip house i, or rob it and add the best from two houses back.
• Base: dp[0] = 0, dp[1] = nums[0]. Answer: dp[n].

// Top-down: best(i) = most money from houses i..n-1
static int robMemo(int[] nums) {
    return best(nums, 0, new Integer[nums.length]);  // null = not solved yet
}
private static int best(int[] nums, int i, Integer[] memo) {
    if (i >= nums.length) return 0;
    if (memo[i] != null) return memo[i];
    int rob  = nums[i] + best(nums, i + 2, memo);    // take i, skip neighbour
    int skip = best(nums, i + 1, memo);              // leave i
    return memo[i] = Math.max(rob, skip);
}

// Bottom-up table
static int robTab(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n + 1];                       // dp[i] = best using first i houses
    dp[1] = nums[0];
    for (int i = 2; i <= n; i++)
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    return dp[n];
}

// Rolling variables: O(n) time, O(1) space
static int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;                        // best up to i-2, best up to i-1
    for (int x : nums) {
        int cur = Math.max(prev1, prev2 + x);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Traced on nums = [2, 7, 9, 3, 1]:

All three versions return 12 (rob houses 2, 9 and 1). Time O(n); space O(n) for memo/table, O(1) for the rolling version.

Space optimisation — the general rule

• If dp[i] only reads dp[i-1] and dp[i-2], keep two variables.
• If a 2D dp[i][j] only reads row i-1, keep one or two 1D rows. Direction matters: loop so you never read a cell you already overwrote in this row (unless you want to — see knapsack in section 25).
• You lose the ability to reconstruct the actual choices (which houses, which items). If the question asks for the path, not just the number, keep the full table.

How to recognise a DP problem

25. DP Patterns

0/1 knapsack

n items each with a weight and a value; a bag of capacity W. Each item is taken at most once. Maximise value.

• State: dp[i][c] = best value using the first i items with capacity c.
• Recurrence: dp[i][c] = max(dp[i-1][c], dp[i-1][c - w] + v) — skip item i, or take it (only if w <= c).
• Base: row 0 is all zeros (no items, no value). Answer: dp[n][W].

static int knapsack2D(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];   // dp[i][c] = best value, first i items, capacity c
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            dp[i][c] = dp[i - 1][c];                          // skip item i
            if (wt[i - 1] <= c)                               // take item i (once)
                dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - wt[i - 1]] + val[i - 1]);
        }
    }
    return dp[n][W];
}

Traced with weights {1, 3, 4}, values {15, 20, 30}, W = 4:

Answer 35 (items of weight 1 and 3). Time O(n·W), space O(n·W).

1D version. Row i only reads row i-1, so one array is enough — if you loop capacity backwards.

static int knapsack1D(int[] wt, int[] val, int W) {
    int[] dp = new int[W + 1];                 // dp[c] = best value with capacity c
    for (int i = 0; i < wt.length; i++)
        for (int c = W; c >= wt[i]; c--)       // BACKWARDS: each item used at most once
            dp[c] = Math.max(dp[c], dp[c - wt[i]] + val[i]);
    return dp[W];
}

Time O(n·W), space O(W). Note W is a value, not a size — this is "pseudo-polynomial", so it is fast only when W is small (say up to 10^4–10^5).

Unbounded knapsack: Coin Change (LC 322) and Coin Change II (LC 518)

Each coin can be used any number of times. Two different questions: fewest coins (min), and number of combinations (count).

• Coin Change — state: dp[a] = fewest coins to make amount a. Recurrence: dp[a] = min over coins (dp[a - coin] + 1). Base: dp[0] = 0.
• Coin Change II — state: dp[a] = number of combinations making a. Recurrence: dp[a] += dp[a - coin]. Base: dp[0] = 1 (one way to make 0: take nothing).

static int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];            // dp[a] = fewest coins to make a
    Arrays.fill(dp, amount + 1);               // "infinity" that cannot overflow on +1
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int coin : coins)
            if (coin <= a)
                dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

static int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];            // dp[a] = number of combinations making a
    dp[0] = 1;                                 // one way to make 0: take nothing
    for (int coin : coins)                     // coins OUTER -> combinations, not orders
        for (int a = coin; a <= amount; a++)   // forwards: a coin may repeat
            dp[a] += dp[a - coin];
    return dp[amount];
}

coinChange({1, 2, 5}, 11) = 3 (5+5+1); coinChange({2}, 3) = -1; change(5, {1, 2, 5}) = 4. Both run in O(amount · coins) time, O(amount) space.

Longest Increasing Subsequence (LC 300)

A subsequence keeps order but may skip elements. Find the longest strictly increasing one.

O(n^2): dp[i] = length of the LIS that ends exactly at index i. For every earlier j with nums[j] < nums[i], you can extend it: dp[i] = max(dp[j] + 1). The answer is the max over all i (not dp[n-1]).

static int lengthOfLIS_n2(int[] nums) {
    int n = nums.length, best = 0;
    int[] dp = new int[n];                     // dp[i] = LIS ending exactly at i
    for (int i = 0; i < n; i++) {
        dp[i] = 1;                             // just nums[i] alone
        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;
}

O(n log n) — patience sorting. Keep tails[k] = the smallest possible last value of an increasing subsequence of length k+1. A smaller tail is always better, because it is easier to extend. For each number, binary-search the first tail >= x and replace it; if none, append.

static int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int lo = 0, hi = size;                 // find first tail >= x
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < x) lo = mid + 1; else hi = mid;
        }
        tails[lo] = x;                         // replace, or append if lo == size
        if (lo == size) size++;
    }
    return size;
}

Both return 4. tails is not itself a valid subsequence — only its length is meaningful. For "non-decreasing" use "first tail > x" instead. Time O(n log n), space O(n). Variants: Russian doll envelopes (sort by width ascending, height descending, then LIS on heights), number of LIS, longest chain.

Longest Common Subsequence (LC 1143)

• State: dp[i][j] = LCS length of a[0..i) and b[0..j) (the first i and j characters).
• Recurrence: if a[i-1] == b[j-1], both last chars join the LCS: dp[i-1][j-1] + 1. Otherwise drop one of them: max(dp[i-1][j], dp[i][j-1]).
• Base: row 0 and column 0 are 0 (empty string). Answer: dp[m][n].

static int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];        // dp[i][j] = LCS of a[0..i) and b[0..j)
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                    ? dp[i - 1][j - 1] + 1                    // diagonal + 1
                    : Math.max(dp[i - 1][j], dp[i][j - 1]);   // up or left
    return dp[m][n];
}

Table for a = "abcde", b = "ace" (bold = a character match, taken from the diagonal):

Answer 3 ("ace"). To rebuild the string, start at dp[m][n]: on a match step diagonally and record the char; else move toward the larger of up/left. Time O(m·n), space O(m·n), or O(min(m, n)) with two rows.

Edit Distance (LC 72)

Fewest single-character inserts, deletes or replaces to turn a into b.

• State: dp[i][j] = edits to turn a[0..i) into b[0..j).
• Recurrence: chars equal: dp[i-1][j-1] (free). Otherwise 1 + min(replace dp[i-1][j-1], delete dp[i-1][j], insert dp[i][j-1]).
• Base: dp[i][0] = i (delete all), dp[0][j] = j (insert all).

static int minDistance(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i; // delete everything
    for (int j = 0; j <= n; j++) dp[0][j] = j; // insert everything
    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];                 // free: chars match
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],    // replace
                               Math.min(dp[i - 1][j],        // delete from a
                                        dp[i][j - 1]));      // insert into a
            }
        }
    }
    return dp[m][n];
}

minDistance("horse", "ros") = 3 (horse → rorse → rose → ros); ("intention", "execution") = 5. Time and space O(m·n).

Grid paths: Unique Paths (LC 62) and Minimum Path Sum (LC 64)

Moving only right or down, a cell can be reached only from above or from the left. So dp[r][c] combines dp[r-1][c] and dp[r][c-1] — sum them to count paths, min them for cheapest path.

static int uniquePaths(int m, int n) {
    int[] dp = new int[n];                     // one row, reused
    Arrays.fill(dp, 1);                        // first row: one way to each cell
    for (int r = 1; r < m; r++)
        for (int c = 1; c < n; c++)
            dp[c] += dp[c - 1];                // from above (old dp[c]) + from left
    return dp[n - 1];
}

static int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (r == 0 && c == 0) dp[r][c] = grid[0][0];
            else if (r == 0)      dp[r][c] = dp[r][c - 1] + grid[r][c];   // top row: only from left
            else if (c == 0)      dp[r][c] = dp[r - 1][c] + grid[r][c];   // left column: only from above
            else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + grid[r][c];
        }
    }
    return dp[m - 1][n - 1];
}

uniquePaths(3, 7) = 28; minPathSum([[1,3,1],[1,5,1],[4,2,1]]) = 7 (path 1→3→1→1→1). Both O(m·n) time; space O(n) and O(m·n) (can also be O(n) or done in place). With obstacles (LC 63), set dp to 0 on blocked cells.

Partition Equal Subset Sum (LC 416)

Can the array split into two parts with equal sums? That means: is there a subset summing to total / 2? This is 0/1 knapsack with booleans.

static boolean canPartition(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;          // odd total can never split evenly
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];    // dp[s] = can some subset sum to s?
    dp[0] = true;                              // the empty subset
    for (int x : nums)
        for (int s = target; s >= x; s--)      // backwards: each number used once
            dp[s] = dp[s] || dp[s - x];
    return dp[target];
}

[1, 5, 11, 5] → true (11 = 1+5+5); [1, 2, 3, 5] → false. Time O(n · sum), space O(sum). Same shape: Target Sum (LC 494) counts subsets with sum (total + target) / 2.

Word Break (LC 139)

• State: dp[i] = the first i characters can be split into dictionary words.
• Recurrence: dp[i] is true if some j < i has dp[j] true and s[j..i) is a word.

static boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];         // dp[i] = s[0..i) can be segmented
    dp[0] = true;                              // empty prefix
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;                         // one valid split is enough
            }
        }
    }
    return dp[n];
}

"leetcode" with ["leet", "code"] → true; "catsandog" with ["cats", "dog", "sand", "and", "cat"] → false. Time O(n^3) in the worst case (n^2 pairs, each substring costs O(n)); limit j to the longest word length to speed it up. Space O(n).

Interval DP: Burst Balloons (LC 312)

Interval DP solves every sub-range [l, r], shortest ranges first, by trying each split point k inside. The trick in Burst Balloons is to let k be the last balloon burst in the range: then its neighbours at that moment are the fixed walls l and r, and the left and right parts become independent.

• State: dp[l][r] = most coins from bursting every balloon strictly between l and r (padded with 1s at both ends).
• Recurrence: dp[l][r] = max over k (dp[l][k] + v[l]·v[k]·v[r] + dp[k][r]).
• Order: by increasing gap r - l.

static int maxCoins(int[] nums) {
    int n = nums.length;
    int[] v = new int[n + 2];                  // pad with 1 on both ends
    v[0] = v[n + 1] = 1;
    for (int i = 0; i < n; i++) v[i + 1] = nums[i];
    int[][] dp = new int[n + 2][n + 2];
    for (int len = 2; len <= n + 1; len++) {   // gap between the two walls
        for (int l = 0; l + len <= n + 1; l++) {
            int r = l + len;
            for (int k = l + 1; k < r; k++)    // k = LAST balloon burst in (l, r)
                dp[l][r] = Math.max(dp[l][r],
                        dp[l][k] + v[l] * v[k] * v[r] + dp[k][r]);
        }
    }
    return dp[0][n + 1];
}

[3, 1, 5, 8] → 167. Time O(n^3), space O(n^2). Matrix chain multiplication is the same shape: dp[i][j] = min over k (dp[i][k] + dp[k+1][j] + rows[i]·cols[k]·cols[j]) — the cost of splitting the product at k.

DP on trees: House Robber III (LC 337)

Houses form a binary tree; you cannot rob a parent and its child. Each node returns two answers to its parent — best if this node is skipped, best if it is robbed — so the parent can choose. This "return a small array from DFS" is the general tree-DP pattern.

static int robTree(TreeNode root) {
    int[] r = dfs(root);
    return Math.max(r[0], r[1]);
}
// returns {best if we SKIP this node, best if we ROB this node}
private static int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] L = dfs(node.left), R = dfs(node.right);
    int skip = Math.max(L[0], L[1]) + Math.max(R[0], R[1]); // children free to choose
    int rob  = node.val + L[0] + R[0];                      // children must be skipped
    return new int[]{skip, rob};
}

Tree [3, 2, 3, null, 3, null, 1] → 7 (3 + 3 + 1). Time O(n) (each node visited once), space O(h) for the recursion, where h is the tree height.

Bitmask DP: Travelling Salesman for small n

When n is at most about 20, a set of visited items fits in the bits of an int: bit i set means item i is in the set. 1 << n masks times n endpoints is small enough.

• State: dp[mask][v] = cheapest path that starts at city 0, visits exactly the cities in mask, and ends at v.
• Transition: from (mask, v) go to an unvisited u: dp[mask | 1<<u][u] = min(…, dp[mask][v] + dist[v][u]).

static int tsp(int[][] dist) {
    int n = dist.length, FULL = 1 << n, INF = Integer.MAX_VALUE / 2;
    int[][] dp = new int[FULL][n];
    for (int[] row : dp) Arrays.fill(row, INF);
    dp[1][0] = 0;                              // start at city 0; mask = {0}
    for (int mask = 1; mask < FULL; mask++) {
        for (int v = 0; v < n; v++) {
            if (dp[mask][v] == INF || (mask & (1 << v)) == 0) continue;
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) != 0) continue;          // already visited
                int next = mask | (1 << u);
                dp[next][u] = Math.min(dp[next][u], dp[mask][v] + dist[v][u]);
            }
        }
    }
    int best = INF;
    for (int v = 1; v < n; v++)                                // return home to 0
        best = Math.min(best, dp[FULL - 1][v] + dist[v][0]);
    return best;
}

For the classic 4-city matrix {{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}} it returns 80. Time O(2^n · n^2), space O(2^n · n) — compared with O(n!) for trying every order. Masks increase numerically, and adding a bit always makes a larger number, so smaller masks are always ready first.

State machine: Buy and Sell Stock

Give each day a few states (holding a share, just sold, resting) and write how you move between them. Each state keeps the best profit so far in that state.

// One transaction (LC 121): track the cheapest price seen so far. O(n), O(1)
static int maxProfitOne(int[] prices) {
    int minPrice = Integer.MAX_VALUE, best = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        best = Math.max(best, p - minPrice);
    }
    return best;
}

// Unlimited transactions with a 1-day cooldown after selling (LC 309). O(n), O(1)
static int maxProfitCooldown(int[] prices) {
    int hold = Integer.MIN_VALUE / 2;   // own a share
    int sold = Integer.MIN_VALUE / 2;   // just sold today (tomorrow is cooldown)
    int rest = 0;                       // no share, free to buy
    for (int p : prices) {
        int prevHold = hold, prevSold = sold, prevRest = rest;
        hold = Math.max(prevHold, prevRest - p);   // keep holding, or buy from rest
        sold = prevHold + p;                       // sell what we held
        rest = Math.max(prevRest, prevSold);       // stay resting, or cooldown ends
    }
    return Math.max(sold, rest);
}

// Unlimited transactions, fee per sale (LC 714). O(n), O(1)
static int maxProfitFee(int[] prices, int fee) {
    int hold = -prices[0], cash = 0;
    for (int i = 1; i < prices.length; i++) {
        int p = prices[i];
        int newCash = Math.max(cash, hold + p - fee);  // sell today
        int newHold = Math.max(hold, cash - p);        // buy today
        cash = newCash; hold = newHold;
    }
    return cash;
}

Results: [7,1,5,3,6,4] one transaction → 5; [1,2,3,0,2] with cooldown → 3; [1,3,2,8,4,9] with fee 2 → 8. For "at most k transactions" (LC 188), add a dimension: hold[j] and cash[j] for j = 1..k, giving O(n·k).

26. Shortest Paths

Which algorithm when

Dijkstra — the idea

Keep a min-heap of (node, distance). Pop the closest node. Because all weights are non-negative, nothing found later can make it cheaper — its distance is final. Relax its outgoing edges and push any improved neighbours.

Dijkstra — reusable Java template

// graph.get(u) = list of {v, w}. Returns dist[] from src (MAX_VALUE = unreachable).
static int[] dijkstra(List<List<int[]>> graph, int src) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    // heap entries are {node, distance}, smallest distance first
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
    pq.offer(new int[]{src, 0});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int u = top[0], d = top[1];
        if (d > dist[u]) continue;                 // stale entry: a shorter path was already found
        for (int[] e : graph.get(u)) {
            int v = e[0], nd = d + e[1];
            if (nd < dist[v]) {                    // relax
                dist[v] = nd;
                pq.offer(new int[]{v, nd});
            }
        }
    }
    return dist;
}

On the graph above it returns [0, 3, 1, 4, 7]. Time O((V + E) log V): each edge can push once, each push/pop costs log. Space O(V + E).

• Lazy deletion: Java's PriorityQueue has no fast "decrease key", so we push a new entry and skip the old one when it pops (the d > dist[u] line). Without that check the code is still correct but slower.
• Use Integer.compare, not a[1] - b[1]: subtraction can overflow with large distances and sort wrongly.
• Use long distances if a path can exceed about 2.1 billion.
• For one target, you may stop as soon as the target is popped.

Why Dijkstra fails with negative edges

Dijkstra's promise — "the popped node is final" — assumes a longer route can never become cheaper later. A negative edge breaks that. Take edges A→B 1, A→C 5, C→B -10, B→D 1. The textbook version (mark a node "done" when popped) finalises B = 1 and D = 2, then later finds A→C→B = -5 — but B is already done. Running it gives [0, 1, 5, 2]; the true answer (Bellman-Ford) is [0, -5, 5, -4].

0-1 BFS

If every weight is 0 or 1, use a deque instead of a heap: a 0-edge keeps the same distance, so push it to the front; a 1-edge goes to the back. The deque stays sorted, like a heap that never needs log. Typical problem: minimum walls to remove, minimum cost to make a grid path valid (LC 1368).

static int[] zeroOneBfs(List<List<int[]>> graph, int src) {
    int[] dist = new int[graph.size()];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    Deque<Integer> dq = new ArrayDeque<>();
    dq.offerFirst(src);
    while (!dq.isEmpty()) {
        int u = dq.pollFirst();
        for (int[] e : graph.get(u)) {
            int v = e[0], w = e[1];                // w is 0 or 1
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.offerFirst(v);      // free edge: same level, go to front
                else        dq.offerLast(v);
            }
        }
    }
    return dist;
}

Time O(V + E), space O(V).

Bellman-Ford

Relax every edge, V - 1 times. After round k, every shortest path that uses at most k edges is correct. A shortest path without cycles has at most V - 1 edges, so that many rounds suffice. If a V-th round still improves something, a negative cycle exists (you could loop forever and keep getting cheaper).

// edges: {u, v, w}. Returns null if a negative cycle is reachable from src.
static int[] bellmanFord(int n, int[][] edges, int src) {
    final int INF = Integer.MAX_VALUE;
    int[] dist = new int[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 1; round <= n - 1; round++) {
        boolean changed = false;
        for (int[] e : edges) {
            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) {   // skip unreachable u
                dist[e[1]] = dist[e[0]] + e[2];
                changed = true;
            }
        }
        if (!changed) break;                               // already settled: stop early
    }
    for (int[] e : edges)                                  // one more round: still improving?
        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]])
            return null;                                   // negative cycle
    return dist;
}

Time O(V · E), space O(V). The != INF check matters: INF + negative would look like a real small distance.

Floyd-Warshall (all pairs)

d[i][j] = shortest distance from i to j using only nodes 0..k as stepping stones. Each round of k asks: "is going through k better?" It is really a DP over k.

static long[][] floydWarshall(int n, int[][] edges) {
    final long INF = Long.MAX_VALUE / 4;                   // room to add two INFs safely
    long[][] d = new long[n][n];
    for (long[] row : d) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);
    for (int k = 0; k < n; k++)                  // k MUST be the outermost loop
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
    return d;                                    // d[i][i] < 0 means i is on a negative cycle
}

Time O(V^3), space O(V^2). Row A of the result for the example graph is 0 3 1 4 7, matching Dijkstra. Putting k in an inner loop is the classic bug — it gives wrong answers silently.

Problem: Network Delay Time (LC 743)

A signal starts at node k; times[i] = {u, v, w}. How long until every node has it? That is the largest shortest distance from k, or -1 if some node is unreachable.

static int networkDelayTime(int[][] times, int n, int k) {
    List<List<int[]>> g = new ArrayList<>();
    for (int i = 0; i <= n; i++) g.add(new ArrayList<>());   // nodes are 1..n
    for (int[] t : times) g.get(t[0]).add(new int[]{t[1], t[2]});
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
    pq.offer(new int[]{k, 0});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int u = top[0], d = top[1];
        if (d > dist[u]) continue;
        for (int[] e : g.get(u)) {
            if (d + e[1] < dist[e[0]]) {
                dist[e[0]] = d + e[1];
                pq.offer(new int[]{e[0], dist[e[0]]});
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;   // someone never gets the signal
        ans = Math.max(ans, dist[i]);
    }
    return ans;
}

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 → 2. Time O(E log V), space O(V + E). Why it works: every node receives the signal at its shortest-path time, so the last one to receive it decides the answer.

Problem: Cheapest Flights Within K Stops (LC 787)

K stops means at most K + 1 flights (edges). Bellman-Ford's "after round r, paths with at most r edges are correct" is exactly this limit — run just K + 1 rounds.

static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    final int INF = Integer.MAX_VALUE;
    int[] dist = new int[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 0; round <= k; round++) {           // k stops = at most k+1 flights
        int[] next = dist.clone();                       // read ONLY last round's values
        for (int[] f : flights) {
            int u = f[0], v = f[1], price = f[2];
            if (dist[u] != INF && dist[u] + price < next[v])
                next[v] = dist[u] + price;
        }
        dist = next;
    }
    return dist[dst] == INF ? -1 : dist[dst];
}

With flights 0→1 100, 1→2 100, 0→2 500: k = 1 → 200, k = 0 → 500. Time O(K · E), space O(V).

Problem: Path With Minimum Effort (LC 1631)

On a height grid, a path's effort is the largest height difference between consecutive cells. Minimise it. Dijkstra still works when the path cost is "max of edges" instead of "sum of edges", because extending a path never makes its cost go down.

static int minimumEffortPath(int[][] heights) {
    int R = heights.length, C = heights[0].length;
    int[][] effort = new int[R][C];
    for (int[] row : effort) Arrays.fill(row, Integer.MAX_VALUE);
    effort[0][0] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2])); // {r, c, effort}
    pq.offer(new int[]{0, 0, 0});
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int r = cur[0], c = cur[1], e = cur[2];
        if (r == R - 1 && c == C - 1) return e;          // first time popped = final answer
        if (e > effort[r][c]) continue;
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
            int ne = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c])); // cost = max step
            if (ne < effort[nr][nc]) {
                effort[nr][nc] = ne;
                pq.offer(new int[]{nr, nc, ne});
            }
        }
    }
    return 0;
}

[[1,2,2],[3,8,2],[5,3,5]] → 2. Time O(R·C·log(R·C)), space O(R·C). Alternatives: binary search on the answer + BFS, or union-find adding edges in increasing weight until corner meets corner.

27. Topological Sort, MST & More

Topological sort — Kahn's algorithm (BFS on indegree)

The indegree of a node is how many edges point into it — how many things must happen before it. Start with every node whose indegree is 0 (no prerequisites). Take one, "finish" it, and lower the indegree of everything it points to. Anything that drops to 0 is now ready.

// Edge {u, v} means u must come before v.
// Returns a topological order, or an empty array if there is a cycle.
static int[] topoKahn(int n, int[][] edges) {
    List<List<Integer>> g = new ArrayList<>();
    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }

    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);   // no prerequisites
    int[] order = new int[n];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u;
        for (int v : g.get(u))
            if (--indeg[v] == 0) q.offer(v);   // its last prerequisite is done
    }
    return idx == n ? order : new int[0];      // fewer than n placed => cycle
}

Running it gives [0, 3, 1, 4, 2]. Time O(V + E), space O(V + E). Cycle detection for free: nodes on a cycle never reach indegree 0, so fewer than V nodes get placed.

Topological sort — DFS with three colours

Colour each node: white = not visited, gray = on the current DFS path (still exploring its descendants), black = completely finished. Reaching a gray node means you walked back into your own path: a cycle. When a node turns black, push it on a stack; the stack from top to bottom is a topological order (reverse post-order).

static final int WHITE = 0, GRAY = 1, BLACK = 2;
static List<List<Integer>> G;
static int[] color;
static Deque<Integer> stack;

static List<Integer> topoDfs(int n, int[][] edges) {
    G = new ArrayList<>();
    for (int i = 0; i < n; i++) G.add(new ArrayList<>());
    for (int[] e : edges) G.get(e[0]).add(e[1]);
    color = new int[n];
    stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++)
        if (color[i] == WHITE && hasCycle(i)) return List.of();   // cycle: no order
    return new ArrayList<>(stack);             // top of stack first
}
// true if a cycle is reachable from u
static boolean hasCycle(int u) {
    color[u] = GRAY;                           // on the current path
    for (int v : G.get(u)) {
        if (color[v] == GRAY) return true;     // back edge => cycle
        if (color[v] == WHITE && hasCycle(v)) return true;
    }
    color[u] = BLACK;                          // fully explored
    stack.push(u);                             // push AFTER all descendants
    return false;
}

On the clothing graph it returns [3, 4, 0, 1, 2] (pants, shoes, shirt, tie, jacket) — a different but equally valid order. Time O(V + E), space O(V) plus recursion depth.

Problem: Course Schedule I & II (LC 207, 210)

prerequisites[i] = {a, b} means "take b before a" — so the edge goes b → a. Getting this direction backwards is the most common bug. Course Schedule I asks "can you finish?" (is it a DAG?); II asks for an order.

static int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> g = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) g.add(new ArrayList<>());
    int[] indeg = new int[numCourses];
    for (int[] p : prerequisites) {            // p = {course, prereq}: prereq -> course
        g.get(p[1]).add(p[0]);
        indeg[p[0]]++;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
    int[] order = new int[numCourses];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u;
        for (int v : g.get(u)) if (--indeg[v] == 0) q.offer(v);
    }
    return idx == numCourses ? order : new int[0];
}

static boolean canFinish(int numCourses, int[][] prerequisites) {
    return findOrder(numCourses, prerequisites).length == numCourses;
}

canFinish(2, [[1,0]]) → true; canFinish(2, [[1,0],[0,1]]) → false. findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) → [0, 1, 2, 3]. Time O(V + E), space O(V + E).

Problem idea: Alien Dictionary (LC 269)

Words are sorted in an unknown alphabet; find the letter order. Compare each pair of adjacent words: the first position where they differ tells you one rule, x comes before y. Those rules are edges; the answer is a topological sort of the letters.

static String alienOrder(String[] words) {
    Map<Character, Set<Character>> g = new HashMap<>();
    Map<Character, Integer> indeg = new HashMap<>();
    for (String w : words)
        for (char c : w.toCharArray()) { g.putIfAbsent(c, new HashSet<>()); indeg.putIfAbsent(c, 0); }
    for (int i = 0; i + 1 < words.length; i++) {
        String a = words[i], b = words[i + 1];
        if (a.length() > b.length() && a.startsWith(b)) return "";  // "abc" before "ab": invalid
        for (int j = 0; j < Math.min(a.length(), b.length()); j++) {
            char x = a.charAt(j), y = b.charAt(j);
            if (x != y) {                                           // first difference decides
                if (g.get(x).add(y)) indeg.merge(y, 1, Integer::sum); // count each edge once
                break;
            }
        }
    }
    Deque<Character> q = new ArrayDeque<>();
    for (var e : indeg.entrySet()) if (e.getValue() == 0) q.offer(e.getKey());
    StringBuilder sb = new StringBuilder();
    while (!q.isEmpty()) {
        char c = q.poll();
        sb.append(c);
        for (char nx : g.get(c)) if (indeg.merge(nx, -1, Integer::sum) == 0) q.offer(nx);
    }
    return sb.length() == indeg.size() ? sb.toString() : "";      // cycle => ""
}

["wrt","wrf","er","ett","rftt"] → "wertf"; ["z","x","z"] → "" (cycle). Time O(total characters), space O(alphabet^2) at most for edges.

Minimum spanning tree

Both MST algorithms rely on the cut property: split the nodes into any two groups; the cheapest edge crossing between them is safe to include in some MST. Kruskal and Prim are two ways of repeatedly finding such an edge.

Kruskal (sort edges + union-find)

Sort all edges by weight. Walk through them cheapest first; take an edge if it connects two different components, skip it if both ends are already connected (it would make a cycle). Union-find answers "already connected?" in almost O(1).

static class DSU {
    int[] parent, rank;
    DSU(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                       // already connected
        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;                                  // union by rank
        if (rank[ra] == rank[rb]) rank[ra]++;
        return true;
    }
}

static int kruskal(int n, int[][] edges) {                // edges {u, v, w}
    int[][] sorted = edges.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[2], b[2]));   // cheapest first
    DSU dsu = new DSU(n);
    int cost = 0, used = 0;
    for (int[] e : sorted) {
        if (dsu.union(e[0], e[1])) {                      // joins two different trees?
            cost += e[2];
            if (++used == n - 1) break;                   // a tree has n-1 edges
        }
    }
    return used == n - 1 ? cost : -1;                     // -1: graph is disconnected
}

Returns 11 on the graph above. Time O(E log E) for the sort; space O(V + E). Best for sparse graphs or when edges come as a list.

Prim (grow one tree with a heap)

Start from any node. Repeatedly add the cheapest edge that leaves the current tree. It looks like Dijkstra, but the heap key is the edge weight, not the total distance from the start.

static int prim(int n, int[][] edges) {
    List<List<int[]>> g = new ArrayList<>();
    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
    for (int[] e : edges) {                              // undirected: add both ways
        g.get(e[0]).add(new int[]{e[1], e[2]});
        g.get(e[1]).add(new int[]{e[0], e[2]});
    }
    boolean[] inTree = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1])); // {node, edgeWeight}
    pq.offer(new int[]{0, 0});
    int cost = 0, count = 0;
    while (!pq.isEmpty() && count < n) {
        int[] top = pq.poll();
        int u = top[0];
        if (inTree[u]) continue;                         // already joined via a cheaper edge
        inTree[u] = true;
        cost += top[1];
        count++;
        for (int[] e : g.get(u))
            if (!inTree[e[0]]) pq.offer(new int[]{e[0], e[1]});
    }
    return count == n ? cost : -1;
}

Also 11. Time O(E log V), space O(V + E).

Problem: Min Cost to Connect All Points (LC 1584)

Every pair of points is an edge with cost = Manhattan distance |x1-x2| + |y1-y2|. That is a complete graph with about n^2 / 2 edges, so the array version of Prim — no heap, just scan for the closest point each step — is the best fit: O(n^2) time and only O(n) memory.

static int minCostConnectPoints(int[][] points) {
    int n = points.length, cost = 0;
    int[] best = new int[n];                   // cheapest edge from the tree to each point
    Arrays.fill(best, Integer.MAX_VALUE);
    boolean[] inTree = new boolean[n];
    best[0] = 0;
    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int i = 0; i < n; i++)            // pick the closest point not yet in the tree
            if (!inTree[i] && (u == -1 || best[i] < best[u])) u = i;
        inTree[u] = true;
        cost += best[u];
        for (int v = 0; v < n; v++) {          // does u offer anyone a cheaper link?
            if (inTree[v]) continue;
            int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
            if (d < best[v]) best[v] = d;
        }
    }
    return cost;
}

[[0,0],[2,2],[3,10],[5,2],[7,0]] → 20. Why it works: each step adds the cheapest edge crossing the cut between "in tree" and "not in tree", which the cut property says is safe. Kruskal would need to build and sort all n^2 edges: O(n^2 log n) time and O(n^2) memory.

Strongly connected components — Kosaraju in easy words

In a directed graph, a strongly connected component (SCC) is a group where every node can reach every other node. Squash each SCC into one node and the graph becomes a DAG.

1. DFS the whole graph and record nodes in the order they finish.
2. Reverse every edge.
3. Take nodes in reverse finish order; each DFS on the reversed graph from an unvisited node collects exactly one SCC.

Why: the node that finishes last belongs to a "source" component. In the reversed graph, that component cannot leak out into others, so one DFS grabs just it.

static int kosaraju(int n, int[][] edges) {
    List<List<Integer>> g = new ArrayList<>(), rg = new ArrayList<>();
    for (int i = 0; i < n; i++) { g.add(new ArrayList<>()); rg.add(new ArrayList<>()); }
    for (int[] e : edges) { g.get(e[0]).add(e[1]); rg.get(e[1]).add(e[0]); }
    boolean[] seen = new boolean[n];
    Deque<Integer> finish = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (!seen[i]) dfs1(i, g, seen, finish);  // pass 1: finish order
    Arrays.fill(seen, false);
    int count = 0;
    while (!finish.isEmpty()) {                                          // pass 2: reversed graph
        int u = finish.pop();                                            // latest finisher first
        if (!seen[u]) { dfs2(u, rg, seen); count++; }                    // one SCC per tree
    }
    return count;
}
static void dfs1(int u, List<List<Integer>> g, boolean[] seen, Deque<Integer> finish) {
    seen[u] = true;
    for (int v : g.get(u)) if (!seen[v]) dfs1(v, g, seen, finish);
    finish.push(u);                                  // pushed when u is finished
}
static void dfs2(int u, List<List<Integer>> rg, boolean[] seen) {
    seen[u] = true;
    for (int v : rg.get(u)) if (!seen[v]) dfs2(v, rg, seen);
}

Edges 0→1, 1→2, 2→0, 1→3, 3→4 give 3 SCCs: {0,1,2}, {3}, {4}. Time O(V + E), space O(V + E). Tarjan's algorithm finds SCCs in one pass using the same low values as below.

Bridges and articulation points — Tarjan's idea

In an undirected graph, a bridge is an edge whose removal disconnects the graph; an articulation point is such a node. They show up as "critical connections in a network" (LC 1192), single points of failure, and road networks.

During DFS, give each node a discovery time disc[u] and compute low[u] = the earliest discovery time reachable from u's subtree using at most one back edge. If child v has low[v] > disc[u], nothing under v can climb back above u without the edge u–v: it is a bridge. (For articulation points the test is low[v] >= disc[u], with a special rule for the root: it is one only if it has two or more DFS children.)

static int timer;
static List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<Integer>> g = new ArrayList<>();
    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
    for (List<Integer> c : connections) { g.get(c.get(0)).add(c.get(1)); g.get(c.get(1)).add(c.get(0)); }
    int[] disc = new int[n], low = new int[n];
    Arrays.fill(disc, -1);                               // -1 = not visited
    List<List<Integer>> bridges = new ArrayList<>();
    timer = 0;
    for (int i = 0; i < n; i++) if (disc[i] == -1) bridgeDfs(i, -1, g, disc, low, bridges);
    return bridges;
}
static void bridgeDfs(int u, int parent, List<List<Integer>> g, int[] disc, int[] low, List<List<Integer>> out) {
    disc[u] = low[u] = timer++;
    for (int v : g.get(u)) {
        if (v == parent) continue;                       // don't reuse the edge we came in on
        if (disc[v] == -1) {
            bridgeDfs(v, u, g, disc, low, out);
            low[u] = Math.min(low[u], low[v]);
            if (low[v] > disc[u]) out.add(List.of(u, v)); // v's subtree can't reach above u
        } else {
            low[u] = Math.min(low[u], disc[v]);          // back edge
        }
    }
}

A triangle 0-1-2 plus edge 1-3 gives [[1, 3]]. Time O(V + E), space O(V + E). For large inputs, recursion depth can reach V; convert to an iterative DFS or run in a thread with a bigger stack.

28. String Algorithms

Naive matching and why it is slow

// Try every start position. O(n·m) worst case, O(1) space
static int naiveSearch(String text, String pat) {
    int n = text.length(), m = pat.length();
    for (int i = 0; i + m <= n; i++) {          // every possible start
        int j = 0;
        while (j < m && text.charAt(i + j) == pat.charAt(j)) j++;
        if (j == m) return i;
    }
    return -1;
}

Text "aaaaaaaaab", pattern "aaab": at every start the loop matches three a's, then fails on b, then slides by one and re-reads those same a's. That is up to m comparisons at each of n starts: O(n·m). On random text it is usually fine, and Java's String.indexOf works this way — but interviewers test with the bad case.

KMP (Knuth–Morris–Pratt)

KMP precomputes, for the pattern alone, the LPS array: lps[i] = length of the longest proper prefix of pat[0..i] that is also a suffix of it ("proper" = not the whole string). On a mismatch after matching j characters, we already know the last lps[j-1] characters of the text equal the start of the pattern — so we continue from there, and the text pointer never moves back.

Traced for pattern "ababaca":

// lps[i] = length of the longest proper prefix of p[0..i] that is also a suffix of it
static int[] buildLps(String p) {
    int m = p.length();
    int[] lps = new int[m];
    int len = 0;                                // length of the current matched prefix
    for (int i = 1; i < m; i++) {
        while (len > 0 && p.charAt(i) != p.charAt(len))
            len = lps[len - 1];                 // fall back to the next shorter border
        if (p.charAt(i) == p.charAt(len)) len++;
        lps[i] = len;
    }
    return lps;
}

// Find the Index of the First Occurrence in a String (LC 28)
static int kmpSearch(String text, String pat) {
    if (pat.isEmpty()) return 0;
    int[] lps = buildLps(pat);
    int j = 0;                                  // chars of pat matched so far
    for (int i = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != pat.charAt(j))
            j = lps[j - 1];                     // shift the pattern; i never moves back
        if (text.charAt(i) == pat.charAt(j)) j++;
        if (j == pat.length()) return i - j + 1; // for ALL matches: record, then j = lps[j - 1]
    }
    return -1;
}

buildLps("ababaca") = [0, 0, 1, 2, 3, 0, 1]; kmpSearch("sadbutsad", "sad") = 0; kmpSearch("leetcode", "leeto") = -1; kmpSearch("ababcabcabababd", "ababd") = 10. Collecting all matches of "aa" in "aaaaa" gives [0, 1, 2, 3] (overlaps included).

Time O(n + m): i only moves forward, and j can only fall back as many times as it went up. Space O(m) for the LPS array.

Rabin-Karp (rolling hash)

Turn each length-m window of the text into a number (a hash) and compare numbers instead of strings. The trick is rolling: sliding the window one step right updates the hash in O(1) — subtract the leftmost character's contribution, multiply by the base, add the new character.

static int rabinKarp(String text, String pat) {
    int n = text.length(), m = pat.length();
    if (m > n) return -1;
    final long MOD = 1_000_000_007L, BASE = 131;
    long power = 1;                              // BASE^(m-1) % MOD, weight of the leading char
    for (int i = 1; i < m; i++) power = power * BASE % MOD;
    long hp = 0, ht = 0;
    for (int i = 0; i < m; i++) {
        hp = (hp * BASE + pat.charAt(i)) % MOD;
        ht = (ht * BASE + text.charAt(i)) % MOD;
    }
    for (int i = 0; ; i++) {
        // equal hashes mean PROBABLY equal strings: confirm to rule out a collision
        if (hp == ht && text.regionMatches(i, pat, 0, m)) return i;
        if (i + m == n) return -1;
        ht = (ht - text.charAt(i) * power % MOD + MOD) % MOD;   // drop left char (+MOD keeps it >= 0)
        ht = (ht * BASE + text.charAt(i + m)) % MOD;              // add right char
    }
}

rabinKarp("sadbutsad", "but") = 3. Expected time O(n + m); worst case O(n·m) if many windows collide (same hash, different string) and each needs a full check. Space O(1).

• Collisions are unavoidable (many strings, few hash values). Either verify on a hash match, as above, or use two independent hashes (two mods) so a false match is astronomically unlikely.
• Use long and a prime modulus around 10^9; hash * BASE then stays below about 1.4·10^11, far inside long.
• Rabin-Karp shines when you need many patterns of the same length, or substring comparisons: Longest Duplicate Substring (LC 1044) = binary search on length + rolling hash.

String hashing (prefix hashes)

Precompute the hash of every prefix once; then the hash of any substring comes out in O(1). Two substrings with equal hashes are (almost certainly) equal — so "compare two substrings" drops from O(length) to O(1).

static class StringHash {
    static final long MOD = 1_000_000_007L, BASE = 131;
    final long[] h, pw;                         // h[i] = hash of s[0..i), pw[i] = BASE^i
    StringHash(String s) {
        int n = s.length();
        h = new long[n + 1]; pw = new long[n + 1];
        pw[0] = 1;
        for (int i = 0; i < n; i++) {
            h[i + 1] = (h[i] * BASE + s.charAt(i)) % MOD;
            pw[i + 1] = pw[i] * BASE % MOD;
        }
    }
    long get(int l, int r) {                    // hash of s[l..r) in O(1)
        return ((h[r] - h[l] * pw[r - l]) % MOD + MOD) % MOD;
    }
}

For "abcabc", get(0, 3) == get(3, 6) is true ("abc" = "abc"). Build O(n), query O(1), space O(n).

Z-algorithm (briefly)

z[i] = length of the longest substring starting at i that matches a prefix of the string. It keeps a window [l, r) known to match the prefix and reuses earlier values inside it, much like KMP, for O(n) total.

static int[] zArray(String s) {
    int n = s.length();
    int[] z = new int[n];
    int l = 0, r = 0;                            // [l, r) = rightmost window matching a prefix
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = Math.min(r - i, z[i - l]);   // reuse what we know
        while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

zArray("aabxaab") = [0, 1, 0, 0, 3, 1, 0]. Pattern search: build pat + "$" + text (with a separator that appears in neither) and look for z[i] == m. For "aab$baabaa", z[5] = 3, so "aab" occurs in "baabaa" at index 5 - 4 = 1. Time and space O(n + m).

Problem: Repeated Substring Pattern (LC 459)

Is s some block repeated two or more times? Using LPS: the longest border (prefix = suffix) is lps[n-1]. The shortest possible repeating block has length n - lps[n-1], and s is a repetition exactly when that length divides n (and the border is non-empty).

static boolean repeatedSubstringPattern(String s) {
    int n = s.length();
    int[] lps = buildLps(s);
    int border = lps[n - 1];                    // longest prefix that is also a suffix
    int period = n - border;                    // candidate block length
    return border > 0 && n % period == 0;
}

// The one-line trick: s is a repetition iff s appears inside (s + s) with first and last char removed
static boolean repeatedTrick(String s) {
    return (s + s).substring(1, 2 * s.length() - 1).contains(s);
}

"abab" → true, "aba" → false, "abcabcabcabc" → true. LPS version: O(n) time and space. The trick uses contains (naive search), so it is O(n^2) worst case — say so if you use it.

Palindromes: expand around center

Every palindrome has a center: a single character (odd length, "aba") or the gap between two characters (even length, "abba"). There are 2n - 1 centers. From each, expand outward while both sides match.

// Longest Palindromic Substring (LC 5). O(n^2) time, O(1) space
static String longestPalindrome(String s) {
    int start = 0, best = 0;
    for (int c = 0; c < s.length(); c++) {
        int odd = expand(s, c, c);              // center on a char: "aba"
        int even = expand(s, c, c + 1);         // center between chars: "abba"
        int len = Math.max(odd, even);
        if (len > best) {
            best = len;
            start = c - (len - 1) / 2;          // works for both odd and even lengths
        }
    }
    return s.substring(start, start + best);
}
private static int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;                           // loop overshot by one on each side
}

"babad" → "bab", "cbbd" → "bb", "forgeeksskeegfor" → "geeksskeeg". Why this works: every palindrome is found when we expand from its own center, and expansion stops exactly at its edges. It beats the O(n^2)-space DP table dp[i][j] = s[i]==s[j] && dp[i+1][j-1].

Manacher's algorithm finds all palindromes in O(n) by reusing mirror information around the rightmost palindrome found so far (the same "reuse a window" idea as the Z-algorithm). Mention it by name; interviewers rarely expect the code. Related: Palindromic Substrings (LC 647) counts instead of maximises — same expansion, add (len + 1) / 2 per center.

Problem pointer: Minimum Window Substring (LC 76)

"Smallest substring of s containing all characters of t" is not a hashing or KMP problem — it is the variable-size sliding window pattern (see the sliding window section): expand the right pointer until the window is valid (counts of needed chars all met, tracked with a need array and a missing counter), then shrink from the left while it stays valid, recording the best length. Each pointer moves at most n times: O(|s| + |t|) time, O(alphabet) space.

29. Math & Number Theory

GCD and LCM (Euclid)

The greatest common divisor gcd(a, b) is the largest number dividing both. Euclid's rule: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a. It works because any number dividing a and b also divides a - k·b, which is what the remainder is.

static long gcd(long a, long b) {
    while (b != 0) {                 // gcd(a, b) = gcd(b, a % b)
        long t = a % b;
        a = b;
        b = t;
    }
    return Math.abs(a);
}
static long lcm(long a, long b) {
    return a / gcd(a, b) * b;        // divide FIRST to avoid overflow
}

gcd(48, 18) = 6, lcm(4, 6) = 12, lcm(10^9, 999,999,999) = 999,999,999,000,000,000 (fits in long only because we divide before multiplying). Time O(log min(a, b)) — the numbers at least halve every two steps. Uses: simplifying fractions, "water jug" problems, GCD of an array (fold gcd over it), slopes as reduced (dy, dx) pairs in Max Points on a Line.

Sieve of Eratosthenes

To find all primes up to n: start with every number marked prime. For each prime i, cross out its multiples. Start crossing at i·i — smaller multiples like 2i, 3i were already crossed out by smaller primes. Stop when i·i > n.

static boolean[] sieve(int n) {                 // isPrime[0..n]
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;
    for (int i = 2; (long) i * i <= n; i++) {   // long: i*i can overflow near MAX_VALUE
        if (!isPrime[i]) continue;
        for (int j = i * i; j <= n; j += i)     // start at i*i
            isPrime[j] = false;
    }
    return isPrime;
}

sieve(30) marks 2 3 5 7 11 13 17 19 23 29. Time O(n log log n) — nearly linear. Space O(n). To test a single number, trial division up to sqrt(n) is enough: O(sqrt n).

Problem: Count Primes (LC 204)

// Count primes strictly less than n
static int countPrimes(int n) {
    if (n < 3) return 0;
    boolean[] composite = new boolean[n];       // false = still possibly prime
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (composite[i]) continue;
        count++;                                // i survived every smaller prime
        for (long j = (long) i * i; j < n; j += i) composite[(int) j] = true;
    }
    return count;
}

countPrimes(10) = 4 (2, 3, 5, 7); countPrimes(1_000_000) = 78,498. Time O(n log log n), space O(n). Using composite (default false) saves the Arrays.fill.

Prime factorisation

Divide out 2 as many times as possible, then 3, then 4 (never divides — its 2s are gone), and so on up to sqrt(n). Whatever is left above 1 is itself a prime (it cannot have two factors both bigger than sqrt).

static Map<Long, Integer> factorize(long n) {
    Map<Long, Integer> f = new TreeMap<>();
    for (long p = 2; p * p <= n; p++) {
        while (n % p == 0) {                    // divide out p completely
            f.merge(p, 1, Integer::sum);
            n /= p;
        }
    }
    if (n > 1) f.merge(n, 1, Integer::sum);     // leftover is a prime > sqrt
    return f;
}

factorize(360) = {2=3, 3=2, 5=1} (360 = 2^3 · 3^2 · 5). Time O(sqrt n), space O(log n). For factorising many numbers, sieve the smallest prime factor spf[x] once, then each number factors in O(log x) by repeatedly dividing by spf.

Fast exponentiation (binary power)

To get a^e, don't multiply e times. Write e in binary: a^13 = a^8 · a^4 · a^1 since 13 = 1101 in binary. Keep squaring the base (a, a^2, a^4, a^8…) and multiply it into the result whenever the current bit of e is 1. That is O(log e) multiplications.

static long modPow(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    if (base < 0) base += mod;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result * base % mod;  // this bit is set: multiply it in
        base = base * base % mod;                          // square for the next bit
        exp >>= 1;
    }
    return result;
}

modPow(2, 10, 10^9+7) = 1024; modPow(2, 10^9, 10^9+7) = 140625001 in about 30 steps. Time O(log exp), space O(1). Safe because both factors are below mod ~ 10^9, so their product is below ~10^18 < Long.MAX_VALUE (~9.2·10^18).

Problem: Pow(x, n) (LC 50)

static double myPow(double x, int n) {
    long e = n;                       // long: -Integer.MIN_VALUE does not fit in an int
    if (e < 0) { x = 1 / x; e = -e; }
    double result = 1;
    while (e > 0) {
        if ((e & 1) == 1) result *= x;
        x *= x;
        e >>= 1;
    }
    return result;
}

myPow(2.0, 10) = 1024.0, myPow(2.0, -2) = 0.25, myPow(1.0, Integer.MIN_VALUE) = 1.0. Time O(log n), space O(1). The classic bug is writing n = -n on an int: -(-2147483648) is still -2147483648.

Modular arithmetic rules and 1_000_000_007

When answers are huge (counting paths, arrangements), problems ask for the result mod 10^9 + 7. Why this number: it is prime (so division works via inverses, below), it fits in an int, and the product of two values below it fits in a long.

Modular inverse via Fermat

The inverse of a mod p is the number x with a · x ≡ 1 (mod p) — the "mod version" of 1/a. Fermat's little theorem says that for a prime p and a not divisible by p, a^(p-1) ≡ 1. Split one factor off: a · a^(p-2) ≡ 1, so a^(p-2) is the inverse.

static final int MOD = 1_000_000_007;

static long modInverse(long a) {      // valid when MOD is prime and a % MOD != 0
    return modPow(a, MOD - 2, MOD);   // a^(p-2) = a^-1
}

modInverse(2) = 500000004, and 2 · 500000004 % MOD = 1. Time O(log p). If the modulus is not prime, use the extended Euclidean algorithm instead (the inverse exists only when gcd(a, m) = 1).

nCr — Pascal's triangle and factorials mod p

C(n, r) = ways to choose r items from n. Two ways to compute it, depending on size.

Pascal's triangle (n up to a few thousand): C(n, r) = C(n-1, r-1) + C(n-1, r) — either item n is chosen or it isn't. Only additions, so it works with any modulus, even non-prime.

static long[][] pascal(int n) {       // C[i][j] for i, j <= n. O(n^2) time and space
    long[][] C = new long[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;  // take item i or not
    }
    return C;
}

Factorials (n up to 10^6 or more): C(n, r) = n! / (r! · (n-r)!). Division mod p means multiplying by inverses. Precompute fact[] and invFact[] once; each query is then O(1).

static long[] fact, invFact;

static void precompute(int n) {                          // O(n + log MOD)
    fact = new long[n + 1];
    invFact = new long[n + 1];
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    invFact[n] = modInverse(fact[n]);                    // one expensive inverse...
    for (int i = n; i > 0; i--)
        invFact[i - 1] = invFact[i] * i % MOD;           // ...then walk down: 1/(i-1)! = i/i!
}
static long nCr(int n, int r) {                          // O(1) per query
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

Both give C(5, 2) = 10 and C(10, 3) = 120; nCr(100000, 50000) mod 10^9+7 = 149033233. Note the multiplication chain: take % MOD after each product, or the second multiplication overflows.

Overflow handling in Java

Rules of thumb: anything that can exceed ~2·10^9 goes in a long; anything that can exceed ~9·10^18 needs mod arithmetic or BigInteger. In "reverse integer" style problems, check result > (Integer.MAX_VALUE - digit) / 10 before multiplying.

Randomness: reservoir sampling

Pick one item uniformly at random from a stream whose length you don't know (and can't store). Keep the k-th item with probability 1/k, replacing the current choice. Each item ends up chosen with probability exactly 1/n: item k is picked with 1/k, then survives each later step j with (j-1)/j, and the product telescopes to 1/n.

static int reservoirPick(Iterator<Integer> stream, Random rnd) {
    int chosen = -1, seen = 0;
    while (stream.hasNext()) {
        int x = stream.next();
        seen++;
        if (rnd.nextInt(seen) == 0) chosen = x;   // keep x with probability 1/seen
    }
    return chosen;
}

Picking from [0..4] 100,000 times (seed 42) gave counts [20023, 20080, 19959, 19937, 20001] — about 20% each, as expected. Time O(n), space O(1). Used in Linked List Random Node (LC 382) and Random Pick Index (LC 398). To keep k items: fill the first k, then item i replaces a random slot with probability k/i. For shuffling an array, use Fisher–Yates: for i from the end, swap a[i] with a[rnd.nextInt(i + 1)].

Problem: Excel Sheet Column Number / Title (LC 171, 168)

Columns are base 26, but with digits 1..26 instead of 0..25 (there is no "zero" letter). Reading is ordinary base conversion; writing needs n-- first to shift into 0-based digits.

static int titleToNumber(String col) {   // "AB" -> 28
    int result = 0;
    for (char c : col.toCharArray())
        result = result * 26 + (c - 'A' + 1);
    return result;
}
static String convertToTitle(int n) {    // 28 -> "AB"
    StringBuilder sb = new StringBuilder();
    while (n > 0) {
        n--;                             // shift to 0-based: A=0 ... Z=25
        sb.append((char) ('A' + n % 26));
        n /= 26;
    }
    return sb.reverse().toString();
}

"A" → 1, "AB" → 28, "ZY" → 701; 28 → "AB", 701 → "ZY", 26 → "Z". Both O(log n) time. A version without n-- that uses (char) ('A' + n % 26 - 1) turns 26 into "A@".

Problem: Happy Number (LC 202)

Repeatedly replace n by the sum of the squares of its digits. Happy if it reaches 1; otherwise it falls into a loop. A loop in a sequence is a cycle in a linked list — use Floyd's slow/fast pointers instead of a HashSet.

static boolean isHappy(int n) {
    int slow = n, fast = next(n);
    while (fast != 1 && slow != fast) {  // Floyd cycle detection
        slow = next(slow);
        fast = next(next(fast));
    }
    return fast == 1;
}
private static int next(int n) {
    int sum = 0;
    while (n > 0) { int d = n % 10; sum += d * d; n /= 10; }
    return sum;
}

19 → true (1 + 81 = 82 → 68 → 100 → 1); 2 → false. Time O(log n) per step, and the values quickly drop below a few hundred, so the loop is short. Space O(1). Why the loop must exist: for any number with 4+ digits, the digit-square sum is smaller than the number, so values stay bounded and must eventually repeat.

30. Two Pointers

How to recognise it

• The input is a sorted array (or sorting it is cheap and allowed) and you need a pair or triplet with some sum or difference.
• "Is this string a palindrome", "reverse", "compare from both ends".
• "Remove / move elements in place", "return the new length", "O(1) extra space".
• "Container", "trap water", "two lines" — answers that depend on a left wall and a right wall.
• The brute force is two nested loops over pairs, and the array order lets you throw away one side each step.

How it works

Why is it safe to throw candidates away? Take Two Sum on a sorted array. If a[L] + a[R] is too big, then a[R] plus anything to the right of L is even bigger, so a[R] can never be part of the answer. Drop it: R--. If the sum is too small, the same logic drops a[L]. Every step removes one element from consideration, so there are at most n steps.

Same-direction pointers work like a filter. fast looks at every element once. When a[fast] should be kept, it is copied to a[slow] and slow moves on. At the end, a[0..slow-1] is the answer and slow is its length.

Java template

// Variant 1: opposite ends — pointers start at both ends and walk toward each other.
public int[] oppositeEnds(int[] a, int target) {
    int left = 0, right = a.length - 1;
    while (left < right) {                      // stop when they meet
        int value = a[left] + a[right];         // CHANGES: what you compute from the pair
        if (value == target) {                  // CHANGES: the "found / record answer" step
            return new int[]{left, right};
        } else if (value < target) {
            left++;                             // need a bigger value -> move left inward
        } else {
            right--;                            // need a smaller value -> move right inward
        }
    }
    return new int[]{-1, -1};                   // CHANGES: what "not found" means
}

// Variant 2: same direction — a slow "write" pointer and a fast "read" pointer.
public int sameDirection(int[] a) {
    int slow = 0;                               // next position to write a kept element
    for (int fast = 0; fast < a.length; fast++) {
        if (keep(a, slow, fast)) {              // CHANGES: the rule for keeping a[fast]
            a[slow] = a[fast];
            slow++;
        }
    }
    return slow;                                // length of the kept prefix a[0..slow-1]
}

Classic problems

Two Sum II — Input Array Is Sorted, LC 167 (Medium)

Given a 1-indexed sorted array, return the positions of the two numbers that add up to target.

Key insight: sorted order tells you which way to move. Too big, move right in; too small, move left in. No HashMap needed, so space is O(1).

public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return new int[]{left + 1, right + 1}; // 1-indexed
        if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1}; // problem guarantees one answer
}
// twoSum([2,7,11,15], 9)  -> [1, 2]
// twoSum([1,3,4,6,8,11], 10) -> [3, 4]

Time O(n), Space O(1).

3Sum, LC 15 (Medium)

Return all unique triplets [a, b, c] in the array with a + b + c == 0.

Key insight: sort, then fix the first number nums[i] and run Two Sum II on the rest looking for -nums[i]. Skipping equal neighbours (for i, left and right) removes duplicate triplets without a Set.

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) break;                          // smallest is positive: no zero sum
        if (i > 0 && nums[i] == nums[i - 1]) continue;   // skip duplicate first number
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) {
                left++;
            } else if (sum > 0) {
                right--;
            } else {
                result.add(List.of(nums[i], nums[left], nums[right]));
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) left++;   // skip dup
                while (left < right && nums[right] == nums[right + 1]) right--; // skip dup
            }
        }
    }
    return result;
}
// threeSum([-1,0,1,2,-1,-4]) -> [[-1, -1, 2], [-1, 0, 1]]
// threeSum([0,0,0,0])        -> [[0, 0, 0]]

Time O(n^2) (the sort is O(n log n), then n two-pointer passes), Space O(1) extra apart from the output (the sort may use O(log n)).

Container With Most Water, LC 11 (Medium)

Each height[i] is a vertical line. Pick two lines that, with the x-axis, hold the most water.

Key insight: area = min(h[L], h[R]) * (R - L). Moving inward always shrinks the width, so the only hope of a bigger area is a taller short wall. Moving the taller wall can never help, so move the shorter one.

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1, best = 0;
    while (left < right) {
        int h = Math.min(height[left], height[right]);
        best = Math.max(best, h * (right - left));
        // The shorter wall limits the area. Moving the taller one can only make it worse,
        // so always move the shorter one.
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}
// maxArea([1,8,6,2,5,4,8,3,7]) -> 49   (lines at index 1 and 8: min(8,7) * 7)

Time O(n), Space O(1).

Remove Duplicates from Sorted Array, LC 26 (Easy)

Remove duplicates in place so each value appears once; return the count k of unique values (they must be in nums[0..k-1]).

Key insight: same-direction pointers. Because the array is sorted, a value is new exactly when it differs from the last value written, nums[slow - 1].

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 1;                                   // nums[0] is always kept
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow - 1]) {         // new value (array is sorted)
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}
// [0,0,1,1,1,2,2,3,3,4] -> 5, first five = [0, 1, 2, 3, 4]

Time O(n), Space O(1).

Trapping Rain Water, LC 42 (Hard)

Given bar heights, compute how much rain water is trapped between the bars.

Key insight: water above bar i is min(maxLeft, maxRight) - height[i]. With two pointers you don't need both maxima: if height[left] < height[right], there is a wall on the right at least as tall as anything on the left, so the level at left is decided by leftMax alone.

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            // Right side has a wall at least this tall, so leftMax decides the level here.
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}
// trap([0,1,0,2,1,0,1,3,2,1,2,1]) -> 6
// trap([4,2,0,3,2,5])             -> 9

Time O(n), Space O(1). (The prefix-max version uses two extra arrays: O(n) space.)

Valid Palindrome, LC 125 (Easy)

After lower-casing and dropping everything that is not a letter or digit, does the string read the same both ways?

Key insight: compare from both ends and skip junk characters on the fly, instead of building a cleaned copy of the string.

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
// isPalindrome("A man, a plan, a canal: Panama") -> true
// isPalindrome("race a car")                     -> false

Time O(n), Space O(1).

Practice list

• LC 344 Reverse String (Easy)
• LC 283 Move Zeroes (Easy)
• LC 977 Squares of a Sorted Array (Easy)
• LC 88 Merge Sorted Array (Easy)
• LC 680 Valid Palindrome II (Easy)
• LC 75 Sort Colors (Medium) — three pointers, the Dutch national flag
• LC 16 3Sum Closest (Medium)
• LC 881 Boats to Save People (Medium)
• LC 18 4Sum (Medium)

31. Sliding Window

How to recognise it

• "Contiguous subarray" or "substring" (not subsequence: a subsequence can skip elements, a window cannot).
• "Longest / shortest / maximum / minimum subarray such that ...".
• "At most k distinct", "without repeating", "contains all characters of t", "an anagram / permutation of p".
• "Every window of size k", "average of each k consecutive elements".
• The rule is monotonic: if a window is invalid, making it bigger keeps it invalid. That is what makes shrinking from the left safe. (With negative numbers and a sum target, this breaks; use prefix sums instead.)

How it works

The variable-window loop has three beats: expand (take s[right] in and update counts), shrink (while the window is invalid, remove s[left] and move left), record (the window is now valid; compare its size to the best). For "longest" problems you record after shrinking. For "shortest" problems (like Minimum Window Substring) you record inside the shrink loop, while the window is still valid.

For character counts, an int[128] (all ASCII) or int[26] (lowercase letters) is faster and simpler than a HashMap<Character, Integer>. Use a HashMap when the "characters" are arbitrary integers, like fruit types.

Java template

// Fixed-size window of length k: add the new right element, drop the one that fell off.
public int fixedWindow(int[] a, int k) {
    int windowSum = 0, best = Integer.MIN_VALUE;        // CHANGES: the window state
    for (int right = 0; right < a.length; right++) {
        windowSum += a[right];                          // 1. add a[right]
        if (right >= k - 1) {                           // window is full (size k)
            best = Math.max(best, windowSum);           // 2. record the answer
            windowSum -= a[right - k + 1];              // 3. remove the leftmost element
        }
    }
    return best;
}

// Variable-size window: expand right every step, shrink left while the window is invalid.
public int variableWindow(String s) {
    int[] count = new int[128];                 // CHANGES: window state (counts, sum, map...)
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        count[c]++;                             // 1. expand: take s[right] into the window
        while (invalid(count, c)) {             // 2. shrink: CHANGES: the "invalid" rule
            count[s.charAt(left)]--;
            left++;
        }
        best = Math.max(best, right - left + 1);// 3. window [left..right] is valid: record
    }
    return best;
}

Classic problems

Maximum Sum Subarray of Size K (Easy)

Return the largest sum of any k consecutive elements. (LC 643 Maximum Average Subarray I is the same problem divided by k.)

Key insight: fixed window. Moving the window by one changes the sum by +nums[right] - nums[right - k], so each step is O(1).

public int maxSumSubarray(int[] nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];   // first window
    int best = windowSum;
    for (int right = k; right < nums.length; right++) {
        windowSum += nums[right] - nums[right - k];     // slide by one
        best = Math.max(best, windowSum);
    }
    return best;
}
// maxSumSubarray([2,1,5,1,3,2], 3)     -> 9   (5 + 1 + 3)
// maxSumSubarray([1,12,-5,-6,50,3], 4) -> 51  (12 - 5 - 6 + 50)

Time O(n), Space O(1).

Longest Substring Without Repeating Characters, LC 3 (Medium)

Return the length of the longest substring with all distinct characters.

Key insight: the template works (shrink while count[c] > 1). A faster trick: remember where each character was last seen and jump left straight past it. Math.max stops left from jumping backwards to an old copy that is already outside the window (try "abba").

public int lengthOfLongestSubstring(String s) {
    int[] lastSeen = new int[128];          // lastSeen[c] = (last index of c) + 1, 0 = never
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        left = Math.max(left, lastSeen[c]); // jump left past the previous copy of c
        lastSeen[c] = right + 1;
        best = Math.max(best, right - left + 1);
    }
    return best;
}
// "abcabcbb" -> 3 ("abc"),  "bbbbb" -> 1,  "pwwkew" -> 3 ("wke"),  "abba" -> 2

Time O(n), Space O(1) (128 slots, fixed).

Longest Repeating Character Replacement, LC 424 (Medium)

You may change at most k characters of an uppercase string. Return the longest substring of one repeated letter you can get.

Key insight: a window is fine if size - (count of its most common letter) <= k: those are the letters you'd replace. maxFreq is never decreased when shrinking. That is safe, because the answer only grows when a window beats the old maxFreq, and a stale value just keeps the window from shrinking too much.

public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0, maxFreq = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);
        // chars to replace = window size - most frequent char count
        while (right - left + 1 - maxFreq > k) {
            count[s.charAt(left) - 'A']--;
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}
// characterReplacement("ABAB", 2)    -> 4
// characterReplacement("AABABBA", 1) -> 4

Time O(n), Space O(1).

Minimum Window Substring, LC 76 (Hard)

Return the shortest substring of s that contains every character of t (with multiplicity), or "" if none.

Key insight: keep need[c] = how many more of c the window needs (it goes negative for extras) and a single counter missing. When missing == 0 the window is valid: record it, then shrink until it breaks. This is a "shortest" problem, so you record inside the shrink loop.

public String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int missing = t.length();               // chars of t still not covered by the window
    int left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
    for (int right = 0; right < s.length(); right++) {
        if (need[s.charAt(right)]-- > 0) missing--;   // this char was actually needed
        while (missing == 0) {                         // window covers t: try to shrink
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            if (++need[s.charAt(left)] > 0) missing++; // we just dropped a needed char
            left++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}
// minWindow("ADOBECODEBANC", "ABC") -> "BANC"
// minWindow("a", "aa")              -> ""

Time O(|s| + |t|), Space O(1) (128 slots).

Permutation in String, LC 567 (Medium)

Does s2 contain some permutation (anagram) of s1 as a substring?

Key insight: an anagram has the same length and the same letter counts. So slide a fixed window of size s1.length() over s2 and compare two int[26] arrays; comparing 26 numbers is O(1).

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    int[] need = new int[26], window = new int[26];
    for (char c : s1.toCharArray()) need[c - 'a']++;
    int k = s1.length();
    for (int right = 0; right < s2.length(); right++) {
        window[s2.charAt(right) - 'a']++;
        if (right >= k) window[s2.charAt(right - k) - 'a']--;  // keep size exactly k
        if (Arrays.equals(need, window)) return true;           // 26 compares: O(1)
    }
    return false;
}
// checkInclusion("ab", "eidbaooo") -> true  ("ba")
// checkInclusion("ab", "eidboaoo") -> false

Time O(26·n) = O(n), Space O(1).

Fruit Into Baskets, LC 904 (Medium)

You have two baskets, each holding one fruit type. Walking right from any start, pick one fruit per tree. What is the most fruit you can collect?

Key insight: in plain words, "longest subarray with at most 2 distinct values". Keep a map of type to count; shrink while the map has more than 2 keys, removing a key when its count hits zero.

public int totalFruit(int[] fruits) {
    Map<Integer, Integer> basket = new HashMap<>();     // fruit type -> count in window
    int left = 0, best = 0;
    for (int right = 0; right < fruits.length; right++) {
        basket.merge(fruits[right], 1, Integer::sum);
        while (basket.size() > 2) {                      // more than 2 types: shrink
            int f = fruits[left++];
            if (basket.merge(f, -1, Integer::sum) == 0) basket.remove(f);
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}
// totalFruit([1,2,1]) -> 3,  [0,1,2,2] -> 3,  [1,2,3,2,2] -> 4

Time O(n), Space O(1) (the map never holds more than 3 keys).

Practice list

• LC 643 Maximum Average Subarray I (Easy)
• LC 219 Contains Duplicate II (Easy)
• LC 1456 Maximum Number of Vowels in a Substring of Given Length (Medium)
• LC 209 Minimum Size Subarray Sum (Medium)
• LC 438 Find All Anagrams in a String (Medium)
• LC 1004 Max Consecutive Ones III (Medium)
• LC 713 Subarray Product Less Than K (Medium)
• LC 992 Subarrays with K Different Integers (Hard) — exactly(k) = atMost(k) - atMost(k - 1)
• LC 30 Substring with Concatenation of All Words (Hard)

32. Prefix Sum & Difference Arrays

How to recognise it

• Many queries for the sum (or count, or XOR) of a range on an array that doesn't change.
• "Number of subarrays with sum equal to k", "divisible by k", "equal number of 0s and 1s", especially when the array has negative numbers (so a sliding window won't work).
• "Product of all elements except this one" (prefix products from both sides).
• "Add v to every element in [l, r]", bookings, passengers getting on and off, "how many overlaps at each point".
• 2D grid with "sum of the sub-rectangle" queries.

How it works

Picture prefix[i] sitting on the boundary before a[i]: it is the total of everything to its left. The sum between two boundaries is the difference of their totals. Using size n + 1 with prefix[0] = 0 removes the special case for ranges that start at 0.

Prefix sum + HashMap. A subarray a[j+1..i] sums to k exactly when prefix[i+1] - prefix[j+1] = k, i.e. when an earlier prefix equals current - k. So walk once, keep a map of "prefix value → how many times seen", and at each step look up current - k. This is the Two Sum idea applied to prefix sums.

Difference array. Here is "add 2 to [1..3]" then "add 3 to [2..4]" on an array of 5 zeros:

2D prefix sums. p[r][c] holds the sum of the rectangle from (0,0) to (r-1,c-1). Build with p[r+1][c+1] = cell + above + left - aboveLeft (the top-left block was added twice). Query any rectangle with the same inclusion-exclusion: big corner, minus the strip above, minus the strip to the left, plus the top-left block that was subtracted twice.

Java template

// 1. Build: prefix[i] = sum of the first i elements, so prefix[0] = 0.
static long[] buildPrefix(int[] a) {
    long[] prefix = new long[a.length + 1];          // one extra slot: no "i - 1" edge case
    for (int i = 0; i < a.length; i++) prefix[i + 1] = prefix[i] + a[i];
    return prefix;
}
// Sum of a[l..r] inclusive, O(1)
static long rangeSum(long[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

// 2. Prefix sum + HashMap: count subarrays whose "sum" hits a target.
static int countSubarrays(int[] a, int k) {
    Map<Integer, Integer> seen = new HashMap<>();   // CHANGES: store count, or first index
    seen.put(0, 1);                                 // empty prefix: sum 0 seen once
    int sum = 0, answer = 0;
    for (int x : a) {
        sum += x;                                   // CHANGES: what you accumulate
        answer += seen.getOrDefault(sum - k, 0);    // earlier prefixes that make sum k
        seen.merge(sum, 1, Integer::sum);
    }
    return answer;
}

// 3. Difference array: many "add v to a[l..r]" updates, then read the final array once.
static int[] applyUpdates(int n, int[][] updates) {  // each update = {l, r, v}
    int[] diff = new int[n + 1];                     // one extra slot for r + 1
    for (int[] u : updates) {
        diff[u[0]] += u[2];                          // start adding v at l
        diff[u[1] + 1] -= u[2];                      // stop adding v after r
    }
    int[] result = new int[n];
    int running = 0;
    for (int i = 0; i < n; i++) {                    // prefix sum of diff = final values
        running += diff[i];
        result[i] = running;
    }
    return result;
}

Classic problems