219. Widest Sorted Gap
A weather station logs the moment of every lightning strike as a whole number of milliseconds since midnight, but the readings arrive in no particular order and several strikes can share a moment. If you put all the readings in increasing order, the pause between two neighbours is the difference between a reading and the next one in that order.
Return the largest pause found in nums. If there are fewer than two readings, return 0. Repeated readings are kept, so two equal readings next to each other give a pause of 0. The log can hold up to 100,000 readings, so the solution must run in linear time; an ordinary comparison sort is not allowed to be the bottleneck.
Example 1
- Input:
- nums = [14,3,9,30,21]
- Output:
- 9
- Explanation:
In sorted order the readings are 3, 9, 14, 21, 30. The pauses are 6, 5, 7 and 9, so the largest is 9.
Example 2
- Input:
- nums = [8]
- Output:
- 0
- Explanation:
A single reading has no neighbour, so the answer is 0.
Example 3
- Input:
- nums = [41,41,41]
- Output:
- 0
- Explanation:
All readings are equal; every pause between neighbours is 0.
Example 4
- Input:
- nums = [100,1]
- Output:
- 99
- Explanation:
Sorted: 1, 100. The only pause is 99.
Constraints
0 ≤ nums.length ≤ 105
0 ≤ nums[i] ≤ 109
The answer always fits in a 32-bit signed integer.
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)
- Space
- O(n)