Maximum Gap Problem


Description

LeetCode Problem 164.

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:

1
2
3
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:

1
2
3
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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int mn = INT_MAX, mx = INT_MIN;
        int n = nums.size();
        if (n < 2)
        	return 0;
        for (int i=0;i<n;++i) {
        	mn = min(nums[i], mn);
        	mx = max(nums[i], mx);
		}
		if (mx == mn)
			return 0;
		double bucket = (mx - mn + 0.0) / n; 
		vector<int> big(n, -1); 
		vector<int> small(n, -1);  
		for (int i=0;i<n;++i) {
			int index = (nums[i] - mn) / bucket;
			if (index >= n) 
				index = n - 1; 
			
			if (big[index] == -1) {
				big[index] = small[index] = nums[i];
			}
			else {
				big[index] = max(big[index], nums[i]);
				small[index] = min(small[index], nums[i]);
			}
		}
		int result = 0;
		int s = mn, b = mn;
		for (int i=0;i<n;++i) { 
			if (big[i] == -1)
				continue;
			result = max(small[i] - b, result); 
			s = small[i];
			b = big[i];
		}
		return result;
    }
};




Related Posts

Sum Of Subsequence Widths Problem

LeetCode 891. The width of a sequence is the difference...

Sort An Array Problem

LeetCode 912. Given an array of integers nums, sort the...

Smallest Range II Problem

LeetCode 910. You are given an integer array nums and...

Reordered Power Of 2 Problem

LeetCode 869. You are given an integer n. We reorder...

Reorder Data In Log Files Problem

LeetCode 937. You are given an array of logs. Each...

Minimum Increment To Make Array Unique Problem

LeetCode 945. You are given an integer array nums. In...