164. Maximum Gap
hardGiven an unsorted array, find the maximum gap between successive elements in its sorted form — in O(n) time and O(n) space. The classic stage for bucket sort and the pigeonhole principle.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0. You must write an algorithm that runs in linear time and uses linear extra space.
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^9
Examples
Example 1
nums = [3,6,9,1]3Explanation: The sorted form is [1,3,6,9], and the maximum gap between successive elements is 3 (between 3 and 6, or 6 and 9).
Example 2
nums = [10]0Explanation: The array contains less than 2 elements, so the answer is 0.
Example 3
nums = [1,1,1,1]0Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Sorting is O(n log n). The constraint asks for linear — what does that rule in?
Hint 2
Spread n numbers into n-1 buckets each of width ceil((max-min)/(n-1)). By pigeonhole, the maximum gap must straddle two buckets.
Hint 3
For each non-empty bucket store only its min and max. The answer is the largest gap between the max of bucket i and the min of the next non-empty bucket.
Solution approach
Reveal approach
Find the min and max of the array in one linear pass. If they are equal, return 0. Otherwise create n-1 buckets each covering an equal slice of the range [min, max]; bucket width = ceil((max-min)/(n-1)). Assign each number to bucket index (num - min) / width, and per bucket track only the running min and max — that's all the maximum-gap calculation will need. By the pigeonhole principle, at least one bucket must be empty when you spread n numbers across n-1 buckets, so the largest gap can never lie inside a single bucket. Walk the buckets in order keeping a running previous-bucket max; the answer is the largest (current-bucket min - previous-bucket max) seen across non-empty buckets. Total work is O(n) time and O(n) space.
Complexity
- Time
- O(n)
- Space
- O(n)
Related patterns
- bucket-sort
- pigeonhole
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Bloomberg
Practice these live with InterviewChamp.AI
Drill Maximum Gap and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →