Core techniques: binary search on the answer, two pointers, sliding windows

Four techniques solve a disproportionate share of coding problems, and each has a recognisable cue. Binary search applies whenever a predicate is monotone, two pointers whenever the array is sorted, sliding windows whenever the constraint is on a contiguous range, and prefix sums whenever the query is a range aggregate.

Proposition 5.1

Binary search on the answer

When a question asks for a minimum or maximum value satisfying some condition, and the condition is monotone in that value — once it holds it keeps holding — you can binary search over the answer rather than over an array. Check feasibility at a candidate, and halve the range.

Holds when

The cue is "minimum capacity", "maximum distance", "smallest $k$ such that…".
You need a feasibility test that is cheaper than solving the problem directly.
Total cost is $O(\log(\text{range}) \times \text{cost of the test})$ .

Figure 5.2 · Binary search on the answer. A thousand candidates in ten questions. The move that turns an optimisation into a search is noticing the predicate is monotone — once "can it be done in

x

?" is yes-then-no, the answer is the boundary and you never enumerate anything.

Monotonicity is the only requirement. Binary search is usually taught on a sorted array, which makes people look for sortedness. What it actually needs is a predicate that is false, false, false, then true, true, true — the array being sorted is one way to get that and not the interesting one. Once you look for monotone predicates instead of sorted arrays, a whole class of optimisation problems becomes a search: "can we finish in $T$ days?" is monotone in $T$ , so find the smallest $T$ for which it is true.

def min_capacity(weights: list[int], days: int) -> int:
    """Smallest ship capacity that moves all weights within the day budget."""
    def feasible(cap: int) -> bool:
        need, load = 1, 0
        for w in weights:
            if load + w > cap:
                need, load = need + 1, 0
            load += w
        return need <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:                    # invariant: answer is in [lo, hi]
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                  # mid works; it might be the answer
        else:
            lo = mid + 1              # mid fails; the answer is above
    return lo

Listing 5.3 · Binary search on the answer. The loop invariant is the whole discipline: keep the answer inside

[lo, hi]

, never exclude it, and let the range shrink to a point. Written this way the off-by-one errors have nowhere to live. Time O(n log(sum)) · Space O(1).

Core techniques: binary search on the answer, two pointers, sliding windows

After this lesson you should be able to

Binary search on the answer

The rest of this lesson is in Premium