Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Binary search

The pattern: maximise the minimum

Lesson · 11 min read · Binary search · Pattern: maximise the minimum

The mirror image of the last module: the largest gap, share or running time that can be guaranteed. Search for the last value that passes; round the midpoint up.

The mirror image

Now the question asks for the largest value of a guarantee: the widest spacing between placed items, the biggest equal share, the longest time all machines can run. Smaller guarantees are easier to meet, so the test is true up to the answer and false after it, and the answer is the last true.

Maximise the minimum

solve(input)

  1. lo = a value that certainly works; hi = an upper bound on the answer.
  2. Last-true search: while lo < hi, mid = lo + (hi − lo + 1) / 2, rounded up.
  3. If feasible(mid), lo = mid; otherwise hi = mid − 1.
  4. Return lo.

The rounding is the trap. With lo = mid on a pass and mid rounded down, a range of two candidates never shrinks; the first module traced the loop that results. Round up, or convert to a first-true search for the first value that fails and subtract one.

The greedy check for spacing

For "place m items in slots so the closest pair is as far apart as possible", sort the slots and test a gap g by placing an item in the first slot and then in each slot at least g past the last item placed. If that places m items, g is achievable. Taking the earliest possible slot never hurts, because it leaves the most room for the items after it.

Three items in seven slots: the widest guaranteed gap.

  1. Step 1 / 6
    lo 1hi 10
    lo1hi10

    Slots at 2, 5, 9, 11, 16, 20, 23. Gaps from 1 to (23 − 2) / 2 = 10. A gap that works keeps working when shrunk, so search for the last one that works; mid rounds up.

  2. Step 2 / 6
    lo 1hi 10mid 6 ✓
    lo1mid6hi10

    Gap 6: the greedy pass places items at 2, 9, 16, 23, 4 items, enough 3. 6 works, so the answer is 6 or larger: lo = 6.

  3. Step 3 / 6
    1lo 6hi 10mid 8 ✓
    lo6mid8hi10

    Gap 8: the greedy pass places items at 2, 11, 20, 3 items, enough 3. 8 works, so the answer is 8 or larger: lo = 8.

  4. Step 4 / 6
    1lo 8hi 10mid 9 ✓
    lo8mid9hi10

    Gap 9: the greedy pass places items at 2, 11, 20, 3 items, enough 3. 9 works, so the answer is 9 or larger: lo = 9.

  5. Step 5 / 6
    1lo 9hi 10mid 10 ✗
    lo9mid10hi10

    Gap 10: the greedy pass places items at 2, 16, 2 items, fewer than 3. 10 fails, so does everything above it: hi = 9.

  6. Step 6 / 6
    110answer 9
    answer9

    lo = hi = 9: items at 2, 11, 20. Gap 10 places only 2.

TimeO(n log n + n log(range))
SpaceO(1) after sorting

Two more checks

ProblemRangefeasible(x)Why
The largest equal share for k people1 to the largest pile; 0 if even 1 failsΣ ⌊pile / x⌋ ≥ keach pile yields ⌊pile / x⌋ shares of size x
Longest time n machines can run0 to ⌊Σ batteries / n⌋Σ min(battery, x) ≥ n × xa battery can contribute at most x minutes, since it powers one machine at a time

The battery check is the one that needs thought. A battery with more than x minutes is effectively a dedicated battery for one machine; the rest can be pooled and swapped, and pooled charge is enough exactly when the total of min(battery, x) covers n machines for x minutes each.

Start the share problem's check at x = 1, not 0: x = 0 divides by zero. Test x = 1 separately and return 0 if it fails.

Problems in this module