VitaminAlgo

VitaminAlgo

Maximum Gap

Maximum Gap

Anup Kalburgi's photo
Anup Kalburgi
·Feb 5, 2022·

2 min read

Table of contents

  • First Exploration
  • Second Exploration
  • Questions

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!

Page1.png

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.

Page2.png

Step-By-Step Approach

Page3.png

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! 109 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

 
Share this