Sorting and binary search

Halfway through a coding round, the interviewer mentions that the input is already sorted, or that the answer is a whole number somewhere up to a billion. Either remark invites a binary search, and the interviewer will watch whether yours stops on the first run. This lesson gets you to compare the standard sorts from memory and to write that search from a stated invariant, over an array or over possible answers.

The sorts to know and what each costs

Here n is the number of items, k the number of possible values (largest minus smallest, plus one), w the digits per key and b the base (the values one digit can take).

Merge sort splits the array in half, sorts each half and merges them by repeatedly taking the smaller front item: O(n) merging on each of about log2 n levels, so O(n log n) on every input, plus an O(n) buffer for the merge. Taking from the left half on ties makes it stable: items with equal keys keep their input order.

Quicksort picks a pivot, moves smaller items to its left and larger ones to its right, and recurses on both sides. It sorts in place, so its extra memory is the call stack. Pivots that split badly every time cause the worst case: the first element as pivot on an already sorted array gives O(n²) time and n levels of recursion. Random pivots make that unlikely, and recursing into the smaller side while looping over the larger caps the stack at O(log n). All-equal values are a second trap: the Lomuto partition most candidates write sends everything to one side, which is quadratic again. Hoare's partition, which stops on keys equal to the pivot, or a three-way split (less, equal, greater) fixes it. In-place versions are usually not stable.

Counting sort fits small integer ranges: a grayscale photo's 12 million pixel values, each 0 to 255, sort by counting each value and writing the counts back out, in O(n + 256). Radix sort extends that to wider keys with one stable counting pass per digit, lowest digit first; 32-bit unsigned integers in base 256 take four passes. Neither compares items, so the O(n log n) lower bound for sorts that only compare doesn't apply.

In an interview, call sorted() unless asked to write a sort, and say "O(n log n), and it's stable" as you do.

Sort first, then make one pass

Many problems get easy once related items sit together: after a sort, equal values are adjacent and overlapping intervals are neighbors, so checking every pair, O(n²), often becomes one scan after an O(n log n) sort.

Take a meeting room whose bookings are (start, end) minute pairs that may overlap: how many minutes is it booked? Sorted by start, one pass does it: keep reach, the latest end seen so far, and let each booking add only the part that sticks out past it.

def booked_minutes(bookings):
    """Minutes covered by at least one (start, end) booking; end is exclusive."""
    total, reach = 0, float("-inf")
    for start, end in sorted(bookings):
        if end > reach:
            total += end - max(start, reach)
            reach = end
    return total


print(booked_minutes([(60, 90), (0, 30), (20, 45), (70, 80)]))  # 75

One pass is enough because the booking that set reach started no later than this one, so every minute from this start up to reach is already counted. Sorting costs O(n log n) and the pass O(n), for n bookings.

Sort by your own rule

Python's key= maps each item to the value to sort by, once per item. Tuples compare field by field, so a tuple key sorts by several fields, and negating a number flips its direction. Strings can't be negated, so for a descending string field, sort twice with the less important field first: the second sort is stable and keeps the first order among its ties. reverse=True stays stable too.

from collections import namedtuple
from functools import cmp_to_key

Result = namedtuple("Result", "team points seconds")
results = [Result("owls", 90, 31.5), Result("bees", 95, 40.0),
           Result("cats", 90, 29.0), Result("ants", 95, 40.0)]

podium = sorted(results, key=lambda r: (-r.points, r.seconds, r.team))  # ants, bees, cats, owls

by_name = sorted(results, key=lambda r: r.team, reverse=True)
by_points = sorted(by_name, key=lambda r: r.points)  # owls, cats, bees, ants

def concat_order(a, b):
    """Negative when a should come first: a + b spells the bigger number."""
    if a + b == b + a:
        return 0
    return -1 if a + b > b + a else 1

pieces = ["3", "30", "34", "5", "9"]
print("".join(sorted(pieces, key=cmp_to_key(concat_order))))  # 9534330

The last sort spells the largest number from digit strings. "3" goes before "30" but after "34", so the rule is about pairs, and a comparator states it directly: a function of two items that returns a negative number, zero or a positive number, which cmp_to_key adapts for sorted().

A comparator must be consistent: if a comes before b and b before c, then a comes before c. Break that and the output depends on the input order; Java's sort may even throw "Comparison method violates its general contract!" The interviewer sees a sort that passes one test and fails a shuffled copy of it. A smaller slip: list.sort() returns None, so items = items.sort() loses your list.

Binary search with a stated invariant

Binary search finds a boundary. It needs a range of positions and a yes/no check that reads False, ..., False, True, ..., True across it, such as "is a[i] at least the target?" on a sorted array. Each probe of the middle rules out half of what remains.

Write down what lo and hi mean before the loop. Below, every position before lo is known to fail and every position from hi on is known to pass, counting the position just past the range as a pass that stands for "none".

def first_true(lo, hi, ok):
    """Smallest i in [lo, hi) with ok(i) True, or hi if there is none.
    ok must read False, ..., False, True, ..., True across the range."""
    # Invariant: ok is False everywhere before lo, True from hi on.
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid        # mid passes: the first pass is mid or earlier
        else:
            lo = mid + 1    # mid fails: the first pass is after mid
    return lo


prices = [3, 8, 8, 12, 20]
print(first_true(0, len(prices), lambda i: prices[i] >= 10))  # 3

Both branches keep the invariant and shrink hi - lo, so the loop ends, and when lo == hi the boundary is there. A range of n positions takes at most ⌈log2(n + 1)⌉ checks: O(log n) time and O(1) space. Say the invariant while you write it:

"lo is the first index that could still be the answer, and everything from hi on passes. If mid passes, hi moves to mid; if it fails, lo moves past it. The gap shrinks every pass, so when they meet, that's the first passing index, or the end if nothing passes."

Most bugs change one line without changing the invariant to match:

Python's bisect.bisect_left(a, x) runs this loop on a sorted list, returning the first index whose value is at least x; use it if the interviewer allows.

Binary search on the answer

Sometimes nothing in the input is sorted, but the possible answers are. If a check, "can it be done with value x?", flips only once as x grows, you can binary search over x.

A street festival has permitted spots along one road, and k food trucks must each take a different spot. Place them so the closest two trucks are as far apart as possible, and return that distance. The check fits(gap) asks whether k trucks fit with every pair at least gap apart: park the first truck at the leftmost spot and each next one at the first spot at least gap past the previous truck, since parking as far left as allowed never leaves less room for the rest. Trucks gap apart are also gap - 1 apart, so fits reads True up to the answer and False after it, and the answer is one less than the first gap that fails.

def widest_spacing(spots, k):
    """Largest gap such that k trucks fit on distinct spots with every pair
    at least that far apart. Assumes 2 <= k <= len(spots)."""
    spots = sorted(spots)

    def fits(gap):
        placed, last = 1, spots[0]          # first truck at the leftmost spot
        for s in spots[1:]:
            if s - last >= gap:
                placed, last = placed + 1, s
        return placed >= k

    outer = spots[-1] - spots[0]            # outer + 1 can never fit
    return first_true(1, outer + 1, lambda gap: not fits(gap)) - 1


print(widest_spacing([1, 2, 4, 8, 9], 3))  # 3

Sorting costs O(n log n), each check O(n), and the search makes O(log S) checks, where n is the number of spots and S is the distance between the two outermost spots: O(n log n + n log S) in all. A prompt asking for the smallest value that works has the same shape facing the other way, and first_true answers it directly.

The mistake here is a check that isn't monotone. If a bigger value can turn a yes back into a no, the search quietly returns a wrong boundary, and the interviewer sees it pass your examples and fail theirs. Before coding, say in one sentence why that can't happen.

Searching things that are not arrays

first_true needs only a range and a check:

• Commits. A test that passed 1,000 commits ago fails now. "Is commit i broken?" reads False and then True, so first_true(0, 1000, is_broken) finds the first bad commit in at most 10 builds (2^10 = 1,024). git bisect runs this search for you.

• Binary search trees. Each comparison discards one subtree, so a lookup costs O(h) for a tree of height h: O(log n) only when the tree is balanced, which lesson 7 covers.

• Real numbers. With no next position, run a fixed number of halvings sized to the precision you need: a range of 1,000 shrinks below 0.000001 in 30, since 2^30 is about 1.07 billion.

• Sorted linked lists. Reaching the middle node costs O(n) steps, so binary search saves nothing over a scan.

Practicing with these questions

For each binary search question, write what lo and hi mean as a comment before the loop, then trace a range of one or two positions by hand, where every bug in the table above shows up. For the sorting questions, say the cost and whether you need stability before you sort. When a question asks for the best value that makes something possible, write the check first and convince yourself it flips once. Save Combined Median of Two Sorted Integer Lists in Logarithmic Time for last, and decide what range you are searching before you code. The Blind 75 binary search set has more reps for the loop itself.