Maximum Gap
Medium · Arrays & Hashing · Array · Sorting · Bucket Sort · Radix Sort
Problem
Given an integer array nums, return the largest difference between two consecutive elements of its sorted order. If the array has fewer than two elements, return 0.
Your algorithm must run in linear time and use linear extra space, so a comparison sort is not allowed.
Examples
Input: nums = [15,2,9,4] Output: 6
Sorted, the array is [2,4,9,15]; the gaps are 2, 5 and 6.
Input: nums = [42] Output: 0
A single element has no neighbor to compare with.
Input: nums = [3,6,9,1] Output: 3
Sorted: [1,3,6,9]. The gaps are 2, 3 and 3.
Constraints
- 1 <= len(nums) <= 10^5
- 0 <= nums[i] <= 10^9
Approaches
- Baseline: comparison sort, then scan — time O(n log n), space O(n)
Follow-up
The bucket trick works because the largest gap is at least the average gap. The smallest gap has no such guarantee, so finding it needs a sort (or hashing tricks with randomization). The use cases ask for the smallest gap, and for the largest gap when the values sit on a circle.
Related problems
Start free on Cariara · Coding problems · System design studio
