DSA in Java — Easy Notes

1. How to Approach a Problem

Key points

• Understand the question first. Say it again in your own words.
• Ask questions: Can the array be empty? Can numbers be negative? Are there duplicates?
• Try a tiny example by hand, like [2, 7, 11]. Write the answer you expect.
• Start with the simple (brute force) idea. Brute force means "try every possibility". It is slow, but correct.
• Then improve it. Ask: "What work am I repeating? Can a HashMap or sorting help?"
• Test your code with your tiny example and with edge cases (empty input, one item).

Step by step: "Two Sum" (find two numbers that add up to a target)

// Step 4: the simple (brute force) answer. Check every pair.
static int[] twoSumBrute(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {          // first number
        for (int j = i + 1; j < nums.length; j++) {  // second number, after the first
            if (nums[i] + nums[j] == target) {        // do they add up?
                return new int[] { i, j };            // yes: return both positions
            }
        }
    }
    return new int[] { -1, -1 };                      // no pair found
}

Time & space: O(n²) time — every pair is checked. O(1) extra space. (The faster HashMap version is in topic 7.)

2. Big-O & Complexity

Key points

• O(1) = constant. Same time for any size. Example: arr[5].
• O(log n) = we cut the problem in half each step. Example: binary search.
• O(n) = we look at each item once. Example: one loop.
• O(n log n) = good sorting. O(n²) = a loop inside a loop.
• Drop constants: O(2n) is just O(n). Keep the biggest part: O(n² + n) is O(n²).
• Rough rule: a computer does about 100 million simple steps per second.

How many steps?

static void examples(int[] arr) {
    int first = arr[0];                       // O(1): one step, any size

    int sum = 0;
    for (int x : arr) {                       // O(n): one pass over the array
        sum += x;
    }

    int pairs = 0;
    for (int i = 0; i < arr.length; i++) {     // O(n²): loop inside a loop
        for (int j = 0; j < arr.length; j++) {
            pairs++;
        }
    }
    System.out.println(first + " " + sum + " " + pairs);
}

Time & space: count the loops. One loop over n = O(n). A loop inside a loop = O(n²). Halving each time = O(log n).

3. Recursion & the Call Stack

Key points

• Every recursive function needs: a base case (stop) and a recursive case (call itself on a smaller input).
• Forget the base case → the function never stops → StackOverflowError.
• Each waiting call uses memory on the stack. So recursion depth n = O(n) space.
• Trust the function: assume fact(n - 1) already works, and just use its answer.
• Recursion is the base of trees, backtracking, and divide & conquer.

Dry run: fact(3)

static int fact(int n) {
    if (n <= 1) {              // base case: stop here
        return 1;
    }
    return n * fact(n - 1);    // recursive case: smaller problem
}

Time & space: O(n) time — n calls. O(n) space — n calls wait on the stack at the same time.

4. Java Toolkit for DSA

Key points

• int[] = fixed size array. ArrayList = array that can grow.
• HashMap = key → value pairs. HashSet = unique items. Both find things in O(1) on average.
• ArrayDeque = use it as a stack or a queue. (Avoid the old Stack class.)
• PriorityQueue = always gives you the smallest item first (a heap).
• Arrays.sort(arr) sorts an array. Collections.sort(list) sorts a list.
• Collections hold objects, so write Integer, not int: List<Integer>.

static void toolkitDemo() {
    List<Integer> list = new ArrayList<>();       // growing list
    list.add(5);                                    // [5]

    Map<String, Integer> age = new HashMap<>();   // key -> value
    age.put("Ali", 25);
    int a = age.getOrDefault("Sara", 0);            // 0 if key is missing

    Set<Integer> seen = new HashSet<>();          // unique items
    seen.add(3);
    boolean has = seen.contains(3);                 // true

    Deque<Integer> stack = new ArrayDeque<>();    // stack
    stack.push(1);
    int top = stack.pop();                          // 1

    Queue<Integer> queue = new ArrayDeque<>();    // queue
    queue.offer(1);
    int front = queue.poll();                       // 1

    PriorityQueue<Integer> heap = new PriorityQueue<>();  // min-heap
    heap.offer(4);
    heap.offer(2);
    int smallest = heap.poll();                     // 2

    int[] arr = { 3, 1, 2 };
    Arrays.sort(arr);                               // [1, 2, 3]
    System.out.println(a + " " + has + " " + top + " " + front + " " + smallest);
}

Time & space: HashMap/HashSet get and put: O(1) on average. PriorityQueue offer/poll: O(log n). Sorting: O(n log n).

5. Bit Manipulation

Key points

• AND a & b: 1 only if both bits are 1.
• OR a | b: 1 if at least one bit is 1.
• XOR a ^ b: 1 if the bits are different. Important: x ^ x = 0 and x ^ 0 = x.
• Shift: x << 1 doubles x. x >> 1 halves x.
• (n & 1) == 1 means n is odd. n & (n - 1) removes the lowest 1 bit.

Dry run: 5 & 3, 5 | 3, 5 ^ 3

// Single Number: every number appears twice except one.
// Pairs cancel out with XOR (x ^ x = 0), so only the single one is left.
static int singleNumber(int[] nums) {
    int result = 0;
    for (int x : nums) {
        result = result ^ x;      // XOR everything together
    }
    return result;
}

// Count how many bits are 1
static int countOnes(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);          // remove the lowest 1 bit
        count++;
    }
    return count;
}

Time & space: singleNumber is O(n) time, O(1) space — one pass, one variable.

6. Arrays & Strings

Key points

• Reading or changing arr[i] is O(1) — instant.
• Inserting or deleting in the middle is O(n) — all later items must move over.
• An int[] has a fixed size. Use ArrayList if it must grow.
• Java strings can't be changed (they are immutable). To build a string piece by piece, use StringBuilder.
• Useful: s.length(), s.charAt(i), s.toCharArray().

Dry run: find the largest number in [3, 1, 4]

static int findMax(int[] arr) {
    int max = arr[0];                         // start with the first item
    for (int i = 1; i < arr.length; i++) {    // look at every other item
        if (arr[i] > max) {                   // found a bigger one?
            max = arr[i];                     // remember it
        }
    }
    return max;
}

static String reverse(String s) {
    StringBuilder sb = new StringBuilder();   // fast way to build a string
    for (int i = s.length() - 1; i >= 0; i--) {  // walk from the end
        sb.append(s.charAt(i));
    }
    return sb.toString();                     // "abc" -> "cba"
}

Time & space: findMax is O(n) — we look at each item once. O(1) extra space.

7. Hashing

Key points

• Add, find and remove are O(1) on average.
• Use a HashSet for "have I seen this before?"
• Use a HashMap for counting: "how many times does each word appear?"
• Use a HashMap to remember positions: "where did I see this number?"
• Hashing trades memory for speed: O(n) extra space to save time.
• A HashMap has no order. Use TreeMap if you need sorted keys (topic 14).

Dry run: Two Sum, nums = [2, 7, 11], target = 9

static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // number -> its index
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];                   // the partner we want
        if (seen.containsKey(need)) {                  // seen the partner before?
            return new int[] { seen.get(need), i };    // yes: done
        }
        seen.put(nums[i], i);                          // no: remember this number
    }
    return new int[] { -1, -1 };                       // no answer
}

// Count how often each character appears
static Map<Character, Integer> countChars(String s) {
    Map<Character, Integer> count = new HashMap<>();
    for (char c : s.toCharArray()) {
        count.put(c, count.getOrDefault(c, 0) + 1);   // old count + 1
    }
    return count;
}

Time & space: O(n) time — one pass, each lookup is O(1). O(n) space for the map.

8. Linked Lists

Key points

• No index. To find the 5th item, walk from the head. That is O(n).
• Adding or removing at the head is O(1) — just change one arrow.
• Always check for null before you use node.next.
• A dummy node (a fake first node) makes many problems easier. You return dummy.next.
• Doubly linked list: each node also points back to the previous node.

Dry run: count the nodes in 3 → 1 → 2

class ListNode {
    int val;           // the value stored here
    ListNode next;     // arrow to the next node (or null)
    ListNode(int val) { this.val = val; }
}

static int length(ListNode head) {
    int count = 0;
    ListNode cur = head;          // start at the head
    while (cur != null) {         // until we fall off the end
        count++;
        cur = cur.next;           // move to the next node
    }
    return count;
}

static ListNode addToFront(ListNode head, int value) {
    ListNode node = new ListNode(value);   // make a new node
    node.next = head;                      // point it at the old head
    return node;                           // the new node is the new head
}

Time & space: length is O(n) — we visit each node once. addToFront is O(1). Both use O(1) extra space.

9. Stacks

Key points

• push(x) adds on top. pop() removes the top. peek() looks at the top without removing it.
• All three are O(1).
• In Java use Deque<Integer> stack = new ArrayDeque<>();
• Use a stack for matching brackets, "undo" features, and going back to the most recent thing.
• Recursion uses a stack inside (the call stack, topic 3).

Dry run: Valid Parentheses on "([])"

static boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);                        // opening: save it
        } else {
            if (stack.isEmpty()) return false;    // closing with nothing open
            char top = stack.pop();               // the latest opening bracket
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();                       // nothing left open = valid
}

Time & space: O(n) time — each character is pushed and popped at most once. O(n) space for the stack.

10. Queues & Deques

Key points

• offer(x) adds at the back. poll() removes from the front. peek() looks at the front.
• All are O(1) with ArrayDeque.
• poll() returns null when the queue is empty — check isEmpty() first.
• Queues are the heart of BFS (breadth-first search, topics 16 and 38): visit things level by level.
• A deque has offerFirst, offerLast, pollFirst, pollLast.

Dry run: a queue step by step

// Number of Recent Calls: count calls in the last 3000 ms
class RecentCounter {
    Queue<Integer> times = new ArrayDeque<>();   // call times, oldest at the front

    int ping(int t) {
        times.offer(t);                              // new call joins at the back
        while (times.peek() < t - 3000) {            // oldest call is too old?
            times.poll();                            // remove it from the front
        }
        return times.size();                         // calls left are all recent
    }
}

Time & space: each time is added once and removed once, so O(1) on average per call. O(n) space for the queue.

11. Heaps & Priority Queues

Key points

• peek() (see the top) is O(1). offer and poll are O(log n).
• Java's PriorityQueue is a min-heap by default.
• Max-heap: new PriorityQueue<>(Collections.reverseOrder()).
• Great for "the k largest", "the k smallest", "the next most important".
• Trick: to find the k largest, keep a min-heap of size k. The top is the k-th largest.

Dry run: 2nd largest in [3, 2, 1, 5], k = 2

static int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();  // min-heap
    for (int x : nums) {
        heap.offer(x);                // add the number
        if (heap.size() > k) {        // too many?
            heap.poll();              // remove the smallest
        }
    }
    return heap.peek();               // smallest of the k largest
}

Time & space: O(n log k) time — n numbers, each heap step costs log k. O(k) space.

12. Binary Trees

Key points

• Each node has a value, a left child and a right child (either can be null).
• Height / depth = the number of levels from the root to the deepest leaf.
• Most tree problems use recursion: solve for the left side, solve for the right side, combine.
• The base case is almost always if (root == null).
• DFS (depth-first) uses recursion. BFS (breadth-first) uses a queue. More in topic 38.

Dry run: maxDepth on the tree above

class TreeNode {
    int val;
    TreeNode left, right;          // children (can be null)
    TreeNode(int val) { this.val = val; }
}

static int maxDepth(TreeNode root) {
    if (root == null) return 0;            // empty tree has depth 0
    int left = maxDepth(root.left);        // depth of the left side
    int right = maxDepth(root.right);      // depth of the right side
    return 1 + Math.max(left, right);      // this node + the deeper side
}

static void preorder(TreeNode root, List<Integer> out) {
    if (root == null) return;
    out.add(root.val);                     // 1. visit the node
    preorder(root.left, out);              // 2. then the left side
    preorder(root.right, out);             // 3. then the right side
}

Time & space: O(n) time — each node is visited once. O(h) space for the call stack, where h is the tree height.

13. Binary Search Trees

Key points

• Search, insert and delete take O(h) steps, where h is the height.
• If the tree is balanced (bushy), h is about log n, so it is fast.
• If you insert sorted numbers (1, 2, 3, 4…), the tree becomes a long line. Then h = n and it is slow.
• Inorder traversal (left, root, right) of a BST gives the values in sorted order.
• Validate a BST by checking each node is inside a (min, max) range, not just against its parent.

Dry run: search for 6

static TreeNode search(TreeNode root, int target) {
    TreeNode cur = root;
    while (cur != null) {
        if (target == cur.val) return cur;     // found it
        if (target < cur.val) cur = cur.left;  // smaller: go left
        else cur = cur.right;                  // bigger: go right
    }
    return null;                               // not in the tree
}

static TreeNode insert(TreeNode root, int value) {
    if (root == null) return new TreeNode(value);   // empty spot: put it here
    if (value < root.val) root.left = insert(root.left, value);
    else root.right = insert(root.right, value);
    return root;
}

Time & space: O(h) time — one path from root down. O(log n) if balanced, O(n) in the worst case.

14. Balanced Trees & TreeMap

Key points

• You almost never write AVL or red-black trees in interviews. You use TreeMap / TreeSet.
• Like HashMap, but the keys are kept sorted. Each operation is O(log n).
• floorKey(x) = biggest key ≤ x. ceilingKey(x) = smallest key ≥ x.
• firstKey() = smallest key. lastKey() = biggest key.
• Use it when you need "the closest value" or sorted order while adding items.

Dry run: TreeSet with {10, 20, 30}

static void treeMapDemo() {
    TreeMap<Integer, String> map = new TreeMap<>();
    map.put(30, "c");
    map.put(10, "a");
    map.put(20, "b");                     // keys are kept sorted: 10, 20, 30

    Integer below = map.floorKey(25);     // 20
    Integer above = map.ceilingKey(25);   // 30
    Integer none = map.floorKey(5);       // null: always check for null!
    int smallest = map.firstKey();        // 10

    System.out.println(below + " " + above + " " + none + " " + smallest);
}

Time & space: O(log n) for put, get, floor and ceiling. O(n) space.

15. Tries

Key points

• Each node has up to 26 children (one per letter a–z) and a flag isEnd ("a word ends here").
• Insert and search take O(L), where L is the length of the word. The number of words does not matter.
• startsWith(prefix) is very fast — that is the main reason to use a trie.
• Used for autocomplete, spell check and word games.

Dry run: insert "cat" and "car"

class Trie {
    Trie[] children = new Trie[26];   // one slot per letter a-z
    boolean isEnd = false;            // does a word end here?

    void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';                       // 'a' -> 0, 'b' -> 1 ...
            if (node.children[i] == null) {
                node.children[i] = new Trie();     // make the path if missing
            }
            node = node.children[i];               // step down
        }
        node.isEnd = true;                         // mark the end of the word
    }

    boolean search(String word) {
        Trie node = walk(word);
        return node != null && node.isEnd;         // path exists AND a word ends here
    }

    boolean startsWith(String prefix) {
        return walk(prefix) != null;               // path exists
    }

    Trie walk(String s) {                          // follow letters, null if missing
        Trie node = this;
        for (char c : s.toCharArray()) {
            node = node.children[c - 'a'];
            if (node == null) return null;
        }
        return node;
    }
}

Time & space: O(L) per operation — one step per letter. Space grows with the total letters stored.

16. Graphs & Traversal

Key points

• Undirected edge = a two-way road. Directed edge = a one-way road. Weighted edge = a road with a length.
• Store it as List<List<Integer>>: graph.get(u) = neighbours of u.
• Always keep a visited set or array. Without it, cycles make you loop forever.
• BFS (queue) explores in rings, nearest first. It finds the shortest path when all edges have the same cost.
• DFS (recursion or stack) goes as deep as possible, then backs up.

Dry run: BFS from node 0

static List<Integer> bfs(List<List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();          // visit order
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new ArrayDeque<>();

    queue.offer(start);
    visited[start] = true;                              // mark when you add it
    while (!queue.isEmpty()) {
        int node = queue.poll();                        // take the oldest
        order.add(node);
        for (int next : graph.get(node)) {              // look at neighbours
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);                      // visit it later
            }
        }
    }
    return order;
}

static void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;                               // mark this node
    for (int next : graph.get(node)) {
        if (!visited[next]) {
            dfs(graph, next, visited);                  // go deeper
        }
    }
}

Time & space: O(V + E) time — each node (V) and each edge (E) is looked at once. O(V) space for visited and the queue.

17. Union-Find

Key points

• Each item has a parent. The item that is its own parent is the group's leader (root).
• find(x) follows parents up to the leader.
• union(a, b) makes one leader the parent of the other leader.
• Path compression: while finding, point everyone straight to the leader. This makes it almost O(1).
• Use it for: counting connected groups, and finding a cycle in an undirected graph.

Dry run: 4 items, union(0,1), union(1,2)

class UnionFind {
    int[] parent;

    UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;   // everyone leads their own group
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);   // path compression: jump to the leader
        }
        return parent[x];
    }

    boolean union(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA == rootB) return false;  // already in the same group
        parent[rootA] = rootB;             // join the two groups
        return true;
    }
}

Time & space: almost O(1) per find/union with path compression. O(n) space for the parent array.

18. Segment & Fenwick Trees

Key points

• Array never changes → use prefix sums: O(1) per query.
• Array changes often → use a Fenwick tree (Binary Indexed Tree) or a segment tree.
• Both do update and range-query in O(log n).
• Fenwick tree: shorter code, good for sums. Segment tree: more code, but works for min, max and more.
• These are rare in beginner interviews. Learn them after you are comfortable with everything else.

The idea in one table: why not a plain array?

// Minimal Fenwick tree for sums. Indexes are 1-based inside.
class Fenwick {
    int[] tree;
    Fenwick(int n) { tree = new int[n + 1]; }

    void add(int i, int delta) {            // add delta at position i (1-based)
        for (; i < tree.length; i += i & (-i)) {
            tree[i] += delta;
        }
    }

    int prefixSum(int i) {                  // sum of positions 1..i
        int sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += tree[i];
        }
        return sum;
    }

    int rangeSum(int left, int right) {     // sum of positions left..right
        return prefixSum(right) - prefixSum(left - 1);
    }
}

Time & space: O(log n) per update and per query. O(n) space.

19. Sorting

Key points

• Simple sorts (bubble, selection, insertion) are O(n²). Fine for small arrays, slow for big ones.
• Fast sorts (merge sort, quick sort) are O(n log n).
• Arrays.sort(int[]) is O(n log n). Use it in interviews unless they ask you to write a sort.
• A stable sort keeps equal items in their original order. Merge sort is stable.
• Sort objects with a comparator: Arrays.sort(people, (a, b) -> a.age - b.age).

Dry run: insertion sort on [3, 1, 2]

static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int card = arr[i];                    // the item we want to place
        int j = i - 1;
        while (j >= 0 && arr[j] > card) {     // bigger items on the left?
            arr[j + 1] = arr[j];              // move them one step right
            j--;
        }
        arr[j + 1] = card;                    // drop the card in the gap
    }
}

Time & space: insertion sort is O(n²) time, O(1) extra space. Arrays.sort is O(n log n).

20. Binary Search

Key points

• The array must be sorted.
• Keep two indexes: lo (left end) and hi (right end). Loop while lo <= hi.
• Middle: mid = lo + (hi - lo) / 2. This avoids number overflow for huge indexes.
• Too small → lo = mid + 1. Too big → hi = mid - 1.
• Off-by-one mistakes are common. Test with 1 item and 2 items.

Dry run: find 9 in [1, 3, 5, 7, 9, 11, 13]

static int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {                     // still something to check
        int mid = lo + (hi - lo) / 2;      // the middle index
        if (arr[mid] == target) {
            return mid;                    // found it
        } else if (arr[mid] < target) {
            lo = mid + 1;                  // too small: search the right half
        } else {
            hi = mid - 1;                  // too big: search the left half
        }
    }
    return -1;                             // not found
}

Time & space: O(log n) time — the search area halves every step. O(1) space.

21. Backtracking

Key points

• It is recursion that builds an answer bit by bit in a list (often called path).
• Choose: add an item to path. Explore: recurse. Un-choose: remove the item.
• When saving an answer, save a copy: new ArrayList<>(path). Otherwise it changes later.
• It is slow (often O(2ⁿ) or O(n!)), because it tries everything. That is OK — the questions expect it.
• Used for: subsets, permutations, combinations, Sudoku, N-Queens, word search.

Dry run: all subsets of [1, 2]

static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

static void backtrack(int[] nums, int start, List<Integer> path,
                      List<List<Integer>> result) {
    result.add(new ArrayList<>(path));          // save a COPY of the current path
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                       // choose
        backtrack(nums, i + 1, path, result);    // explore
        path.remove(path.size() - 1);            // un-choose (go back)
    }
}

Time & space: O(2ⁿ × n) time — there are 2ⁿ subsets and copying each costs up to n. O(n) space for the recursion (plus the answers).

22. Greedy

Key points

• Greedy is usually sort + one loop. Fast and short.
• It works only when a local best choice never hurts the final answer.
• Test it with small examples. If you find a case where greedy fails, use DP (topic 24) instead.
• Common greedy ideas: pick the earliest finish time, the smallest that fits, the biggest jump.

Dry run: Assign Cookies, children's greed g = [1, 2, 3], cookie sizes s = [1, 1]

static int findContentChildren(int[] greed, int[] cookies) {
    Arrays.sort(greed);                  // least greedy child first
    Arrays.sort(cookies);                // smallest cookie first
    int child = 0, cookie = 0;
    while (child < greed.length && cookie < cookies.length) {
        if (cookies[cookie] >= greed[child]) {
            child++;                     // this child is happy, next child
        }
        cookie++;                        // this cookie is used or too small
    }
    return child;                        // number of happy children
}

Time & space: O(n log n) time because of sorting. O(1) extra space.

23. Divide & Conquer

Key points

• Merge sort: split the array in half, sort each half, then merge the two sorted halves.
• Merging two sorted lists is easy: compare the fronts, take the smaller one.
• Splitting in half gives log n levels. Each level does n work. Total: O(n log n).
• Binary search and quick sort are also divide and conquer.

Dry run: merge sort on [3, 1, 2]

static void mergeSort(int[] arr, int lo, int hi) {   // sorts arr[lo..hi]
    if (lo >= hi) return;                  // 0 or 1 item: already sorted
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, lo, mid);               // sort the left half
    mergeSort(arr, mid + 1, hi);           // sort the right half
    merge(arr, lo, mid, hi);               // combine them
}

static void merge(int[] arr, int lo, int mid, int hi) {
    int[] temp = new int[hi - lo + 1];
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) {          // both halves have items
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];   // take the smaller
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++]; // copy what is left
    while (j <= hi) temp[k++] = arr[j++];
    for (k = 0; k < temp.length; k++) {
        arr[lo + k] = temp[k];             // put the merged items back
    }
}
// Call it like this: mergeSort(arr, 0, arr.length - 1);

Time & space: O(n log n) time — log n levels, n work each. O(n) extra space for the temp arrays.

24. Dynamic Programming

Key points

• DP works when the big problem is made of smaller, repeating problems.
• State: what does dp[i] mean? Write it in words first. Example: "ways to reach step i".
• Recurrence (the rule): how dp[i] uses smaller answers. Example: dp[i] = dp[i-1] + dp[i-2].
• Base case: the smallest answers you know without work.
• Top-down = recursion + a memo (saved answers). Bottom-up = fill a table with a loop.

Dry run: Climbing Stairs, n = 4

static int climbStairs(int n) {
    int[] dp = new int[n + 1];           // dp[i] = ways to reach step i
    dp[0] = 1;                           // base: one way to stand at the start
    dp[1] = 1;                           // base: one way to reach step 1
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];   // came from 1 step below or 2 steps below
    }
    return dp[n];
}

// Same idea, top-down with a memo (saved answers)
static int fib(int n, int[] memo) {      // call with memo = new int[n + 1]
    if (n <= 1) return n;                // base cases
    if (memo[n] != 0) return memo[n];    // already solved? reuse it
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

Time & space: O(n) time — each step is computed once. O(n) space for the table.

25. DP Patterns

Key points

• Grid: you can only come from the top or the left, so add (or take min of) those two cells.
• Pick or skip: for each item, the answer is the better of "take it" and "leave it".
• Draw the table on paper for a tiny input before you code.

Dry run: Unique Paths in a 3 × 3 grid (move only right or down)

static int uniquePaths(int rows, int cols) {
    int[][] dp = new int[rows][cols];        // dp[r][c] = ways to reach (r, c)
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (r == 0 || c == 0) {
                dp[r][c] = 1;                // first row/column: only one way
            } else {
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1];   // from top + from left
            }
        }
    }
    return dp[rows - 1][cols - 1];
}

static int rob(int[] houses) {               // House Robber: no two neighbours
    int skip = 0, take = 0;                  // best so far without / with last house
    for (int money : houses) {
        int newTake = skip + money;          // rob this one: last one must be skipped
        skip = Math.max(skip, take);         // skip this one: keep the best so far
        take = newTake;
    }
    return Math.max(skip, take);
}

Time & space: uniquePaths is O(rows × cols) time and space. rob is O(n) time, O(1) space.

26. Shortest Paths

Key points

• All edges equal → BFS, O(V + E).
• Different weights, none negative → Dijkstra with a PriorityQueue, O(E log V).
• Negative weights → Bellman-Ford (advanced — come back later).
• Keep a dist array. Start with "infinity" everywhere, and 0 for the start.
• When you find a shorter way to a node, update dist and put it in the heap.

Dry run: edges 0→1 (cost 4), 0→2 (cost 1), 2→1 (cost 2). Start at 0.

// graph.get(u) holds edges as {neighbour, cost}
static int[] dijkstra(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);             // "infinity" at first
    dist[start] = 0;

    // heap of {node, distance}, smallest distance first
    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    heap.offer(new int[] { start, 0 });

    while (!heap.isEmpty()) {
        int[] cur = heap.poll();
        int node = cur[0], d = cur[1];
        if (d > dist[node]) continue;                 // old, out-of-date entry: skip
        for (int[] edge : graph.get(node)) {
            int next = edge[0], cost = edge[1];
            if (d + cost < dist[next]) {              // found a shorter way?
                dist[next] = d + cost;
                heap.offer(new int[] { next, dist[next] });
            }
        }
    }
    return dist;
}

Time & space: O(E log V) time — each edge may push into the heap. O(V + E) space.

27. Topo Sort, MST & More

Key points

• Kruskal = sorting + Union-Find (topic 17). If union says "already joined", skip that edge — it would make a loop.
• An MST of n nodes always has exactly n - 1 edges.

Dry run: Kruskal on 3 nodes. Edges: (0-1, cost 1), (1-2, cost 2), (0-2, cost 3)

// edges are {from, to, cost}. Uses the UnionFind class from topic 17.
static int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));   // cheapest first
    UnionFind uf = new UnionFind(n);
    int total = 0;
    for (int[] e : edges) {
        if (uf.union(e[0], e[1])) {      // joins two different groups?
            total += e[2];               // yes: use this edge
        }                                // no: it would make a loop, skip
    }
    return total;
}

Time & space: O(E log E) time — sorting the edges is the slow part. O(V) space for Union-Find.

28. String Algorithms

Key points

• Simple search: try every start position, compare letter by letter. O(n × m) (n = text length, m = pattern length).
• KMP: uses a helper table so it never goes backwards in the text. O(n + m).
• Rolling hash (Rabin-Karp): turns each window of text into a number, compares numbers. O(n + m) on average.
• In Java, text.indexOf(pattern) does the simple search for you.
• Many "string" problems are really hashing (anagrams), two pointers (palindromes) or sliding window.

Dry run: find "ll" in "hello"

static int strStr(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    for (int i = 0; i + m <= n; i++) {        // every possible start position
        int j = 0;
        while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
            j++;                              // letters match, keep going
        }
        if (j == m) return i;                 // all m letters matched
    }
    return -1;                                // not found
}

Time & space: O(n × m) time in the worst case. O(1) space. (KMP gets this down to O(n + m).)

29. Math & Number Theory

Key points

• a % b = remainder. n % 10 = last digit. n / 10 = remove the last digit.
• GCD with Euclid's trick: gcd(a, b) = gcd(b, a % b), stop when b is 0.
• To check if n is prime, test divisors only up to √n.
• Sieve of Eratosthenes: find all primes up to n by crossing out multiples.
• Big answers: problems often say "return answer % 1,000,000,007". Use long to avoid overflow.

Dry run: gcd(12, 8)

static int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;       // remainder
        a = b;               // shift: (a, b) becomes (b, r)
        b = r;
    }
    return a;
}

static boolean isPrime(int n) {
    if (n < 2) return false;               // 0 and 1 are not prime
    for (int d = 2; d * d <= n; d++) {     // only up to the square root
        if (n % d == 0) return false;      // found a divisor
    }
    return true;
}

static int sumOfDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;                     // take the last digit
        n = n / 10;                        // remove the last digit
    }
    return sum;
}

Time & space: gcd is O(log n). isPrime is O(√n). sumOfDigits is O(number of digits). All O(1) space.

30. Two Pointers

Key points

• Opposite ends (L and R move towards each other): pair sums in a sorted array, palindromes, reversing.
• Same direction (slow and fast both move right): remove duplicates, move zeroes.
• Often the array must be sorted first.
• Loop while left < right.
• Each pointer only moves forward, so the total work is O(n).

Dry run: is "racecar" a palindrome?

static boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;   // mismatch
        left++;                                   // move inwards
        right--;
    }
    return true;
}

// Pair with a given sum in a SORTED array (0-based positions)
static int[] pairSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[] { left, right };
        if (sum < target) left++;                 // need bigger: move left up
        else right--;                             // need smaller: move right down
    }
    return new int[] { -1, -1 };
}

Time & space: O(n) time — the pointers together cross the array once. O(1) space.

31. Sliding Window

Key points

• Fixed window: size k is given. Add the right item, remove the left item, update the answer.
• Variable window: grow the right side; when the window breaks a rule, shrink from the left.
• Clues in the question: "subarray", "substring", "contiguous" (next to each other), "longest", "of size k".
• Often uses a HashMap or HashSet to track what is inside the window.
• Both ends only move right, so it is O(n).

Dry run: biggest sum of 3 in a row, [2, 1, 5, 1, 3, 2]

// Fixed window: biggest sum of k items in a row
static int maxSumOfK(int[] arr, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += arr[i];    // first window
    int best = sum;
    for (int right = k; right < arr.length; right++) {
        sum += arr[right];                         // add the new item
        sum -= arr[right - k];                     // remove the old item
        best = Math.max(best, sum);
    }
    return best;
}

// Variable window: longest substring with no repeated letter
static int lengthOfLongestSubstring(String s) {
    Set<Character> inWindow = new HashSet<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        while (inWindow.contains(c)) {             // repeat! shrink from the left
            inWindow.remove(s.charAt(left));
            left++;
        }
        inWindow.add(c);                           // grow on the right
        best = Math.max(best, right - left + 1);   // window size
    }
    return best;
}

Time & space: O(n) time — each item enters and leaves the window once. O(1) for the fixed version, O(k) for the set.

32. Prefix Sum & Difference

Key points

• Build once in O(n): prefix[i + 1] = prefix[i] + arr[i], with prefix[0] = 0.
• Sum from index L to R = prefix[R + 1] - prefix[L]. That is O(1).
• The extra 0 at the start removes special cases for L = 0.
• Prefix sum + HashMap solves "count subarrays with sum k".
• Difference array: to add v to range [L, R], do diff[L] += v and diff[R + 1] -= v, then take running totals at the end.

Dry run: arr = [1, 2, 3, 4]

Sum of index 1 to 2 (2 + 3) = prefix[3] - prefix[1] = 6 - 1 = 5. Correct!

class RangeSum {
    int[] prefix;

    RangeSum(int[] arr) {
        prefix = new int[arr.length + 1];          // one extra slot for the 0
        for (int i = 0; i < arr.length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];    // running total
        }
    }

    int sumRange(int left, int right) {            // sum of arr[left..right]
        return prefix[right + 1] - prefix[left];
    }
}

Time & space: O(n) to build, then O(1) for every range question. O(n) space.

33. Fast & Slow Pointers

Key points

• Find the middle of a list in one pass.
• Detect a cycle (loop) with O(1) extra memory — no HashSet needed.
• Always check fast != null && fast.next != null before moving fast 2 steps.
• Also works on numbers, like Happy Number (the "list" is the next value each time).

Dry run: middle of 1 → 2 → 3 → 4 → 5

static ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;              // 1 step
        fast = fast.next.next;         // 2 steps
    }
    return slow;                       // slow is in the middle
}

static 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; // they met: there is a loop
    }
    return false;                      // fast reached the end: no loop
}

Time & space: O(n) time, O(1) space — just two pointers.

34. Monotonic Stack & Queue

Key points

• Clue: "next greater", "next smaller", "how many days until warmer".
• Store indexes in the stack, not values. Then you can find both the value and the distance.
• When the new item is bigger than the top, the top has found its "next greater". Pop it and record the answer.
• Each item is pushed once and popped once, so it is O(n).
• A monotonic queue (deque) does the same for a sliding window maximum. (Advanced — come back later.)

Dry run: next greater for [2, 1, 3]

static int[] nextGreater(int[] nums) {
    int[] answer = new int[nums.length];
    Arrays.fill(answer, -1);                       // -1 means "none found"
    Deque<Integer> stack = new ArrayDeque<>();     // holds indexes
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int j = stack.pop();                   // nums[i] is j's next greater
            answer[j] = nums[i];
        }
        stack.push(i);                             // wait for my next greater
    }
    return answer;
}

Time & space: O(n) time — each index is pushed and popped at most once. O(n) space.

35. Merge Intervals

Key points

• Step 1: sort by start time. This is almost always the first step.
• Overlap check (after sorting): next.start <= current.end.
• Merge: current.end = Math.max(current.end, next.end).
• No overlap → save the current interval and start a new one.
• Used for meeting rooms, calendars, booking systems.

Dry run: [[1, 3], [2, 6], [8, 10]] (already sorted)

static int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));   // sort by start
    List<int[]> merged = new ArrayList<>();
    for (int[] cur : intervals) {
        if (merged.isEmpty() || cur[0] > merged.get(merged.size() - 1)[1]) {
            merged.add(cur);                              // no overlap: new interval
        } else {
            int[] last = merged.get(merged.size() - 1);   // overlap: stretch the end
            last[1] = Math.max(last[1], cur[1]);
        }
    }
    return merged.toArray(new int[0][]);
}

Time & space: O(n log n) time for sorting, then one pass. O(n) space for the answer.

36. Cyclic Sort

Key points

• Clue: "numbers in the range 1 to n", "find the missing / duplicate number".
• If nums[i] is not at its home, swap it there. Do not move i yet — check the new number too.
• If the number is already home (or its home already has the same number), move on: i++.
• After sorting, any index i where nums[i] != i + 1 shows a problem number.
• O(n) time and O(1) extra space — better than sorting or a HashSet.

Dry run: [3, 1, 2]

static void cyclicSort(int[] nums) {          // numbers are 1..n
    int i = 0;
    while (i < nums.length) {
        int home = nums[i] - 1;               // where this number belongs
        if (nums[i] != nums[home]) {          // not home yet (and no duplicate there)
            int temp = nums[i];               // swap it home
            nums[i] = nums[home];
            nums[home] = temp;
        } else {
            i++;                              // fine: move to the next index
        }
    }
}

// Missing Number: numbers 0..n with one missing (simple math version)
static int missingNumber(int[] nums) {
    int n = nums.length;
    int expected = n * (n + 1) / 2;           // sum of 0..n
    int actual = 0;
    for (int x : nums) actual += x;
    return expected - actual;                 // the difference is the missing one
}

Time & space: O(n) time — every swap puts one number home for good. O(1) space.

37. In-place List Reversal

Key points

• Save next = cur.next before you change the arrow, or you lose the rest of the list.
• Turn the arrow: cur.next = prev.
• Move both forward: prev = cur, cur = next.
• At the end, prev is the new head.
• Draw it on paper. Three boxes and arrows make it clear.

Dry run: reverse 1 → 2 → 3

static ListNode reverseList(ListNode head) {
    ListNode prev = null;              // the reversed part (empty at first)
    ListNode cur = head;               // the node we are working on
    while (cur != null) {
        ListNode next = cur.next;      // 1. remember the rest of the list
        cur.next = prev;               // 2. turn the arrow backwards
        prev = cur;                    // 3. move prev forward
        cur = next;                    // 4. move cur forward
    }
    return prev;                       // prev is the new head
}

Time & space: O(n) time — each node once. O(1) space — only three pointers.

38. Tree BFS & DFS

Key points

• BFS: put the root in a queue. Each round, take out all nodes of the current level and add their children.
• Use BFS for: level order, "minimum depth", "rightmost node of each level".
• DFS: preorder (node, left, right), inorder (left, node, right), postorder (left, right, node).
• Use DFS for: height, path sums, checking a property of every subtree.
• Trick for BFS levels: save size = queue.size() at the start of each level, then loop exactly that many times.

Dry run: level order of the tree 1 (children 2, 3), 2 (children 4, 5)

static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();                 // nodes in this level
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);    // next level
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

// DFS: is there a root-to-leaf path that adds up to target?
static boolean hasPathSum(TreeNode root, int target) {
    if (root == null) return false;
    if (root.left == null && root.right == null) {   // leaf
        return root.val == target;
    }
    int rest = target - root.val;                     // what is still needed
    return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);
}

Time & space: O(n) time for both — each node once. BFS uses O(width) space, DFS uses O(height) space.

39. Top K & K-way Merge

Key points

• k largest → min-heap of size k (the smallest of the best k sits on top, easy to kick out).
• k most frequent → count with a HashMap first, then use the heap on the counts.
• K-way merge → heap holds one item from each list. Poll the smallest, then push the next item from that same list.
• Time is O(n log k), which beats sorting everything (O(n log n)) when k is small.

Dry run: top 2 frequent in [1, 1, 1, 2, 2, 3]

static int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);   // 1. count

    // 2. min-heap ordered by count: the least frequent is on top
    PriorityQueue<Integer> heap =
        new PriorityQueue<>(Comparator.comparingInt(n -> count.get(n)));
    for (int num : count.keySet()) {
        heap.offer(num);
        if (heap.size() > k) heap.poll();        // drop the least frequent
    }

    int[] result = new int[k];                   // 3. the heap holds the answer
    for (int i = 0; i < k; i++) result[i] = heap.poll();
    return result;
}

Time & space: O(n log k) time — counting is O(n), each heap step is O(log k). O(n) space for the counts.

40. Two Heaps

Key points

• low = max-heap (smaller half). high = min-heap (bigger half).
• Keep sizes balanced: low has the same number of items as high, or one more.
• Odd count → median = top of low. Even count → average of both tops.
• Clue: "median of a stream" (numbers keep arriving), "sliding window median".

Dry run: add 5, then 2, then 8

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

    void addNum(int num) {
        low.offer(num);                       // 1. add to the small half
        high.offer(low.poll());               // 2. move the biggest small one up
        if (high.size() > low.size()) {       // 3. keep low the same size or bigger
            low.offer(high.poll());
        }
    }

    double findMedian() {
        if (low.size() > high.size()) return low.peek();     // odd count
        return (low.peek() + high.peek()) / 2.0;              // even count
    }
}

Time & space: O(log n) per add, O(1) for the median. O(n) space.

41. Subsets & Permutations

Key points

• Permutations: every position can use any item that is not used yet.
• Save the answer when path.size() == nums.length.
• With duplicates in the input: sort first, then skip equal neighbours.

Dry run: permutations of [1, 2] (first steps)

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

static void build(int[] nums, boolean[] used, List<Integer> path,
                  List<List<Integer>> result) {
    if (path.size() == nums.length) {            // all items placed
        result.add(new ArrayList<>(path));       // save a copy
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;                   // already in the path
        used[i] = true;                          // choose
        path.add(nums[i]);
        build(nums, used, path, result);         // explore
        path.remove(path.size() - 1);            // un-choose
        used[i] = false;
    }
}

Time & space: O(n! × n) time — n! orderings, each copied. O(n) space for the recursion.

42. Modified Binary Search

Key points

• First position: when you find x, save it, then keep searching left (hi = mid - 1).
• Last position: same, but keep searching right.
• Rotated array (like [4, 5, 6, 1, 2, 3]): one half is always sorted. Check if x is in that half.
• Search on the answer: if "does value v work?" is no, no, no, yes, yes, yes, binary search for the first yes.
• The question's clue is often "sorted" plus "O(log n)".

Dry run: first position of 2 in [1, 2, 2, 2, 3]

static int firstPosition(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    int answer = -1;                      // -1 if never found
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            answer = mid;                 // found one, save it
            hi = mid - 1;                 // but maybe there is an earlier one
        } else if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return answer;
}

Time & space: O(log n) time, O(1) space — still halving every step.

43. Topological Sort

Key points

• Kahn's algorithm: start with all nodes that have in-degree 0 (nothing before them). Put them in a queue.
• Take one out, add it to the order, and lower the in-degree of its neighbours by 1.
• When a neighbour reaches in-degree 0, it is ready — add it to the queue.
• If the final order has fewer than n nodes, there is a cycle (impossible to finish).
• Clue: "prerequisites", "dependencies", "build order", "can all courses be finished?"

Dry run: 4 courses. 0 before 1, 0 before 2, 1 before 3, 2 before 3

// prereqs[i] = {course, before}: "before" must be taken before "course"
static List<Integer> courseOrder(int n, int[][] prereqs) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    int[] inDegree = new int[n];
    for (int[] p : prereqs) {
        graph.get(p[1]).add(p[0]);        // arrow: before -> course
        inDegree[p[0]]++;                 // course has one more thing before it
    }

    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);   // ready to start
    }

    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int course = queue.poll();
        order.add(course);
        for (int next : graph.get(course)) {
            inDegree[next]--;             // one less thing to wait for
            if (inDegree[next] == 0) queue.offer(next);
        }
    }
    return order.size() == n ? order : new ArrayList<>();   // empty = cycle
}

Time & space: O(V + E) time — each course and each arrow once. O(V + E) space for the graph.

44. Matrix & Islands

Key points

• A cell is grid[r][c]: r = row, c = column.
• Always check the borders first: r >= 0 && r < rows && c >= 0 && c < cols.
• Mark visited cells, often by changing '1' to '0' (sinking the land).
• Number of islands = how many times you start a new DFS on unvisited land.
• Use BFS instead when the question asks for the shortest number of steps.

Dry run: count islands

static int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == '1') {       // new land we have not visited
                count++;                   // found a new island
                sink(grid, r, c);          // mark the whole island as visited
            }
        }
    }
    return count;
}

static void sink(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;  // outside
    if (grid[r][c] != '1') return;         // water or already visited
    grid[r][c] = '0';                      // mark as visited
    sink(grid, r + 1, c);                  // down
    sink(grid, r - 1, c);                  // up
    sink(grid, r, c + 1);                  // right
    sink(grid, r, c - 1);                  // left
}

Time & space: O(rows × cols) time — each cell is visited once. O(rows × cols) space for the recursion in the worst case.

45. Design Problems

Key points

• First, list each method and the speed it needs (often O(1)).
• Then pick structures: HashMap for fast lookup, a linked list or deque for order, a heap for min/max.
• Min Stack: a normal stack plus a second stack that tracks the minimum so far.
• LRU Cache: HashMap + doubly linked list. In Java, LinkedHashMap already combines them.
• Interviewers may ask you to build the linked list yourself — see the full notes for that version.

Dry run: LRU cache with capacity 2

// LRU Cache using LinkedHashMap (keeps items in "last used" order)
class LRUCache extends LinkedHashMap<Integer, Integer> {
    int capacity;

    LRUCache(int capacity) {
        super(16, 0.75f, true);          // true = order by last access, not insert
        this.capacity = capacity;
    }

    int get(int key) {
        return getOrDefault(key, -1);    // reading also marks it "recently used"
    }

    void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;        // too big? Java removes the oldest
    }
}

// Min Stack: getMin() in O(1)
class MinStack {
    Deque<Integer> stack = new ArrayDeque<>();
    Deque<Integer> mins = new ArrayDeque<>();     // min so far, at each level

    void push(int x) {
        stack.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
    }
    void pop()    { stack.pop(); mins.pop(); }
    int top()     { return stack.peek(); }
    int getMin()  { return mins.peek(); }
}

Time & space: every method is O(1). O(n) space for the stored items.

Which Pattern When?

Read the question slowly and look for these clues. The clue usually tells you which tool to try first.

Big-O Cheat Sheet

Average times for the most common operations. "n" is the number of items.

What input size allows what speed?

Learning Path

Go in this order. Do the easy problems at each step before moving on. It is fine to look at a solution when stuck for 30 minutes — then try again the next day without looking.

1. Big-O and Java basics (topics 2, 4) — loops, arrays, ArrayList, HashMap.
   Problems: Fizz Buzz (#412), Running Sum of 1d Array (#1480), Richest Customer Wealth (#1672).
2. Arrays & strings (6) — loops, indexes, StringBuilder.
   Problems: Reverse String (#344), Best Time to Buy and Sell Stock (#121), Merge Sorted Array (#88).
3. Hashing (7) — HashMap and HashSet.
   Problems: Two Sum (#1), Contains Duplicate (#217), Valid Anagram (#242).
4. Two pointers (30) — from both ends.
   Problems: Valid Palindrome (#125), Move Zeroes (#283), Two Sum II (#167).
5. Sliding window & prefix sum (31, 32).
   Problems: Maximum Average Subarray I (#643), Longest Substring Without Repeating Characters (#3), Range Sum Query - Immutable (#303).
6. Stacks & queues (9, 10).
   Problems: Valid Parentheses (#20), Min Stack (#155), Implement Queue using Stacks (#232).
7. Linked lists (8, 33, 37).
   Problems: Reverse Linked List (#206), Middle of the Linked List (#876), Linked List Cycle (#141).
8. Recursion (3) — base case and call stack.
   Problems: Fibonacci Number (#509), Power of Two (#231), Merge Two Sorted Lists (#21).
9. Binary search (20, 42).
   Problems: Binary Search (#704), Search Insert Position (#35), First Bad Version (#278).
10. Binary trees (12, 13, 38) — DFS recursion and BFS levels.
    Problems: Maximum Depth of Binary Tree (#104), Invert Binary Tree (#226), Binary Tree Level Order Traversal (#102).
11. Heaps (11, 39).
    Problems: Last Stone Weight (#1046), Kth Largest Element in a Stream (#703), Top K Frequent Elements (#347).
12. Backtracking (21, 41).
    Problems: Subsets (#78), Permutations (#46), Combination Sum (#39).
13. Graphs & grids (16, 44, 43).
    Problems: Flood Fill (#733), Number of Islands (#200), Course Schedule (#207).
14. Dynamic programming (24, 25).
    Problems: Climbing Stairs (#70), House Robber (#198), Coin Change (#322).
15. Then — intervals, greedy, tries, Union-Find, Dijkstra. Advanced topics (segment trees, KMP, MST) last. Now read the full notes and practise with the LeetCode cheat sheet and the interview Q&A.