Maximum Gap
Real-world version: Widest Step Between Sorted ReadingsThe statement here is our own: the same inputs, outputs and technique.
A logger dumps nums, a batch of meter readings in the order they were captured, so the batch is in no particular order and readings may repeat.
Imagine the batch laid out on a number line from smallest to largest. Between each neighbouring pair of that laid-out sequence there is a step, and the step is the difference between the two values. Return the width of the widest step. When the batch holds fewer than two readings there is no step at all, so return 0.
Solve it in time that grows linearly with the number of readings, using extra space that also grows only linearly.
Examples
Example 1
- Input
- nums = [3, 41, 7, 20]
- Output
- 21
Laid out the readings run 3, 7, 20, 41, so the steps are 4, 13 and 21 and the widest is 21.
Example 2
- Input
- nums = [7, 7, 1]
- Output
- 6
Laid out the readings run 1, 7, 7, giving steps of 6 and 0, so the widest step is 6.
Example 3
- Input
- nums = [9]
- Output
- 0
A single reading leaves no neighbouring pair, so the answer is 0.
Example 4
- Input
- nums = [5, 5, 5]
- Output
- 0
All three readings match, so every step is 0.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def widest_reading_step(readings: list[int]) -> int:public int widestReadingStep(int[] readings)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 4 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's