About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Maximum Gap Problem

Problem Statement:

You are given an array of n non negative integers. You need to find the maximum difference between 2 consecutive numbers in the sorted array of the given integers.

Note:

● We need a linear time solution, not n*logn. You can use up-to linear extra space.

● Assume input is always valid, and won't overflow.

● If the input has only one element, then return 0.

● There can be duplicates elements in given array.

Input/Output Format For The Function:

Input Format:

The function contains a single argument, an integer array arr.

Output Format:

Return a single integer, maximum difference between 2 consecutive elements in sorted array of given integers.

Solution

We have provided a solution which contains necessary comments to understand the approach used:

solution.java

Description:

● We are given an input array on integers.

● First of all we find the minimum and maximum integer in this array, let's name them, min and max respectively.

● Now the range of the numbers is max – min + 1.

● We create an array named buckets of this size and use it to keep frequency of occurrence of numbers in an array.

● When we encounter the number present in the array, we increment buckets[arr[i] – max] by 1.

● After all the numbers in the array are processed, we find the maximum number of consecutive 0’s between 2 non zero elements of buckets array. This is the required answer.

Time Complexity (assuming that input arguments are already given and excluding time used in declaration of output):

O(n + range) considering the number of integers in the array are n and range is max(Elements of array) – min(Elements of array).

We iterate all the elements of the array only once, and similarly we iterate through the buckets array of size range once. So total time complexity is O(n + range).

Time Complexity:

O(n + range) considering the number of integers in the array are n and range is max(Elements of array) – min(Elements of array).

As time complexity assuming that input arguments are already given and excluding time used in declaration of output is O(n + range), to read input it will take O(n) and to store output it will take O(1) hence total complexity will be O(n + range) + O(n) + O(1) → O(n + range).

Auxiliary Space Used:

O(range) considering the range is max(Elements of array) – min(Elements of array).

We create an auxiliary array of size range to store frequency of the array elements. So, auxiliary space used is O(range).

Space Complexity:

O(n + range) considering the number of integers in the array are n and range is max(Elements of array) – min(Elements of array).

The input array is of size n, so the input space complexity is O(n), and auxiliary space used is O(range) and output uses O(1), hence total complexity will be O(n + range).


// -------- START --------
    public static int maximumGap(List arr) {
        // Write your code here
        int n = arr.size();
        //if less than 2 elements then answer is 0
        if(n==1) {
            return 0;
        }
    
        int max = 0;
        int min = 1000001;
        //finding maximum and minimum element in the array.
        for(int i = 0; i0;) {
            int cnt = 0, temp = i;
            i--;
            while(i>=0 && buckets[i]==0) {
                cnt++;
                i--;
            }
            if(i>=0) {
                ans = Math.max(ans, temp - i);
            }
        }
        return ans;
    }
    // -------- END --------