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.

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Constraints:

• 1 <= nums.length <= 104
• 0 <= 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
  Advertisement
  . Largest – Smallest, two gaps.
• Based on this, we only need to compare the max number in this bucket and the min number in the next bucket to get the relatively large gap and find out which two buckets have the largest gap.

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)