Place Chargers in Baskets to Maximize the Minimum Distance Between Them

Implement maxMinDistance

Given baskets, the locations of every basket (given in no particular order), and an integer m, choose m of those baskets to place a charger in so that the smallest distance between any two chargers is as large as possible. Return that largest possible minimum distance. Since the baskets aren't given sorted, the first step is sorting them — the greedy feasibility check (always jump to the next basket at least d away from the last placed charger) only makes sense once positions are in order. From there this becomes exactly the same pattern as maximizing the minimum spacing between placed sensors: if m chargers can all be placed at least d apart, that same greedy placement trivially works for any smaller d too. That "easier for a smaller distance" relationship is exactly what a binary search on the answerBinary Search on the AnswerThe search runs directly over the space of candidate answers rather than over the array's values. It applies whenever "is this candidate good enough?" is monotonic in one direction — here, achievability only ever improves as the candidate distance shrinks. needs — search the candidate distances directly, keeping the largest one that still manages to place every charger.

Example 1:

Input: baskets = [2,3,5,6,9], m = 3

Output: 3

Example 2:

Input: baskets = [3,1,9,20,15], m = 3

Output: 8

Example 3:

Input: baskets = [1,10], m = 2

Output: 9

+ 5 hidden test cases run on Submit.

Constraints:

  • 2 ≤ number of baskets ≤ 10⁵
  • 0 ≤ baskets[i] ≤ 10⁹ (given in any order)
  • 2 ≤ m ≤ number of baskets

baskets =

[2, 3, 5, 6, 9]

m =

3