DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

Maximum Gap

#go #javascript #algorithms #programming

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/maximum-gap.

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.
Enter fullscreen mode Exit fullscreen mode

Example 2:

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

Constraints:

- 1 <= nums.length <= 10^5 - 0 <= nums[i] <= 10^9
Enter fullscreen mode Exit fullscreen mode

Solution

Approach 1: Brute force

The brute force approach sorts the array and finds the maximum difference between two adjacent elements. The time complexity of this approach is O(n), and the space complexity is O(1).

A C++ snippet of this approach is as below:

int maximumGap(vector<int>& nums) { int n = nums.size(); if(n <= 1) { return 0; } sort(nums.begin(), nums.end()); int maxDifference = INT_MIN; for(int i = 0; i < n - 1; i++) { maxDifference = max(maxDifference, nums[i + 1] - nums[i]); } return maxDifference; }
Enter fullscreen mode Exit fullscreen mode

Approach 2: Pigeonhole Sorting

The problem statement mentions solving the problem in linear time, using linear extra space. We can use the concept of Pigeonhole Sorting. Pigeonhole algorithm is suitable for sorting lists of elements where the number of elements and possible key values is approximately the same. It requires O(n + Range) time, where n is the number of elements in the input array and Range is the number of possible values in the array.

The flow of this algorithm is as follows:

- Find the minimum and maximum values in the array. We get the difference between the maximum and minimum value, which we call range. `range = maximum - minimum + 1`. - Create an array of empty values (pigeonholes) with a size range. - Iterate over the input array and insert each element in its pigeonhole. An element nums[i] is inserted in the hole at index nums[i] - min. - Iterate over the pigeonhole array in order and insert the elements from the non-empty pigeonhole back into the original array.
Enter fullscreen mode Exit fullscreen mode

We apply the above approach to find the maximum gap between two successive elements in the sorted array.

Let's check the algorithm.

Algorithm 

- set maximum = nums[0] minimum = nums[0] n = nums.size() - if n <= 1 - return 0 - end if - loop for i = 1; i < n; i++ // set maximum and minimum - maximum = max(maximum, nums[i]) - minimum = min(minimum, nums[i]) - end for // create arrays to store maximum and minimum values in n-1 buckets of range - vector<int> maxBucket(n - 1, INT_MIN) - vector<int> minBucket(n - 1, INT_MAX) // calculate the range - range = ceil((maximum - minimum) / (n - 1)) // traverse through the input array and insert the element in the appropriate bucket // if the bucket is empty else, update bucket values - loop for i = 0; i < n; i++ - if nums[i] == maximum || nums[i] == minimum - continue - end if // compute the index of the bucket - index = ((nums[i] - minimum) / range) - maxBucket[index] = max(maxBucket[index], nums[i]) - minBucket[index] = min(minBucket[index], nums[i]) - end for // find the maximum gap between the maximum value // of the previous bucket minus a minimum of the current bucket. - set previousValue = minimum maximumGap = 0 - loop for i = 0; i < n - 1; i++ - if minBucket[i] == INT_MAX - continue - end if - maximumGap = max(maximumGap, minBucket[i] - previousValue) - previousValue = maxBucket[i] - end for - set maximumGap = max(maximumGap, maximum - previousValue) - return maximumGap
Enter fullscreen mode Exit fullscreen mode

The time complexity of this approach is O(n), and the space complexity if O(n).

Let's check out our solutions in C++, Golang, and Javascript.

C++ solution 

class Solution { public: int maximumGap(vector<int>& nums) { int maximum = nums[0], minimum = nums[0]; int n = nums.size(), i; if(n <= 1) { return 0; } // find the maximum and minimum in nums[] for(int i = 1; i < n; i++) { maximum = max(maximum, nums[i]); minimum = min(minimum, nums[i]); } // create arrays to store maximum and minimum values in n-1 buckets of range. vector<int> maxBucket(n - 1, INT_MIN); vector<int> minBucket(n - 1, INT_MAX); // calculate the range int range = ceil((maximum - minimum) / (n - 1)); // traverse through the input array and insert the element in the appropriate bucket // if the bucket is empty else, update bucket values for (i = 0; i < n; i++) { if (nums[i] == maximum || nums[i] == minimum) continue; // compute the index of the bucket int index = ((nums[i] - minimum) / range); maxBucket[index] = max(maxBucket[index], nums[i]); minBucket[index] = min(minBucket[index], nums[i]); } // find the maximum gap between the maximum value // of the previous bucket minus a minimum of the current bucket. int previousValue = minimum; int maximumGap = 0; for (i = 0; i < n - 1; i++) { if (minBucket[i] == INT_MAX) continue; maximumGap = max(maximumGap, minBucket[i] - previousValue); previousValue = maxBucket[i]; } maximumGap = max(maximumGap, maximum - previousValue); return maximumGap; } };
Enter fullscreen mode Exit fullscreen mode

Go solution 

func maximumGap(nums []int) int { maximum, minimum := nums[0], nums[0] n, i := len(nums), 0 if n <= 1 { return 0 } // find the maximum and minimum in nums[] for i = 1; i < n; i++ { maximum = max(maximum, nums[i]) minimum = min(minimum, nums[i]) } // create arrays to store maximum and minimum values in n-1 buckets of range. maxBucket := make([]int, n - 1) minBucket := make([]int, n - 1) for j := range maxBucket { maxBucket[j] = math.MinInt32 minBucket[j] = math.MaxInt32 } // calculate the range rangeValue := int(math.Ceil(float64(maximum - minimum) / float64(n - 1))) // traverse through the input array and insert the element in the appropriate bucket // if the bucket is empty else, update bucket values for i = 0; i < n; i++ { if nums[i] == maximum || nums[i] == minimum { continue } index := ((nums[i] - minimum) / rangeValue) maxBucket[index] = max(maxBucket[index], nums[i]) minBucket[index] = min(minBucket[index], nums[i]) } // find the maximum gap between the maximum value // of the previous bucket minus a minimum of the current bucket previousValue, maximumGap := minimum, 0 for i = 0; i < n - 1; i++ { if minBucket[i] == math.MaxInt32 { continue } maximumGap = max(maximumGap, minBucket[i] - previousValue) previousValue = maxBucket[i] } return max(maximumGap, maximum - previousValue) } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }
Enter fullscreen mode Exit fullscreen mode

JavaScript solution 

/** * @param {number[]} nums * @return {number} */ var maximumGap = function(nums) { let maximum = nums[0], minimum = nums[0]; let n = nums.length, i; if(n <= 1) { return 0; } // find the maximum and minimum in nums[] for(i = 1; i < n; i++) { maximum = Math.max(maximum, nums[i]); minimum = Math.min(minimum, nums[i]); } // create arrays to store maximum and minimum values in n-1 buckets of range. let maxBucket = new Array(n - 1).fill(Number.MIN_SAFE_INTEGER); let minBucket = new Array(n - 1).fill(Number.MAX_SAFE_INTEGER); // calculate the range let range = Math.ceil((maximum - minimum) / (n - 1)); // traverse through the input array and insert the element in the appropriate bucket // if the bucket is empty else, update bucket values for (i = 0; i < n; i++) { if (nums[i] == maximum || nums[i] == minimum) continue; // compute the index of the bucket let index = ((nums[i] - minimum) / range); maxBucket[index] = Math.max(maxBucket[index], nums[i]); minBucket[index] = Math.min(minBucket[index], nums[i]); } // find the maximum gap between the maximum value // of the previous bucket minus a minimum of the current bucket. let previousValue = minimum; let maximumGap = 0; for (i = 0; i < n - 1; i++) { if (minBucket[i] == Number.MAX_SAFE_INTEGER) continue; maximumGap = Math.max(maximumGap, minBucket[i] - previousValue); previousValue = maxBucket[i]; } maximumGap = Math.max(maximumGap, maximum - previousValue); return maximumGap; };
Enter fullscreen mode Exit fullscreen mode

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: nums = [3, 6, 9, 1] Step 1: maximum = nums[0] = 3 minimum = nums[0] = 3 n = nums.size() = 4 Step 2: if n <= 1 4 <= 1 false Step 3: // find the maximum and minimum in nums[] loop for int i = 1; i < n; i++ // at the end of this loop we get max // and min maximum = 9 minimum = 1 Step 4: vector<int> maxBucket(n - 1, INT_MIN) maxBucket = [INT_MIN, INT_MIN, INT_MIN] vector<int> minBucket(n - 1, INT_MAX) minBucket = [INT_MAX, INT_MAX, INT_MAX] Step 5: range = ceil((maximum - minimum) / (n - 1)) = ceil(9 - 1 / 4 - 1) = ceil(8 / 3) = 2 Step 6: loop for i = 0; i < n 0 < 4 true if nums[i] == maximum || nums[i] == minimum nums[0] == 9 || nums[0] == 1 3 == 9 || 3 == 1 false index = ((nums[i] - minimum) / range) = ((nums[0] - 1) / 2) = (3 - 1) / 2 = 1 maxBucket[index] = max(maxBucket[index], nums[i]) maxBucket[1] = max(maxBucket[1], nums[0]) = max(INT_MIN, 3) = 3 maxBucket = [INT_MIN, 3, INT_MIN] minBucket[index] = min(minBucket[index], nums[i]) minBucket[1] = max(minBucket[1], nums[0]) = max(INT_MAX, 3) = 3 minBucket = [INT_MAX, 3, INT_MIN] i++ i = 1 loop for i < 4 1 < 4 true if nums[i] == maximum || nums[i] == minimum nums[1] == 9 || nums[1] == 1 6 == 9 || 6 == 1 false index = ((nums[i] - minimum) / range) = ((nums[1] - 1) / 2) = (6 - 1) / 2 = 2 maxBucket[index] = max(maxBucket[index], nums[i]) maxBucket[2] = max(maxBucket[2], nums[1]) = max(INT_MIN, 6) = 6 maxBucket = [INT_MIN, 3, 6] minBucket[index] = min(minBucket[index], nums[i]) minBucket[2] = max(minBucket[2], nums[1]) = max(INT_MAX, 6) = 6 minBucket = [INT_MAX, 3, 6] i++ i = 2 loop for i < 4 2 < 4 true if nums[i] == maximum || nums[i] == minimum nums[2] == 9 || nums[2] == 1 9 == 9 || 9 == 1 true continue i++ i = 3 loop for i < 4 3 < 4 true if nums[i] == maximum || nums[i] == minimum nums[3] == 9 || nums[3] == 1 1 == 9 || 1 == 1 true continue i++ i = 4 loop for i < 4 4 < 4 false Step 7: previousValue = minimum = 1 maximumGap = 0 Step 8: loop for i = 0; i < n - 1 0 < 4 - 1 0 < 3 true if minBucket[i] == INT_MAX minBucket[0] == INT_MAX true continue i++ i = 1 loop for i < n - 1 1 < 4 - 1 1 < 3 true if minBucket[i] == INT_MAX minBucket[1] == INT_MAX 3 == INT_MAX false maximumGap = max(maximumGap, minBucket[i] - previousValue) = max(0, minBucket[1] - previousValue) = max(0, 3 - 1) = max(0, 2) = 2 previousValue = maxBucket[i] = maxBucket[1] = 3 i++ i = 2 loop for i < n - 1 2 < 4 - 1 2 < 3 true if minBucket[i] == INT_MAX minBucket[1] == INT_MAX 6 == INT_MAX false maximumGap = max(maximumGap, minBucket[i] - previousValue) = max(2, minBucket[2] - previousValue) = max(2, 6 - 3) = max(2, 3) = 3 previousValue = maxBucket[i] = maxBucket[2] = 6 i++ i = 3 loop for i < n - 1 3 < 4 - 1 3 < 3 false Step 9: maximumGap = max(maximumGap, maximum - previousValue) = max(3, 9 - 6) = max(3, 3) = 3 Step 10: return maximumGap We return the answer as 3.
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
husseinkizz profile image
Hussein Kizz •

Hello thanks for the post, am just starting out on algorithmns and data structure, transitioning from frontend which I have done for sometime with javascript, like 4 or so, how do I get good at these, there's also an algorithmn am having a problem to solve if you could help!