Visualize LeetCode 774 step by step. Watch binary search narrow the maximum gap, with a linear feasibility pass counting how many extra stations keep all gaps below the candidate threshold.
The answer (minimum possible max gap) lies in [0, maxExistingGap]. Binary search this range: for each candidate d (mid), check whether adding ≤ k new stations can keep every gap ≤ d.
For each existing gap g between adjacent stations, you need ceil(g / d) − 1 new stations to subdivide it into parts of size ≤ d. Sum across all gaps: if total ≤ k, then d is feasible.
If feasible (totalNeeded ≤ k): we can afford d, so try a smaller max gap → hi = mid. If not feasible: d is too small, we need a larger threshold → lo = mid. Repeat until hi − lo < ε.
Each feasibility check is O(N). Binary search runs O(log(maxGap / ε)) iterations ≈ 50 for typical inputs. Total: O(N × log(maxGap / ε)). Space O(1).
Classic "binary search on answer". Whenever the answer is a real number and feasibility is monotone (if d works, d+ε also works), this pattern applies. LeetCode 774.