Maximum Gap is a leetcode hard 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.

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.

First Exploration

Let us do the brute force way!

V0 - Sort Elements and Two Pointer to Find Maximum Gap

class Solution {
    public int maximumGap(int[] nums) {
        Arrays.sort(nums);
        int maxDiff = 0;

        for(int ptr1=0, ptr2=ptr1+1; ptr2<nums.length; ptr1++, ptr2++){
            int diff = nums[ptr2]- nums[ptr1];
            maxDiff = Math.max(diff, maxDiff);
        }

        return maxDiff;
    }
}

Second Exploration

So we have established that brute force is simple ! What makes it hard is maybe finding a linear time solution. Let's explore more on our options and thoughts.

Step-By-Step Approach

V1 - Multiple Pass , Use Boolean Array and Two Pointer to Find Maximum Gap

class Solution {
    public int maximumGap(int[] nums) {
        int maxElem = Arrays.stream(nums).max().getAsInt();
        Boolean[] boolArray = new Boolean[maxElem+1]; 

        Arrays.fill(boolArray, Boolean.FALSE);
        for(int i=0;i<nums.length;i++){ 
            boolArray[nums[i]] = Boolean.TRUE;
        }
        int maxDiff = 0;
        int ptr1 = -1, ptr2 = 0;

        while(ptr2 < boolArray.length){
           if(boolArray[ptr2]){
               if(ptr1 != -1){
                   maxDiff = Math.max( maxDiff, ptr2-ptr1 );
               }
               ptr1 = ptr2;
           }
           ptr2++;
        }
        return maxDiff;
    }
}

Questions

We have been asked to find a linear time and linear space, and we have found one solution with linear time complexity, with actually better, constant space. So what's the catch?
What happens when we have very large number as maxElement? Shouldn't we be spending a lot of time iterating through this boolean array? Also, wasting a lot of storage space when the total elements in the nums[] is less?

Let us check our constraints in the problem before we mark it as a final solution

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

Right! 10⁹ its a huge number, a linear time solution for iterating this size of array will cause Time Limit Exceeded.

Well! The start was simple and the problem got progressively harder. Let us explore this thought process on finding an optimum solution in the next blog.

Author: Rasika.Warade

VitaminAlgo