The idea
When a problem asks for the largest or smallest value that satisfies a condition, try turning it around: for a given value, can the condition be met? That check is usually a simple greedy pass.
If feasibility is monotone (when d works, everything smaller works too), binary-search the value. The cost is O(check × log range).
Phrases that signal it: “maximise the minimum”, “minimise the maximum”, “the least time / capacity needed”.
Sample problem
1552. Magnetic Force Between Two Balls ↗ Medium
There are baskets at given positions and m balls. Put each ball in a basket so that the smallest distance between any two balls is as large as possible. Return that distance.
position = [1,2,3,4,7], m = 3 output = 3 (balls at 1, 4, 7)
Why the solution works
Choosing the baskets directly is hard. Checking a given distance d is easy: go left to right and greedily place a ball whenever the basket is at least d from the previous ball. If m balls fit, d is feasible.
Feasibility is monotone: if d works, every smaller d works. So the answers form “yes … yes, no … no”, and binary search finds the last yes.
This is the pattern behind “maximise the minimum”: search the answer, verify with a greedy pass.
Complexity: O(n log n) to sort, plus O(n log(range)) for the search. O(1) extra memory.
Watch out
- Convince yourself the check is monotone before coding; otherwise binary search returns nonsense.
- The bounds must contain the answer: start from the widest sensible range.
- Sums inside the check often overflow
int.