## DEV Community

Posted on • Originally published at alkeshghorpade.me

# Maximum Gap

## 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.
``````

Example 2:

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

Constraints:

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

### 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;
}
``````

#### 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.
``````

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
``````

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;
}
};
``````

#### 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
}
``````

#### 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;
};
``````

#### 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.
``````