Leetcode – 164. Maximum Gap
Given an integer array nums, return the maximum difference between two successive elements in their 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.
Example 1:
Input: nums = [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.
Example 2:
Input: nums = [10] Output: 0 Explanation: The array contains less than 2 elements, therefore return 0.
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 109
Solution:
The main problem is we can’t sort the array as it will take n log(n) complexity, but as asked we have to do this in O(n).
We will be solving this question using The Pigeonhole Principle. (Recommended: Watch this video)
The pigeonhole principle states that “if n items are put into m containers, with n>m, then at least one container must contain more than one item.” Sounds simple but it has many applications.
To understand the solution, you must be first familiar with bucket sort.
- For example, we set the bucket size to be 10, those numbers can be put into the above buckets. If we set the bucket size clever(relatively small), we can ensure that the max gap cannot be in the same bucket. In the worst-case, each successive numbers have the same gap. For example, we have 1, 3, 5 the gap and the max gap is
(5 - 1) / 2
Table of Contents
Step 1 – Find maximum and minimum elements from the input
int max = nums[0];
int min = nums[0];
for(int num:nums){
max = Math.max(num, max) ;
min = Math.min(num, min);
}Step 2 – Create min and max bucket
int[] maxBucket = new int[n];
int[] minBucket = new int[n];
Arrays.fill(maxBucket,Integer.MIN_VALUE);
Arrays.fill(minBucket,Integer.MAX_VALUE);
Step 3 – Derive bucket size
int bucketSize = (int)Math.ceil((double)(max-min)/(n - 1));
Step 4 – Fill up min and max elements belongs to buckets
As we can’t have the maximum gap lies in the same bucket (because at maximum gap we can have is bucketSize-1, so we will be maintaining only min and max elements in the respective buckets.
for(int num: nums){
int bucketIndex = (num-min) / bucketSize;
maxBucket[bucketIndex] = Math.max(num,maxBucket[bucketIndex]);
minBucket[bucketIndex] = Math.min(num,minBucket[bucketIndex]);
}Step 5 – Finding out the maximum gap
int maxGap = 0;
int previous = maxBucket[0];
for(int i=1;i<n;i++){
if(minBucket[i] == Integer.MAX_VALUE)
continue;
maxGap = Math.max(maxGap,minBucket[i] - previous);
previous = maxBucket[i];
}Complete Code
class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if(n < 2)
return 0;
int max,min = nums[0];
int min = nums[0];
for(int num:nums){
max = Math.max(num, max) ;
min = Math.min(num, min);
}
if(max == min)
return 0;
int[] maxBucket = new int[n];
int[] minBucket = new int[n];
Arrays.fill(maxBucket,Integer.MIN_VALUE);
Arrays.fill(minBucket,Integer.MAX_VALUE);
int bucketSize = (int)Math.ceil((double)(max-min)/(n -1));
for(int num: nums){
int bucketIndex = (num-min) / bucketSize;
maxBucket[bucketIndex] = Math.max(num,maxBucket[bucketIndex]);
minBucket[bucketIndex] = Math.min(num,minBucket[bucketIndex]);
}
int maxGap = 0;
int previous = maxBucket[0];
for(int i=1;i<n;i++){
if(minBucket[i] == Integer.MAX_VALUE)
continue;
maxGap = Math.max(maxGap,minBucket[i] - previous);
previous = maxBucket[i];
}
return maxGap;
}
}Complexity
Time complexity: O(n)
Space complexity: O(n)
