Spread m items to maximise the closest pair
Medium · Target 25 minutes · Binary search · Type asked atGoogle
Jane StreetOptiver
There are slots at distinct positions position[i] on a line. Place m items in
m different slots so that the smallest distance between any two placed items is as large as
possible. Return that largest possible smallest distance.
Examples
| Input | Output | Why |
|---|---|---|
position = [1, 2, 3, 4, 7], m = 3 | 3 | Slots 1, 4 and 7: gaps of 3 and 3. |
position = [5, 4, 3, 2, 1, 1000000000], m = 2 | 999999999 | |
position = [10, 20, 30, 40, 50], m = 4 | 10 |
Constraints
- 2 ≤ n ≤ 10⁵
- 1 ≤ position[i] ≤ 10⁹, all distinct
- 2 ≤ m ≤ n
Hints
Hint 1
For a given distance d, can you decide quickly whether m items fit with every gap at least d?
Hint 2
Sort the positions. Put the first item in the leftmost slot, and each next item in the first slot at least d past the previous one. If that places m items, d is achievable.
Hint 3
If d is achievable, so is every smaller distance. Search for the largest achievable d, rounding the midpoint up.
Where people lose marks
- Forgetting to sort the positions before the greedy pass.
- Rounding the midpoint down while setting lo = mid: an infinite loop on the last two candidates.
- Counting gaps instead of items: m items make m − 1 gaps.
Dry run on [1,2,4,8,9,13,17],4
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5lo1hi5
Slots at 1, 2, 4, 8, 9, 13, 17. Gaps from 1 to (17 − 1) / 3 = 5. A gap that works keeps working when shrunk, so search for the last one that works; mid rounds up.
-
Step 2 / 5lo1mid3hi5
Gap 3: the greedy pass places items at 1, 4, 8, 13, 17, 5 items, enough 4. 3 works, so the answer is 3 or larger: lo = 3.
-
Step 3 / 5lo3mid4hi5
Gap 4: the greedy pass places items at 1, 8, 13, 17, 4 items, enough 4. 4 works, so the answer is 4 or larger: lo = 4.
-
Step 4 / 5lo4mid5hi5
Gap 5: the greedy pass places items at 1, 8, 13, 3 items, fewer than 4. 5 fails, so does everything above it: hi = 4.
-
Step 5 / 5answer4
lo = hi = 4: items at 1, 8, 13, 17. Gap 5 places only 3.
How to think about it
Maximising a minimum directly is awkward. The decision version is simple: can m items be placed with
every gap at least d? Sort the positions and place greedily: the first item at the leftmost slot, each next
item at the first slot at least d beyond the last one placed. Placing as far left as allowed never
hurts, because it leaves the most room for the items still to come, so the greedy count is the most items that
fit at spacing d.
A spacing that works keeps working when it is reduced, so the test is true up to the answer and false after it. This is the mirror image of the minimise-the-maximum searches: we want the last true.
- If
dfits, the answer isdor larger:lo = d. - Otherwise it is smaller:
hi = d − 1. - Round the midpoint up, or
lo = midcan repeat for ever whenhi = lo + 1.
Bounds: 1 always works (positions are distinct), and no gap can exceed
(max − min) / (m − 1), so that is a safe upper bound.
Complexity. Time O(n log n + n log(range)) · Space O(n) for the sort
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def max_min_gap(position, m):
p = sorted(position)
def fits(gap): # greedy: each item in the first slot gap past the last
placed, last = 1, p[0]
for x in p:
if x - last >= gap:
placed += 1
last = x
return placed >= m
lo, hi = 1, (p[-1] - p[0]) // (m - 1)
while lo < hi:
mid = (lo + hi + 1) // 2 # round up: lo = mid must move
if fits(mid):
lo = mid
else:
hi = mid - 1
return lo#include <vector>
#include <algorithm>
int solve(std::vector<int> p, int m) {
std::sort(p.begin(), p.end());
auto fits = [&](int gap) { // greedy placement
int placed = 1, last = p[0];
for (int x : p) if (x - last >= gap) { ++placed; last = x; }
return placed >= m;
};
int lo = 1, hi = (p.back() - p.front()) / (m - 1);
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2; // round up
if (fits(mid)) lo = mid; else hi = mid - 1;
}
return lo;
}import java.util.Arrays;
class Solution {
public int maxMinGap(int[] position, int m) {
int[] p = position.clone();
Arrays.sort(p);
int lo = 1, hi = (p[p.length - 1] - p[0]) / (m - 1);
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2; // round up
int placed = 1, last = p[0]; // greedy placement
for (int x : p) if (x - last >= mid) { placed++; last = x; }
if (placed >= m) lo = mid; else hi = mid - 1;
}
return lo;
}
}function maxMinGap(position, m) {
const p = position.slice().sort((a, b) => a - b);
const fits = gap => { // greedy placement
let placed = 1, last = p[0];
for (const x of p) if (x - last >= gap) { placed++; last = x; }
return placed >= m;
};
let lo = 1, hi = Math.floor((p[p.length - 1] - p[0]) / (m - 1));
while (lo < hi) {
const mid = lo + Math.ceil((hi - lo) / 2); // round up
if (fits(mid)) lo = mid; else hi = mid - 1;
}
return lo;
}fn solve(position: &[i64], m: i64) -> i64 {
let mut p = position.to_vec();
p.sort();
let fits = |gap: i64| -> bool { // greedy placement
let (mut placed, mut last) = (1, p[0]);
for &x in &p {
if x - last >= gap {
placed += 1;
last = x;
}
}
placed >= m
};
let (mut lo, mut hi) = (1i64, (p[p.len() - 1] - p[0]) / (m - 1));
while lo < hi {
let mid = lo + (hi - lo + 1) / 2; // round up
if fits(mid) { lo = mid } else { hi = mid - 1 }
}
lo
}import Data.List (sort)
solve :: [Int] -> Int -> Int
solve position m = go 1 ((last p - head p) `div` (m - 1))
where
p = sort position
-- greedy placement: count items, each in the first slot gap past the last one
fits gap = fst (foldl step (1, head p) (tail p)) >= m
where step (placed, lst) x
| x - lst >= gap = (placed + 1, x)
| otherwise = (placed, lst)
go lo hi
| lo >= hi = lo
| fits mid = go mid hi
| otherwise = go lo (mid - 1)
where mid = lo + (hi - lo + 1) `div` 2 -- round upVariants to try
- Return the slots chosen: replay the greedy pass at the answer.
- Slots on a circle: the gap between the last and first item also counts; fix the first item and check the wrap-around gap.
- Two-dimensional points with Manhattan distance: the check is no longer a greedy line scan, and the problem becomes much harder.
Next problems
The largest equal share for k people
A pile of p cut into shares of x yields ⌊p / x⌋ shares. Bigger shares mean fewer of them: search for the last x that still gives k.
Open the problem → Hard30 minLongest time n machines can run on shared batteries
Can all n machines run for t minutes? A battery can contribute at most t of its charge, so the test is Σ min(b, t) ≥ n·t. Search the last t that passes.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
The largest equal share for k people
A pile of p cut into shares of x yields ⌊p / x⌋ shares. Bigger shares mean fewer of them: search for the last x that still gives k.
Open the problem → Hard30 minLongest time n machines can run on shared batteries
Can all n machines run for t minutes? A battery can contribute at most t of its charge, so the test is Σ min(b, t) ≥ n·t. Search the last t that passes.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.