In a divide-and-conquer closest-pair search over drop coordinates, what must the combine step do?

## The setup You have a set of points in the plane — say the drop coordinates on a delivery run — and you want the two that are closest to each other. The brute-force answer compares every pair: `Θ(n²)`. The divide-and-conquer design is the standard way to beat it, and it is worth studying not for the result but because **the combine step is the entire design**. The divide step is trivial and the conquer step is a recursive call; everything interesting happens on the way back up. ## Divide and conquer **Divide:** sort the points by x-coordinate once, up front, and split at the median into a left set and a right set of roughly equal size, separated by a vertical line at `x = xm`. **Conquer:** recurse on each side, obtaining `dLeft` and `dRight`, the closest-pair distances within each half. Let `d = min(dLeft, dRight)`. The two halves are disjoint sets of points, so the subproblems are genuinely independent: nothing computed on the left is needed on the right, and no subproblem is ever solved twice. ## Why the combine cannot just return d `d` is the best distance among pairs *both of whose points lie on the same side*. Nothing has yet examined a pair with one point on the left and one on the right, and such a pair can easily be closer — two drops on opposite sides of the same street, with the dividing line between them. Returning `min(dLeft, dRight)` is the single most common wrong answer, and it is wrong on inputs as small as three points. ## Why the combine must not be exhaustive either The obvious fix — compare every left point with every right point — is correct and useless. That is `Θ(n²)` work at the top level alone, which by itself dominates the entire recursion. A quadratic combine turns a decomposition into a slower version of brute force. This is the general lesson of the paradigm in one example: **if the combine step ignores what the recursion learned, the recursion was pointless.** ## The pruning argument The recursion already produced a bound, and the combine step's job is to exploit it. 1. **Restrict to a band.** Any straddling pair closer than `d` must have both points within horizontal distance `d` of the dividing line — otherwise their x-difference alone already exceeds `d`. So only points in the vertical strip `[xm - d, xm + d]` are candidates. In the worst case every point is in the strip, so this step alone does not bound anything. 2. **Order the band by y.** Now walk the strip's points in increasing y-coordinate. For each point, only points whose y-coordinate is within `d` above it can possibly be closer than `d`, so you can stop scanning forward as soon as the y-gap exceeds `d`. 3. **Bound the scan with geometry.** The candidates for a given point live in a `2d`-wide, `d`-tall rectangle straddling the line. Split that rectangle into squares of side `d/2`: each square can hold at most one point, because two points in the same square would be closer than `d` and would already have been found within one half. That caps the number of candidates a point must be compared against at a small constant — the classic argument gives at most seven successors in y-order. So the strip scan is `Θ(n)` comparisons, not `Θ(n²)`, and the bound is a geometric fact rather than an assumption about the data. ## The cost, and the one bookkeeping trap With a linear combine and two half-size subproblems, the total is `Θ(n log n)`. But that holds only if the y-ordering is available for free. If you re-sort the strip by y at every level, the combine becomes `Θ(n log n)` per level and the total degrades to `Θ(n log² n)` — still far better than quadratic, but not the advertised bound. The standard fix is to have each recursive call return its points in y-order and merge the two ordered halves on the way up, exactly as a merge step would, so the ordering is maintained in linear time per level. That detail is a good senior signal: it shows you tracked where the sortedness comes from rather than assuming it. ## What the interviewer is really testing Three things, in order of weight: that you noticed the straddling case at all; that you refused the quadratic merge and looked for a bound; and that you found the bound *in the sub-answers themselves*. That last move — the recursion's result constrains the combine's search space — is the reusable idea. When you meet an unfamiliar problem and the combine step looks quadratic, the question to ask is always "what did the recursive calls already prove, and how does that shrink what I still have to check?"