Binary Search on Answer, Union-Find, Trie, DP & Backtracking

Binary Search on the Answer

Ordinary binary search halves a range of array indices to find a value that's already sitting in a sorted array. Binary search on the answer is a different move entirely: the thing you halve isn't an index into anything, it's a range of candidate answers — a value range like "capacity could be anywhere from 1 to 1,000,000." Nothing in the input needs to be sorted at all.

The move only works if the problem has a monotonic yes/no predicate: as the candidate answer increases (or decreases), the predicate flips from false to true exactly once and never flips back. Write a function feasible(x) that answers "does candidate answer x work?", confirm it's monotonic, then binary-search lo/hi over the value range instead of scanning every candidate one at a time — turning an O(range) linear scan into O(log range) predicate checks.

Worked Example: Minimum Ship Capacity Within D Days

A classic version of this pattern: six packages must ship, in order, over at most 3 days. Each day you load packages onto a ship, in order, up to its weight capacity; once a package would overflow the current day's capacity, the next day starts. What's the minimum capacity that still gets everything shipped within the day limit?

def can_ship(weights, days, capacity):
    needed_days = 1
    current_load = 0
    for w in weights:
        # this weight doesn't fit in today's remaining capacity -- start a new day
        if current_load + w > capacity:
            needed_days += 1
            current_load = 0
        current_load += w
    return needed_days <= days

weights = [3, 7, 4, 2, 8, 5]
days = 3
print(can_ship(weights, days, 12))
print(can_ship(weights, days, 13))

feasible(capacity) = can_ship(weights, days, capacity) is monotonic: any capacity large enough to ship everything in 3 days is also large enough at every larger capacity, and any capacity too small stays too small at every smaller capacity. That's what makes it safe to binary-search. The search range starts at lo = max(weights) = 8 (a ship smaller than the heaviest package can never work) and hi = sum(weights) = 29 (shipping everything in a single day always works).

lo == hi == 13, so the loop stops. A direct check confirms it: can_ship(weights, days, 12) prints False and can_ship(weights, days, 13) prints True — 13 is exactly the smallest capacity that works, and sweeping every capacity from 8 to 29 by hand confirms the predicate never flips back to False once it turns True.

def min_capacity(weights, days):
    # a ship smaller than the heaviest single package can never work
    lo = max(weights)
    # shipping everything in one day always works, so this is a safe upper bound
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_ship(weights, days, mid):
            # mid works -- it's a valid candidate, but a smaller one might also work
            hi = mid
        else:
            # mid isn't enough capacity -- the answer must be strictly larger
            lo = mid + 1
    return lo

print(min_capacity([3, 7, 4, 2, 8, 5], 3))

Complexity: O(n log(sum(weights) - max(weights))) time — each of the O(log range) binary-search steps does an O(n) feasibility scan; O(1) extra space.

Examples in This Set

#32 (longest increasing streak via bisect_left), #34 (consistent-hashing ring lookup), and #47 (median of two sorted arrays via partition search) all use this pattern. #4 looks like a threshold binary search at first glance — "find the minimum threshold that hits a precision target" — but it's a near miss: precision as a function of threshold is not monotonic, so that problem's own writeup rules out binary search and uses a sort-then-sweep instead.

Union-Find (Disjoint Set)

Union-Find tracks a partition of items into disjoint groups under two operations: "are these two items in the same group?" (find) and "merge these two items' groups" (union). Each item starts as its own group of one, pointing to itself as its own "parent." find(x) walks parent pointers up to the group's root; union(a, b) finds both roots and, if they differ, attaches one root under the other.

Two optimizations turn this from "works" into "near O(1) per operation": path compression (every node visited on the way up during a find gets re-pointed straight at the root, so the next lookup is instant) and union by rank/size (always attach the shorter/smaller tree under the taller/larger one, so trees never get needlessly deep). Either one alone helps; both together give the amortized inverse-Ackermann bound.

Worked Example: Connected Components Over 8 Nodes

Eight nodes, numbered 0-7, and seven edges processed in order: (0,1), (1,2), (3,4), (5,6), (6,7), (2,3), (0,4). How many connected components remain at the end?

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        path = []
        while self.parent[x] != x:
            path.append(x)
            x = self.parent[x]
        # path compression: point every visited node straight at the root
        for node in path:
            self.parent[node] = x
        return x

    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False
        # union by rank: attach the shorter tree under the taller one
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
        self.components -= 1
        return True

Initial parent = [0, 1, 2, 3, 4, 5, 6, 7], initial components = 8.

The last call is the interesting one: union(0,4) returns False (0 and 4 are already in the same group after the union(2,3) step made 0 the root of the whole {0,1,2,3,4} tree), yet the parent array still changes — parent[4] flips from 3 straight to 0. That's path compression firing inside find(4) even though the union itself is rejected: find walked 4 → 3 → 0 and flattened it to 4 → 0 on the way out. Final state: find(0)==find(1)==find(2)==find(3)==find(4)==0 and find(5)==find(6)==find(7)==5 — exactly 2 components, {0,1,2,3,4} and {5,6,7}.

Complexity: amortized O(α(n)) per find/union call with both optimizations — effectively O(1); O(n) space for the parent and rank arrays.

Examples in This Set

#9 (clustering near-duplicate queries into groups) and #45 (validating an escalation hierarchy is a valid tree — no cycles, one root) both use Union-Find directly.

Trie (Prefix Tree)

A trie is a tree of nested dictionaries, one level of nesting per character, shared across every word that starts with the same prefix. Each node's children maps a single character to the next node; a boolean flag on a node (commonly called is_word) marks "a real word ends exactly here," which matters because one word can be a strict prefix of another ("car" ends inside the path that also leads to "card").

Insertion walks the word character by character, creating a new child node only where one doesn't already exist, then marks the final node as a word. A prefix search (startsWith) does the identical walk but doesn't check the is_word flag; an exact-word search does the same walk and then requires it. Both operations cost O(L) where L is the length of the word/prefix — completely independent of how many other words are stored.

Worked Example: Building and Querying a Small Trie

Insert six words in order: cat, car, card, care, dog, do.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_word

    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

Complexity: O(L) time per insert/search/starts_with, where L is the word/prefix length; O(total characters across all inserted words) space in the worst case, less in practice since shared prefixes reuse nodes.

Examples in This Set

#17 (KB autocomplete) is the only problem in this set that uses a literal trie — it's a narrow pattern, most "prefix matching" needs elsewhere in this set get solved with simpler string methods instead.

Dynamic Programming

DP applies when a problem has overlapping subproblems — the naive recursive solution would solve the exact same smaller instance over and over — and optimal substructure, meaning the optimal answer to the whole problem can be built directly from optimal answers to smaller subproblems. The entire discipline is: define what dp[i] (or dp[i][j]) precisely means in words first, write the recurrence that computes it from smaller states, nail the base case(s), then fill the table in an order where every dependency is already computed by the time you need it.

Bottom-up (fill a table iteratively) and top-down (recursion plus a memo dict) compute the exact same values — bottom-up avoids recursion-depth limits and repeated function-call overhead, top-down is often easier to write directly from the recursive definition. Both are "DP"; neither is more correct than the other.

Worked Example: Coin Change (Fewest Coins to Make a Target)

Coins [1, 3, 4], target amount 6. dp[a] means "the fewest coins needed to make exactly amount a," with dp[0] = 0 as the base case (zero coins needed to make nothing). The recurrence: dp[a] = 1 + min(dp[a - c] for every coin c <= a).

def coin_change(coins, amount):
    INF = float("inf")
    # dp[0] = 0 is the base case; every other amount starts "unreachable"
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

print(coin_change([1, 3, 4], 6))

dp[6] = 2 — two coins reach 6 (e.g. 3 + 3), confirmed by running coin_change([1, 3, 4], 6), which prints 2. Note that the "obviously biggest first" greedy instinct doesn't actually drive the optimum here: dp[6] is won by coin 3, not the largest coin 4 — greedy coin selection is a different (and not always correct) algorithm from this DP.

Complexity: O(amount × len(coins)) time — every amount is checked against every coin once; O(amount) space for the 1D table.

Examples in This Set

#19 (word break), #23 (edit distance), #26 (longest common subsequence), #27 (regex matching DP), #48 (0/1 knapsack), and #49 (longest palindromic substring) all use this pattern, each with its own state definition and recurrence.

Backtracking

Backtracking is recursive, exhaustive search with early pruning: at each step, try every legal choice, recurse into it, and if that path doesn't pan out, undo the choice before trying the next one. The undo step is what makes it backtracking rather than plain recursion — state that got mutated to make a choice (a cell marked visited, a value pushed onto a partial solution, a constraint set updated) must be restored to exactly what it was before trying the next sibling choice, or later branches see corrupted state.

It differs from DP in that it doesn't memoize — it's for problems asking "find all X" or "does any valid X exist" where the state space doesn't compress into a small number of reusable subproblems the way DP's does. Pruning (bailing out of a branch the instant it's provably invalid, instead of building it out fully first) is what keeps the exponential worst case tractable in practice.

Worked Example: 4-Queens

Place 4 queens on a 4x4 board, one per row, so that no two share a column or diagonal. Track used columns and both diagonal directions (row - col and row + col are each constant along one diagonal) as sets; place a queen in row row by trying every column, skipping any that conflict, recursing to the next row, then removing the queen and its constraints before trying the next column.

def solve_n_queens(n):
    solutions = []
    cols = set()
    diag1 = set()  # row - col is constant along one diagonal
    diag2 = set()  # row + col is constant along the other diagonal
    placement = []

    def backtrack(row):
        if row == n:
            solutions.append(list(placement))
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            # place the queen and mark its column/diagonals as used
            placement.append(col)
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1)
            # undo -- remove the queen and its constraints before trying the next column
            placement.pop()
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return solutions

print(solve_n_queens(4))

Tracing just the row 0, col 0 branch shows the full place-recurse-undo cycle playing out to a dead end and backing all the way out:

Every column choice starting from row 0, col 0 dead-ends by row 3, and the undo steps correctly restore placement to [] before row 0 tries col 1 next. Continuing the same process for col 1, col 2, and col 3 at row 0, running solve_n_queens(4) finds exactly two valid boards: [1, 3, 0, 2] and [2, 0, 3, 1] (each list is the column chosen for row 0, row 1, row 2, row 3 in order) — the known count of solutions for 4-queens.

Complexity: exponential worst case (naive column-permutation search is O(n!)); the column/diagonal conflict sets prune the vast majority of branches before they're ever fully built, which is why 4-queens above never even explores most of the 4⁴ = 256 raw column combinations. Space is O(n) for the recursion depth and constraint sets.

Examples in This Set

#19 (Word Break II -- enumerating every valid segmentation, not just whether one exists) and #25 (word search over a grid) both use backtracking.

Common Pitfalls Across All Five