Spread Out the Sensors
MediumBinary Search
Problem
Along a pipeline there are mounting points at the distinct integer positions points (in any order). You must install count sensors, each on a different mounting point, so that interference is as low as possible.
Return the largest possible value of the smallest distance between any two installed sensors.
Example 1
- Input:
- points = [1, 9, 4, 7, 2], count = 3
- Output:
- 3
Sensors at 1, 4 and 7 are at least 3 apart. No placement keeps all three 4 apart.
Example 2
- Input:
- points = [10, 1, 20], count = 2
- Output:
- 19
Use the two extreme points, 1 and 20.
Example 3
- Input:
- points = [5, 6, 7, 8], count = 4
- Output:
- 1
Constraints
- 2 ≤ count ≤ points.length ≤ 10^5
- 0 ≤ points[i] ≤ 10^9
- All points are distinct.
Hint
Show the first hint
If you can keep every pair at least d apart, can you also keep them at least d - 1 apart?
Walkthrough
How to approach it
01Clarify before coding
- Are the points sorted? No, sort them first.
- Must every sensor be on a mounting point? Yes, so gaps are differences between points.
- Is the answer an integer? Yes, positions are integers.
02Brute force
Try every subset of count points and compute its minimum gap.
Cost: C(n, count) subsets: astronomically many for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.