Place Sensors on a Track to Maximize the Smallest Gap Between Them
Solve this Problempositions, the sorted locations of every mounting point along a straight track, and an integer k, choose k of those points to install sensors so that the smallest distance between any two installed sensors is as large as possible. Return that largest possible minimum distance.
Unlike most binary-search-on-answer problems, this one maximizes the answer instead of minimizing it — but the same monotonic structure still applies, just flipped: if k sensors can all be placed at least d apart, the same greedy placement (always jump to the next point at least d away from the last one placed) trivially works for any smaller d too. That "easier for a smaller gap" 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 gap shrinks. needs — search the candidate gaps directly, keeping the largest one that still manages to place every sensor.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ number of mounting points ≤ 10⁵ - ◆
0 ≤ positions[i] ≤ 10⁹, given in strictly increasing order - ◆
2 ≤ k ≤ number of mounting points
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Gap From 1 Upward
BruteFor a candidate minimum gap d, greedily place the first sensor at the leftmost point, then keep placing the next sensor at the first point at least d away from the last one placed — this greedy placement is always optimal for testing feasibility. Try d = 1, 2, 3, ... and keep the largest d that still manages to place all k sensors; the moment a d fails, every larger d fails too, so stop there. Correct, but re-scanning the whole track for every single candidate gap wastes a lot of work.
O(n · maxGap)O(1)1class Solution {
2 public int maxMinGap(int[] positions, int k) {
3 int maxGap = positions[positions.length - 1] - positions[0];
4 int ans = 0;
5 for (int d = 1; d <= maxGap; d++) {
6 if (canPlace(positions, k, d)) {
7 ans = d;
8 } else {
9 break;
10 }
11 }
12 return ans;
13 }
14
15 private boolean canPlace(int[] positions, int k, int d) {
16 int count = 1, last = positions[0];
17 for (int i = 1; i < positions.length; i++) {
18 if (positions[i] - last >= d) { count++; last = positions[i]; }
19 }
20 return count >= k;
21 }
22}Optimal — Binary Search on the Gap
OptimalWhether a gap d is achievable is monotonic: if k sensors can be placed with every pair at least d apart, the same greedy placement trivially works for any smaller gap too — and the reverse fails the same way. That monotonic "easier to satisfy as d shrinks" relationship is exactly what binary search needs: search the candidate gaps between 1 and the full span of the track, and whenever a candidate gap is achievable, remember it and try a bigger gap; otherwise it's too ambitious, so search smaller.
O(n · log(maxGap))O(1)1class Solution {
2 public int maxMinGap(int[] positions, int k) {
3 int lo = 1, hi = positions[positions.length - 1] - positions[0];
4 int ans = 0;
5 while (lo <= hi) {
6 int mid = lo + (hi - lo) / 2;
7 if (canPlace(positions, k, mid)) {
8 ans = mid;
9 lo = mid + 1;
10 } else {
11 hi = mid - 1;
12 }
13 }
14 return ans;
15 }
16
17 private boolean canPlace(int[] positions, int k, int d) {
18 int count = 1, last = positions[0];
19 for (int i = 1; i < positions.length; i++) {
20 if (positions[i] - last >= d) { count++; last = positions[i]; }
21 }
22 return count >= k;
23 }
24}