164. Maximum Gap - cocoder39/coco39_LC GitHub Wiki

164. Maximum Gap

we are asked to solve it with O(n) time and O(n) memory. Hence we can try bucket sort.

  • There are sz - 1 gaps within [low, high]. suppose double len = (double)(high - low) / (sz - 1), then len should be less than max gap since len * (sz - 1) < high - low.
  • if the length of each bucket is len, then there should be (high - low) / len + 1 buckets, which is equal to sz
  • the gap between numbers within the same bucket is no more than len, thus cannot be max gap. Hence only numbers in different buckets can achieve max gap.
int maximumGap(vector<int>& nums) {
        int sz = nums.size();
        if (sz < 2) {
            return 0;
        }
        int low = nums[0], high = nums[0];
        for (auto num : nums) {
            low = min(low, num);
            high = max(high, num);
        }
        
        //guaranteed to be less than max gap, len * (sz - 1) <= high - low, 
        double len = (double)(high - low) / (sz - 1);  
        if (high == low) { //ensure len != 0
            return 0;
        }
        vector<int> lows(sz, INT_MAX); 
        vector<int> highs(sz, INT_MIN);
        for (auto num : nums) {
            int idx = (num - low) / len; 
            lows[idx] = min(lows[idx], num);
            highs[idx] = max(highs[idx], num);
        }
        
        int res = 0;
        int pre_high = low;
        for (int i = 0; i < lows.size(); i++) {
            if (lows[i] == INT_MAX) { //empty bucket
                continue;
            }
            res = max(res, lows[i] - pre_high);
            pre_high = highs[i];
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️