0164. Maximum Gap¶
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Example 1:
Input: [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: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.
Note:
- You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
- Try to solve it in linear time/space.
Analysis¶
Let's first split the array into multiple equal-size ranges, and the total number of ranges is n (the size of the input array).
3, 6, 9, 1
-> we have 4 numbers, so we will have four ranges
(] (] (] (]
Because we have n ranges, if we can know how big is each range, we can place each number to its correct range. For each range, we will keep a record of the maximum difference between a current number and the sorted number.
3, 6, 9, 1
-> Let's assume the size of each range is len
(a, a + len] (b, b + len] (c, c + len] (d, d + len]
To determine which range should each number be placed into, we use a math trick:
idx = \frac{x-a-1}{n-1}, where a is the minimum value or the starting value of our ranges.
Given this information, we can just find and compare the maximum difference across every two ranges. Now we have n numbers, and there are len - 1 numbers in each range. If we have a relatively small length of each range, the maximum difference cannot exist in each range, but across two successive ranges.
(n-1)(len-1) < Max - Min, which yield
(Max - Min + n - 2)/(n - 1) after rearrangement.
- Time: O(n)
- Space: O(n)
Code¶
class Solution {
public:
struct Range{
int min,max;
bool used;
Range() : min(INT_MAX), max(INT_MIN), used(false) {}
};
int maximumGap(vector<int>& nums) {
int n = nums.size();
int Max = INT_MIN, Min = INT_MAX;
for (int x : nums) {
Max = max(Max, x);
Min = min(Min, x);
}
if (n < 2 || Max == Min) return 0;
vector<Range> r(n-1);
// average size of each range to make sure
// global diff only exists in each range
// but not accross any two more more range
int len = (Max-Min+n-2)/(n-1);
for (int x : nums) {
if (x == Min) continue;
int idx = (x-Min-1)/len;
r[idx].min = min(r[idx].min,x);
r[idx].max = max(r[idx].max, x);
r[idx].used = true;
}
int res = 0;
for (int i = 0, last = Min; i < n - 1; ++i) {
if (r[i].used) {
res = max(res, r[i].min - last);
last = r[i].max;
}
}
return res;
}
};