Maximum Gap in C++

Suppose we have an array, that is not sorted. We have to find the maximum difference between successive elements in its sorted form. We will return 0 if the array contains less than 2 elements. So if the array is like [12,3,9,1,17], then the output will be 6, as the sorted array will be [1,3,9,12,17] so 5 will be the maximum difference as difference between 3 and 9 is 6.

To solve this, we will follow these steps −

• minVal := inf, maxCal := -inf

• n := size of nums

• if n < 2, then return 0;

• for i in range 0 to n – 1 −

  • minVal := min of nums[i] and minVal

  • maxVal := max of nums[i] and maxVal

• gap := celing of maxVal – minVal / n – 1

• make one array called bucketMax of size n – 1, and fill this with –inf

• make one array called bucketMin of size n – 1, and fill this with inf

• for i in range 0 to n – 1 −

  • x := nums[i]

  • if x = minVal or x = maxVal, then skip next part, go for next iteration

  • idx := (nums[i] – minVal) / gap.

  • bucketMax[idx] := max of bucketMax[idx] and nums[i]

  • bucketMin[idx] := min of bucketMin[idx] and nums[i]

• ret := 0

• prev := minVal

• for i in range 0 to n – 1

  • if bucketMax[i] = -inf and bucketMin[i] = inf, then skip next part, go for next iteration

  • ret := max of ret and bucketMin[i] – prev

  • prev := bucketMax[i]

• return max of ret, maxVal - prev

Example

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution {    public:    int maximumGap(vector<int>& nums) {       lli minVal = INT_MAX;       lli maxVal = INT_MIN;       int n = nums.size();       if(n < 2) return 0;       for(int i = 0; i < n; i++){          minVal = min((lli)nums[i], minVal);          maxVal = max((lli)nums[i], maxVal);       }       int gap = ceil((double)(maxVal - minVal) / (double)(n - 1));       vector <int> bucketMax(n - 1, INT_MIN);       vector <int> bucketMin(n - 1, INT_MAX);       for(int i = 0; i < n; i++){          int x = nums[i];          if(x == minVal || x == maxVal) continue;          int idx = (nums[i] - minVal) / gap;          bucketMax[idx] = max(bucketMax[idx], nums[i]);          bucketMin[idx] = min(bucketMin[idx], nums[i]);       }       lli ret = 0;       lli prev = minVal;       for(int i = 0; i < n - 1; i++){          if(bucketMax[i] == INT_MIN && bucketMin[i] == INT_MAX) continue;          ret = max(ret, bucketMin[i] - prev);          prev = bucketMax[i];       }       return max(ret, maxVal - prev);    } }; main(){    Solution ob;    vector<int> v = {12,3,9,1,17};    cout << (ob.maximumGap(v)); }

Input

[12,3,9,1,17]

Output

6