164. Maximum Gap
1. Description
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.
2. Example
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.
3. 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.
4. Solutions
My Accepted Solution
n = m_nums.size()
Time complexity: O($nlg_2n$)
Space complexity: O(1)
class Solution
{
public:
// int maximumGap(vector<int>& nums)
int maximumGap(vector<int> &m_nums)
{
sort(m_nums.begin(), m_nums.end());
int result = 0;
for(int i = 1; i < m_nums.size(); i++)
{
result = max(result, m_nums[i] - m_nums[i-1]);
}
return result;
}
};
4.1 Radix Sort
n = m_nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
private:
void radixSort(vector<int> &m_nums)
{
int maxValue = *max_element(m_nums.begin(), m_nums.end());
for(int leftMove = 0; leftMove < 32 && ((1 << leftMove) < maxValue); leftMove++) // 32 means the an integer has 32 bits
{
vector<int> oneBucket;
vector<int> zeroBucket;
int probe = 1 << leftMove;
for(int i = 0; i < m_nums.size(); i++)
{
if(m_nums[i] & probe)
oneBucket.push_back(m_nums[i]);
else
zeroBucket.push_back(m_nums[i]);
}
zeroBucket.insert(zeroBucket.end(), oneBucket.begin(), oneBucket.end());
m_nums = zeroBucket;
}
}
public:
// int maximumGap(vector<int>& nums)
int maximumGap(vector<int> &m_nums)
{
if(m_nums.size() < 2) return 0;
radixSort(m_nums);
int maxGap = 0;
for(int i = 1; i < m_nums.size(); i++)
maxGap = max(maxGap, m_nums[i] - m_nums[i-1]);
return maxGap;
}
};
4.2 Buckets and The Pigeonhole Principle
n = m_nums.size()
b is (max - min) / (n - 1), while max is the maximum of m_nums, min is the minimun of m_nums
Time complexity: O(n)
Space complexity: O(b)
// bucket
// we calculate the gap between buckets, it is max(1, (int)((maxValue-minValue) / (m_nums.size()-1)));
// then we could get the number of buckets, it is (maxValue - minValue) / bucketGap + 1;
// so, wo coule get the conclusion that the result is bigger than bucketGap
// that's because when the minimum result occurs, it is the case we have uniform width array, it is bucketGap
// so the result will not occur during the difference between a bucket, since this difference is less than bucketGap
// so, we coule get the conclusion that the result occurs at the max value of a bucket and min value of the next bucket
class Solution
{
private:
struct Bucket
{
bool used = false;
int max = INT_MIN;
int min = INT_MAX;
};
public:
// int maximumGap(vector<int>& nums)
int maximumGap(vector<int> &m_nums)
{
if(m_nums.size() < 2) return 0;
int maxValue = *max_element(m_nums.begin(), m_nums.end());
int minValue = *min_element(m_nums.begin(), m_nums.end());
int bucketGap = max(1, (int)((maxValue-minValue) / (m_nums.size()-1)));
int bucketCount = (maxValue - minValue) / bucketGap + 1;
vector<Bucket> buckets(bucketCount);
for(int i = 0; i < m_nums.size(); i++)
{
int bucketIndex = (m_nums[i] - minValue) / bucketGap;
buckets[bucketIndex].used = true;
buckets[bucketIndex].min = min(buckets[bucketIndex].min, m_nums[i]);
buckets[bucketIndex].max = max(buckets[bucketIndex].max, m_nums[i]);
}
int maxGap = 0;
for(int i = 0, lastBucketMaxValue = maxValue; i < buckets.size(); i++)
{
if(buckets[i].used)
{
maxGap = max(maxGap, buckets[i].min - lastBucketMaxValue);
lastBucketMaxValue = buckets[i].max;
}
}
return maxGap;
}
};