Mixed Practice: Putting It All Together

By the final session every tool is already on the table — binary search, DFS and backtracking, heaps, dynamic programming, linked lists, hashmaps, BSTs. Real interviews rarely hand you a problem with its category stamped on the front. This session is a deliberate grab bag: every question here fuses two or more of the patterns from earlier sessions, and the skill actually being drilled is triage — reading a prompt and naming which tool it is really testing before you write a single line. The problems below are grouped not by the story they tell but by the technique they demand, because that regrouping is the exercise.

Deep Copy Across Three Structures

LC 138 Copy List with Random Pointer is the canonical warm-up because it forces the deep-vs-shallow distinction into the open: a shallow copy dereferences the same object, a deep copy allocates a brand-new one on the heap and rebuilds every pointer. The wrinkle is the random pointer, which can point anywhere — possibly to a node you haven't copied yet.

Three solutions, escalating in cleverness:

• Two-pass hashmap — first pass allocates every copy and records original → copy in a map; second pass wires next and random by looking each original up. O(n) time, O(n) space, trivially correct.
• One-pass hashmap — copy pointers as you go, calling containsKey to create a target node on demand when the random destination doesn't exist yet. Same complexity, one loop.
• Interweaving, O(1) extra space — the trick worth remembering. Splice each copy in right after its original so the list reads A → A' → B → B' → …. Now a node's copy is always node.next, which means copy.random = node.random.next with no map at all. A final unzip pass restores both lists in place.

public Node copyRandomList(Node head) {
    if (head == null) return null;

    // 1. weave a copy in after each original: A -> A' -> B -> B' -> ...
    Node cur = head;
    while (cur != null) {
        Node copy = new Node(cur.val);
        copy.next = cur.next;
        cur.next  = copy;
        cur = copy.next;
    }
    // 2. wire random pointers on the copies (copy sits at node.next)
    cur = head;
    while (cur != null) {
        if (cur.random != null) cur.next.random = cur.random.next;
        cur = cur.next.next;
    }
    // 3. unzip the two interleaved lists back apart
    cur = head;
    Node copyHead = head.next;
    while (cur != null) {
        Node copy = cur.next;
        cur.next  = copy.next;
        copy.next = (copy.next != null) ? copy.next.next : null;
        cur = cur.next;
    }
    return copyHead;
}

The same deep-copy skeleton generalizes: deep copy a tree is a list with two "next" pointers, and deep copy a graph (LC 133 Clone Graph) adds two hazards — cycles and disconnected components. The fix for both is a hashmap keyed by original node reference: never revisit a node you've already copied, and for every neighbor pointer, check the map before allocating. BFS with a queue or DFS with recursion both work; the hashmap is what turns an infinite cyclic walk into a finite one.

Trees Beyond Traversal: BST Ops & Structural Surgery

A BST is really binary search wearing a tree costume — each node comparison prunes one subtree, so "find something" problems need a single top-down path, not full recursion.

LC 270 Closest BST Value makes the point sharply: the recursive helper works, but since there is exactly one root-to-leaf path to follow, an iterative while (root != null) descent that tracks the closest value seen is cleaner and O(h). Go left when target < root.val, right otherwise.

LC 272 Closest K Values raises the bar. The brute force treats the inorder traversal as an array and runs a top-k heap — O(k + (n−k) log k). The elegant answer builds two stacks via a modified inorder walk: a predecessor stack of values ≤ target and a successor stack of values > target, each lazily unwound. Then it's a k-way merge — pop from whichever stack's top is closer, k times. That predecessor/successor machinery is exactly what largest-value-smaller-than-target and smallest-value-larger-than-target need (LC 285 Inorder Successor in BST is the same descent); the classic trap there is the single-node tree with no valid answer — seed closest with a sentinel like Integer.MIN_VALUE rather than the root, or you'll return the root by accident.

Insert and Delete

LC 701 Insert into a BST is the easy half: descend until you fall off the tree, then hang the new node on that empty slot (iterative loop or a recursion that reassigns root.left/right to the returned subtree). LC 450 Delete Node in a BST is the interview-grade half, and its structure — recurse down, reassigning subtrees on the way back up — is worth memorizing. Once you find the target there are four cases, collapsing into three lines: no child or one child, promote the surviving side; two children, copy the successor (min of the right subtree) into this node, then recursively delete that successor.

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;

    if (key < root.val) {
        root.left = deleteNode(root.left, key);        // recurse, reattach subtree
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {                                          // found it
        if (root.left == null)  return root.right;      // 0 / 1 child: promote the other
        if (root.right == null) return root.left;
        TreeNode min = findMin(root.right);         // 2 children: pull successor up
        root.val = min.val;
        root.right = deleteNode(root.right, min.val);  // then delete the successor
    }
    return root;
}

private TreeNode findMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

Reusing Linked-List Reversal on a Tree

LC 156 Binary Tree Upside Down is the cross-topic gem of the set: it looks like a tree problem but is really reverse-a-linked-list applied to the left spine. Given a tree whose right nodes are always leaf siblings, you walk down the left spine and, at each step, the old left child adopts the old right sibling as its left and the old root as its right — precisely the pointer-rewiring dance from list reversal, with the same recursive and iterative (pre / cur / next / tmp) forms. Recognizing that a tree problem is secretly a list problem is the entire trick.

Interval DP: Cutting and Merging on a Line

Two problems that share one recurrence shape — the answer for a range is built from the answers of its sub-ranges split at every interior point. This is the matrix-chain-multiplication family, and it's O(n³).

Stone Cutting: given cut positions on a stick, the cost of a cut equals the length of the piece being cut, and you want the minimum total. Define dp[i][j] = cheapest cost to fully cut the segment between cut points i and j; the transition tries every interior cut k first: dp[i][j] = cost(i,j) + min over k of ( dp[i][k] + dp[k][j] ), base case "nothing left to cut" = 0. The reason DP beats naive recursion is the shared work — cutting 1-then-2 and cutting 2-then-1 both leave the same sub-segments, so memoization erases the overlap.

Merge Stones (the interval-DP cousin of LC 1000 Minimum Cost to Merge Stones) is the mirror image: repeatedly merge two adjacent piles for a score equal to the combined size, and find the min or max total. Same dp[i][j] over interior split k, but the "cost of this merge" is a range sum, so a prefix-sum array makes it O(1): sum[j] − sum[i−1]. When the piles form a ring, the standard move is to double the array (append a second copy) and run linear interval DP over the doubled length — an O((2n)³) but conceptually unchanged solution. The takeaway: whenever "combine adjacent things, pay for the size" appears, reach for interval DP plus prefix sums.

Backtracking's Greatest Hits

A cluster of problems that are all one DFS skeleton with different pruning. The recurring design question is "at each layer, do I choose whether to take element i, or do I choose which element to place next?" — the two framings produce different trees for the same answer set.

• LC 78 Subsets / LC 90 Subsets II — every node is an answer. The clean "pick which next" version adds each candidate and recurses from i+1; to kill duplicates in Subsets II, sort first and if (i > start && nums[i] == nums[i-1]) continue;. The alternative "take-or-skip" framing puts answers at the leaves and dedups by advancing past a run of equal values on the skip branch; a BFS/queue version also works, and duplicates land in contiguous blocks because the queue preserves order.
• LC 46 / LC 47 Permutations — the swap-in-place template: swap(index, i), recurse at index+1, swap back. With duplicates you either sort and guard on used[i-1], or track a per-layer seen-set — a while-with-i++ skip overruns the array, so use continue.
• LC 20 / LC 22 Parentheses — LC 20 (validity) is a stack: push the expected closer, and any mismatch or leftover fails. LC 22 (generate n pairs) is backtracking with two counters: add ( while open < n, add ) while close < open. The generalization to n pairs of {} / [], or to validating XML/HTML tags, is the same open/close bookkeeping over a richer alphabet.
• LC 322 / LC 518 Coin Change — the poster child for the DFS→DP ladder, shown below.
• LC 416 Partition Equal Subset Sum (the "split the loot evenly" problem) and LC 51 / LC 52 N-Queens round out the set: subset-sum is a boolean knapsack; N-Queens is DFS with three conflict sets (column, two diagonals) — which motivates a quick tour of how to check duplicates fast.

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);   // sentinel: not MAX_VALUE, or dp[i-coin]+1 overflows
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

The progression is worth internalizing: naive DFS tries every coin at every amount (exponential); memoizing on amount prunes repeats (top-down); flipping to dp[i] = min(dp[i−coin] + 1) is bottom-up. Same recurrence, three costs — and the interviewer wants to see you climb the ladder. LC 518 Coin Change II (count combinations) reframes the branching: one coin type per layer with "how many of it" as the branches, versus one coin per branch — the order you iterate the loops is what separates counting combinations from permutations.

Fast Duplicate Checks — the Backtracker's Toolbox

Half of backtracking performance is how you answer "have I used this already?" The ladder, cheapest to richest: a boolean[k] flag array for small fixed alphabets; a bit vector (a single int, or a few ints, with k/32 indexing) when you want set membership in O(1) and negligible space; a HashSet for arbitrary values; a HashMap when you need counts or object keys (and the natural fit inside Tries). LC 318 Maximum Product of Word Lengths is the showcase — encode each word's letters as a 26-bit mask, and two words share no letter iff mask1 & mask2 == 0, turning an O(k) character comparison into one machine instruction; sorting by length descending and pruning once no better product is reachable finishes it.

Heap + BFS on Implicit Graphs

A family that feels like graph search but has no explicit graph — the "nodes" are tuples you generate on demand, and a min-heap keeps you honest about order. The recipe is always the same five steps: define a cost function, seed the start state, expand by pushing neighbors, stop after the k-th poll, and dedup with a seen-set.

• k-th smallest of f(x,y,z) = aˣ·bʸ·cᶻ (the ugly-number family, cf. LC 264 / LC 313) — start at (0,0,0), and each poll pushes (x+1,y,z), (x,y+1,z), (x,y,z+1) into a min-heap ordered by f. The space is infinite, but you halt at the k-th element. Values can collide, so dedup on the exponent tuple with a hashset (encode the tuple or override equals). Time O(k · 4 log k), space O(k).
• k closest points in KD space / k smallest sums from m sorted arrays (LC 373 K Pairs with Smallest Sums) — identical shape with cost a[i]² + b[j]² (or a coordinate distance) and expansions (i+1,j), (i,j+1). Same dedup concern: two different index pairs can sit on the same circle. Time O(k log k), space O(k).
• LC 317 Shortest Distance from All Buildings / LC 296 Best Meeting Point — instead of BFS from the meeting point to every building, BFS from each building outward and accumulate distances into a grid — O(k·n) for k buildings beats O(n²). Choosing the right BFS source is the whole insight; a PQ-based Dijkstra (O(n log n)) is the weighted-edge upgrade when steps have costs.

Monotonic Stack & Two Pointers on Arrays

Two histogram classics that reward the same instinct — stop recomputing what a single sweep already knows.

LC 84 Largest Rectangle in Histogram: the brute force expands left and right from every bar to find how far it stays the tallest — O(n²). The insight is that boundaries can be discovered simultaneously: when bar A is shorter than bar B to its left, A caps B's right boundary. Precomputing each bar's nearest-smaller-to-left and nearest-smaller-to-right gives (right − left) × height in O(n); the tidiest implementation is a monotonic increasing stack that pops a bar exactly when its right boundary is found.

LC 42 Trapping Rain Water is the same "left max vs right max" idea taken to its limit. Water above a bar is min(leftMax, rightMax) − height. Brute force recomputes both maxes per index (O(n²)); precomputing two arrays makes it O(n) time and O(n) space; and the two-pointer refinement drops space to O(1) by noticing that whichever running max is smaller is the true bottleneck for that side, so you can safely settle that pointer and move inward.

public int trap(int[] height) {
    if (height == null || height.length <= 2) return 0;
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;

    while (left < right) {                       // meet in the middle; the peak holds no water
        leftMax  = Math.max(leftMax,  height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (leftMax < rightMax) {                  // left side is the bottleneck
            water += leftMax - height[left];
            left++;
        } else {
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

Design Problems: When Two Data Structures Marry

Cache problems are the purest "two structures, one contract" exercise — no single structure gives you every operation in O(1), so you compose two.

LC 146 LRU Cache: you need O(1) get, O(1) update-recency, and O(1) eviction of the oldest entry. A HashMap alone can't order by recency; a linked list alone can't look up by key. Marry them — the map stores node references into a doubly linked list, so you can splice any node out of the middle in O(1) and re-append it at the tail (most-recently-used), while eviction pops from the head. This is essentially a hand-rolled LinkedHashMap.

class LRUCache {
    class Node { int key, val; Node prev, next; }

    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(), tail = new Node();
    private final int capacity;
    private int size = 0;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail; tail.prev = head;      // sentinels bracket the list
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToTail(node);                         // touched -> most-recently-used
        return node.val;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) { node.val = value; moveToTail(node); return; }
        if (size == capacity) {                   // evict LRU: node right after head
            Node lru = head.next;
            remove(lru); map.remove(lru.key); size--;
        }
        Node fresh = new Node();
        fresh.key = key; fresh.val = value;
        addToTail(fresh); map.put(key, fresh); size++;
    }

    private void moveToTail(Node n) { remove(n); addToTail(n); }
    private void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addToTail(Node n) {
        n.prev = tail.prev; tail.prev.next = n; tail.prev = n; n.next = tail;
    }
}

LC 460 LFU Cache ups the difficulty to eviction by frequency: keep a value map, a frequency map, and a bucket of keys per frequency (a LinkedHashSet preserves insertion order to break ties), plus a running min frequency for O(1) eviction. The subtlety the notes flag: unlike LRU, you can't just drop an entry on access — you must migrate it from bucket f to bucket f+1, because the frequency itself is state.

First Unique Character — String vs Stream

Finding the first non-repeating character (LC 387) in a fixed string is a two-pass frequency count — a HashMap<Character,Integer>, or a freq[128] array, or even a two-bit-per-char bit vector to encode "never / once / many." The stream version is where it turns into a design problem that rhymes with LRU: maintain a doubly linked list of currently-unique candidates plus a hashmap; when a new character arrives, either append it or, if it's now a repeat, splice it out and mark it "seen many" so it never re-enters. The head of the list is your answer in O(1) at any moment.

String & Sequence DP, Array Tricks, and Math

The final cluster mixes 2D string DP, a DP-plus-binary-search hybrid, and three array problems that each hide a mathematical shortcut.

Longest Common Substring / Subarray / Subsequence (LCS, LC 1143) is a 2D DP where dp[i][j] spans the first i and first j characters. The one-character difference between variants is everything: for a contiguous substring, dp[i][j] = dp[i-1][j-1] + 1 on a match and reset to 0 on a mismatch; for a subsequence, a mismatch takes max(dp[i-1][j], dp[i][j-1]). Both compress from 2D to 1D since each cell depends only on the previous row.

LC 300 Longest Increasing Subsequence is the DP-meets-binary-search hybrid. The O(n²) DP sets dp[i] = max(dp[k]) + 1 over earlier smaller elements; the O(n log n) upgrade maintains a tails array (smallest possible tail for each length) and binary-searches each element's insertion point — an array the algorithm builds and keeps sorted itself. LC 354 Russian Doll Envelopes is 2D LIS: sort by width ascending, height descending on ties, then run LIS on heights — the sort is the whole trick.

Three array problems close the session, each a "there's a math shortcut" moment:

• LC 41 First Missing Positive — O(n) time, O(1) space by using the array itself as a hashmap: place value v at index v−1, then scan for the first index whose value is wrong. The trick is recognizing the answer must lie in [1, n+1], so out-of-range values are ignorable.
• LC 149 Max Points on a Line — fix each point, bucket the rest by slope in a hashmap, and the biggest bucket wins; O(n²). The mathematical care is the slope: store it as a gcd-reduced (dy, dx) pair rather than a floating-point ratio to dodge precision loss, and handle vertical lines and duplicate points as their own counters.
• LC 169 Majority Element — sorting gives you the n/2 index for free, a hashmap counts with early exit, but the O(1)-space Boyer-Moore voting algorithm is the one to know, shown next.

public int majorityElement(int[] nums) {
    int candidate = nums[0], count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (count == 0) {                // no leader standing -> nums[i] takes the throne
            candidate = nums[i];
            count = 1;
        } else if (nums[i] == candidate) {
            count++;                     // ally
        } else {
            count--;                     // rival cancels one vote
        }
    }
    return candidate;                    // valid ONLY because majority strictly > n/2
}

The voting intuition: pair off each majority element against a different element and both cancel; because the majority strictly exceeds n/2, at least one of its votes always survives. Push to LC 229 Majority Element II (elements appearing more than n/3, or the general 1/k) and you keep k−1 counters instead of one — but the guarantee weakens, so you must add a second pass to re-verify each survivor actually clears the threshold. Below n/2, voting is invalid and a hashmap count is the honest tool.

Problem Checklist