# 164. 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.
### Solution
Approach 1: Sorting.
Approach 2: Bucket sort.
Approach 3: Radix sort.
### Code (Python)
Approach 1:
```python
Approach 2:
# Code (C++)
Approach 1:
// Sorting.
class Solution {
public:
int maximumGap(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int maxGap = 0;
for (int i = 1; i < nums.size(); ++i)
{
maxGap = std::max(maxGap, nums[i] - nums[i-1]);
}
return maxGap;
}
};
Approach 2:
// Bucket sort.
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2)
return 0;
int max = nums[0];
int min = nums[0];
for (int i = 1; i < n; ++i)
{
max = std::max(max, nums[i]);
min = std::min(min, nums[i]);
}
vector<int> bucketMax(n, min-1);
vector<int> bucketMin(n, max+1);
int interval = (max - min + 1) / n;
if (interval == 0 || (max - min + 1) % n != 0)
interval++;
for (int i = 0; i < n; ++i)
{
int id = (nums[i] - min) / interval;
bucketMax[id] = std::max(bucketMax[id], nums[i]);
bucketMin[id] = std::min(bucketMin[id], nums[i]);
}
int maxGap = 0;
int prevMax = bucketMax[0];
for (int i = 1; i < n; ++i)
{
if (bucketMin[i] <= max)
{
maxGap = std::max(maxGap, bucketMin[i] - prevMax);
prevMax = bucketMax[i];
}
}
return maxGap;
}
};
Approach 3:
// radix sort
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2)
return 0;
for (int bit = 0; bit < 32; ++bit) {
std::stable_partition(nums.begin(), nums.end(),
[bit](int a) {
return !(a & (1 << bit));
});
}
int maxGap = -1;
for (int i = 1; i < n; ++i) {
maxGap = std::max(maxGap, nums[i] - nums[i-1]);
}
return maxGap;
}
};