Stage 4: Advanced Techniques·Binary Search on Answer

Hard#7748 min readBinary SearchGreedyLeetCode

Minimize Max Distance to Gas Station

Binary search on float distance

Real-valued binary search. Use an epsilon or fixed iterations.

Published Apr 16, 2026

Problem

You have a sorted array stations[] of positive integer positions along a highway and a budget k of additional gas stations you can place anywhere on the line. Return the minimum possible value of the largest gap between any two adjacent stations after placing all k new ones. The answer is a real number.

Place them to equalize spacing as aggressively as possible — but pieces inside different original gaps are independent, so the optimal allocation is not just "split the biggest gap first."

Input

stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 9

Output

0.50000

Explanation

Nine gaps of length 1, k = 9. Drop one new station inside each gap; every piece becomes 0.5.

Input

stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 1

Output

1.00000

Explanation

A single extra station can at best halve one gap to 0.5, but the other nine gaps of 1 remain — the max is still 1.

Input

stations = [23, 24, 36, 39, 46, 56, 57, 65, 84, 98], k = 1

Output

14.00000

Intuition

There are two tempting wrong instincts. The first is "always split the largest gap in half." It fails because splitting the largest once may still leave it larger than the second-largest, and a better plan was to split both. The second instinct is "divide k stations proportionally across gaps." Also wrong — k is an integer, gaps are real, and rounding decisions interact.

The right reframe is the same one as #410 (Split Array) and #1011 (Ship Packages): stop searching over the allocations and search over the answer.

Fix a candidate max distance D. Ask the feasibility question: "can I place stations so that every piece is ≤ D?" Per original gap g, the minimum number of splits needed is ceil(g/D) - 1 (breaking g into ceil(g/D) equal-ish pieces). Sum those over all gaps — if the total is ≤ k, D is feasible.

Feasibility is monotone:

if D is feasible, every D' > D is (bigger caps need fewer splits);
if D is infeasible, every D' < D is also infeasible.

That is a binary search on a real-valued answer. The only twist vs. integer binary search is the stopping rule — we iterate until hi - lo < ε rather than converging to adjacent integers.

Approach

Priority-Queue Greedy

TimeO((n + k) log n)

SpaceO(n)

A natural first attempt: track each gap's current piece size g_i / (c_i + 1) where c_i is how many stations we've dropped into it. At each step, pop the largest piece, increment its c_i, push it back. Repeat k times.

This greedy is optimal in principle — at each step the max piece is the bottleneck and reducing it always helps — but it has two real-world costs:

Throughput. k can be up to 10^6 on the LeetCode variant; k log n probes accumulates.
Numerical drift. Repeated g_i / (c_i + 1) divisions compound floating-point error. The answer is compared with ±1e-5, which usually passes, but it's a less robust answer than a single-division feasibility pass.

It's still worth internalizing: the priority queue is the "what's the current bottleneck?" question, answered explicitly. Binary search answers the same question implicitly by probing the answer space.

use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(Copy, Clone)]
struct Piece {
    size: f64,
    gap: f64,
    splits: u32,
}

impl PartialEq for Piece {
    fn eq(&self, other: &Self) -> bool {
        self.size == other.size
    }
}
impl Eq for Piece {}
impl PartialOrd for Piece {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.size.partial_cmp(&other.size)
    }
}
impl Ord for Piece {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap_or(Ordering::Equal)
    }
}

impl Solution {
    pub fn minmax_gas_dist(stations: Vec<i32>, k: i32) -> f64 {
        let mut heap: BinaryHeap<Piece> = BinaryHeap::new();
        for w in stations.windows(2) {
            let g = (w[1] - w[0]) as f64;
            heap.push(Piece { size: g, gap: g, splits: 0 });
        }

        for _ in 0..k {
            let mut top = heap.pop().unwrap();
            top.splits += 1;
            top.size = top.gap / (top.splits as f64 + 1.0);
            heap.push(top);
        }

        heap.peek().map(|p| p.size).unwrap_or(0.0)
    }
}

Rust · runnable

function minmaxGasDist(stations: number[], k: number): number {
  // Simple max-heap with piece objects; indices are into a parallel array.
  type Piece = { size: number; gap: number; splits: number };
  const heap: Piece[] = [];

  const push = (p: Piece) => {
    heap.push(p);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent].size >= heap[i].size) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  };

  const pop = (): Piece => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      const n = heap.length;
      while (true) {
        const l = 2 * i + 1;
        const r = 2 * i + 2;
        let best = i;
        if (l < n && heap[l].size > heap[best].size) best = l;
        if (r < n && heap[r].size > heap[best].size) best = r;
        if (best === i) break;
        [heap[best], heap[i]] = [heap[i], heap[best]];
        i = best;
      }
    }
    return top;
  };

  for (let i = 1; i < stations.length; i++) {
    const g = stations[i] - stations[i - 1];
    push({ size: g, gap: g, splits: 0 });
  }

  for (let i = 0; i < k; i++) {
    const top = pop();
    top.splits++;
    top.size = top.gap / (top.splits + 1);
    push(top);
  }

  return heap[0].size;
}

TypeScript · runnable

Binary Search on Float Distance

TimeO(n log(S/ε))

SpaceO(1)

Recommended

Lower-bound binary search over the real-valued range [0, max_gap]. The feasibility predicate counts total splits required for a candidate D and compares to k.

The termination rule switches from "lo < hi" (integer) to "hi - lo > ε" where ε ≈ 1e-6. The number of iterations is log2(max_gap / ε) ≈ 40 — bounded and tiny regardless of n.

Feasibility for gap g under cap D: minimum pieces needed is ceil(g / D), which means ceil(g / D) - 1 additional stations. Using floor division: for strict > D avoidance use floor(g / D) when g % D == 0, else floor(g / D). In floats, write it as (int)(g / D) — if g is exactly divisible by D this undercounts by one, but the ε margin absorbs the edge.

impl Solution {
    pub fn minmax_gas_dist(stations: Vec<i32>, k: i32) -> f64 {
        let k = k as i64;
        let mut lo: f64 = 0.0;
        let mut hi: f64 = 0.0;
        for w in stations.windows(2) {
            let g = (w[1] - w[0]) as f64;
            if g > hi { hi = g; }
        }

        let feasible = |d: f64| -> bool {
            let mut needed: i64 = 0;
            for w in stations.windows(2) {
                let g = (w[1] - w[0]) as f64;
                needed += (g / d).floor() as i64;
                if needed > k { return false; }
            }
            needed <= k
        };

        // ~40 iterations drives the window under 1e-6 for any practical hi.
        for _ in 0..50 {
            let mid= (lo + hi) / 2.0;
            if mid <= 0.0 { break; }
            if feasible(mid) {
                hi= mid;
            } else {
                lo= mid;
            }
            if hi - lo < 1e-7 { break; }
        }

        lo + (hi - lo) / 2.0
    }
}

Rust · runnable

function minmaxGasDist(stations: number[], k: number): number {
  let lo = 0;
  let hi = 0;
  for (let i = 1; i < stations.length; i++) {
    const g = stations[i] - stations[i - 1];
    if (g > hi) hi = g;
  }

  const feasible = (d: number): boolean => {
    let needed = 0;
    for (let i = 1; i < stations.length; i++) {
      const g = stations[i] - stations[i - 1];
      needed += Math.floor(g / d);
      if (needed > k) return false;
    }
    return needed <= k;
  };

  for (let iter = 0; iter < 50; iter++) {
    const mid = (lo + hi) / 2;
    if (mid <= 0) break;
    if (feasible(mid)) {
      hi = mid;
    } else {
      lo = mid;
    }
    if (hi - lo < 1e-7) break;
  }

  return lo + (hi - lo) / 2;
}

TypeScript · runnable

Trace

Binary search on stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 9. Nine gaps, each of size 1. Search window starts at [0, 1]:

lo	hi	mid	needed(mid)	action
0.000	1.000	0.500	9	needed ≤ 9, move hi to 0.500
0.000	0.500	0.250	27	needed > 9, move lo to 0.250
0.250	0.500	0.375	18	needed > 9, move lo to 0.375
0.375	0.500	0.4375	18	needed > 9, move lo to 0.4375
0.4375	0.500	0.46875	18	needed > 9, move lo to 0.46875

After ~40 more halvings the window closes on 0.5. The insertion count floor(1.0 / 0.5) = 2 drops the needed-stations per gap to 1; summed across 9 gaps that is exactly k.

Edge cases

k = 0 — no insertions allowed; answer is max_gap. The lower bound lo starts at 0 and the search converges on max_gap.
All equal gaps — binary search converges exactly on g / (1 + k/n) up to ε.
k much larger than n — more stations than segments; each segment's piece shrinks proportionally.
Single gap — trivially (b - a) / (k + 1).
Precision — compare results with |got - expected| < 1e-5. The 50-iteration cap gives ~2^-50 window, safely under that tolerance.

💡

Tip

When the PQ-greedy and the binary-search answers disagree past the 5th decimal, suspect the PQ-greedy: repeated divisions compound floating error. The binary search uses a single division per gap per probe.

Takeaway

Binary search on answer works on continuous ranges too — only the stopping rule changes. Instead of "adjacent integers", you stop when the window is narrower than the precision you care about, or after a fixed iteration cap (log₂ of range-over-tolerance).

This pattern shows up whenever the answer is continuous — minimum radius, maximum SLA, optimal temperature setpoint. The monotone-feasibility framing is identical; the binary search body is essentially the same four lines.

Hard#410

Split Array Largest Sum

Binary search on max sum. Check: can we split into ≤k parts each ≤ mid?

Medium#1011

Capacity To Ship Packages

Same template as #410. The greedy check is the same pattern.

Medium#875

Koko Eating Bananas

Binary search on the ANSWER. This is the gateway to a whole class of hards.

Hard#2141

Maximum Running Time of N Computers

Binary search on time + greedy check on battery allocation.

Problem

Intuition

Approach

Trace

Edge cases

Takeaway

More in Binary Search on Answer