Binary Search Searching the answer
242. Magnetic Force Between Two Balls
A straight road has a number of spots where a charging station can be built. spots[i] is the distance of
spot i from the start of the road. You must build exactly k stations, each at a different spot.
The spacing of a choice of spots is the distance between the two stations that are closest to each other.
The distance between two stations is the difference between their positions. Choose the k spots so that the
spacing is as large as possible, and return that spacing.
Example 1
Input: spots = [14, 2, 9, 30, 21, 5], k = 3
12Explanation: Build at 2, 14 and 30. The gaps are 12 and 16, so the spacing is 12. With 9 or 21 as the middle station instead, the spacing drops to 7 or 9.
Example 2
Input: spots = [1, 4, 6, 10], k = 4
2Explanation: There are as many stations as spots, so every spot gets one. The two closest stations are at 4 and 6.
Example 3
Input: spots = [7, 1000000000, 0, 500], k = 2
1000000000Explanation: With two stations, the best choice puts one at each end of the road, at 0 and 109.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
2 ≤ spots.length ≤ 1050 ≤ spots[i] ≤ 109- All the values in
spotsare different. 2 ≤ k ≤ spots.length
Clarifying questions
What you would ask an interviewer before writing any code.