The problem. There are n baskets at the given positions on a line. Put m balls into baskets (at most one per basket) so that the smallest distance between any two balls is as large as possible. Return that largest possible minimum distance.
position = [1, 2, 3, 4, 7], m = 3 -> 3
position = [5, 4, 3, 2, 1, 1000000000], m = 2 -> 999999999Turn the question around: can the balls be placed so every pair is at least gap apart? Sort the positions and place greedily — the first ball in the first basket, each next ball in the first basket at least gap past the previous one. Placing as early as possible leaves the most room for the rest, so if greedy fits m balls, the gap is possible. A smaller gap is always easier, so the answers go yes, yes, …, no: binary search for the last yes. Round mid up so low = mid always makes progress.
function maxDistance(position, m) { const pos = [...position].sort((a, b) => a - b); const fits = (gap) => { // can m balls be placed at least gap apart? let count = 1, last = pos[0]; for (const p of pos) { if (p - last >= gap) { count++; last = p; } // greedy: the first basket far enough away } return count >= m; }; let gap = 1; while (fits(gap + 1)) gap++; // widen until the next gap fails return gap;}Time O(n log n + n · range), space O(n). The second example would take a billion checks.
Try the middle gap and place balls greedily: if they all fit, a bigger gap might too.
function maxDistance(position, m) { const pos = [...position].sort((a, b) => a - b); const fits = (gap) => { // can m balls be placed at least gap apart? let count = 1, last = pos[0]; for (const p of pos) { if (p - last >= gap) { count++; last = p; } // greedy: the first basket far enough away } return count >= m; }; let low = 1; let high = pos[pos.length - 1] - pos[0]; // the widest any gap could be while (low < high) { const mid = low + Math.ceil((high - low) / 2); // round up: low = mid must make progress if (fits(mid)) low = mid; // possible: try a bigger gap else high = mid - 1; // impossible: the answer is smaller } return low;}Time O(n log n + n log(range)), space O(n) for the sorted copy. Gap 1 always works (positions are distinct and m <= n), so low = 1 is a safe start.
low + (high - low + 1) / 2.