359. Spread the Magnets
A museum has a long rail with notches at the integer positions listed in positions, in no particular order. It must mount m small magnets on the rail, each one on a different notch, and it wants them to repel as little as possible, which means keeping them as far apart as it can.
The closeness of a layout is the smallest distance between any two of its magnets. Return the largest closeness that any layout of the m magnets can achieve. If every notch is at the same position the answer is 0. Do not try every layout: there are far too many of them.
Example 1
- Input:
- positions = [1,4,9,10,14], m = 3
- Output:
- 5
- Explanation:
Placing magnets at 1, 9 and 14 gives distances 8 and 5, so the closeness is 5, the best possible.
Example 2
- Input:
- positions = [6,6], m = 2
- Output:
- 0
- Explanation:
Both notches are at position 6, so the distance between the magnets is 0.
Constraints
2 ≤ m ≤ positions.length ≤ 105
0 ≤ positions[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n + n log D)
- Space
- O(1)