SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is to find the maximum difference between the successive elements in the sorted form of an array. This is known as the maximum gap problem. Given an unsorted array nums, you need to return the maximum difference between the successive elements after sorting the array. The solution must run in linear time O(n) and use only linear extra space O(n).

Intuition

A direct approach would involve sorting the array and then finding the maximum difference between successive elements. However, this would result in a time complexity of O(n log n). To achieve O(n) complexity, we can use a bucket-based approach, inspired by the pigeonhole principle. The idea is that if we divide the range of possible values into several buckets, the maximum gap will either be found between the highest value in one bucket and the lowest value in the next bucket or within a single bucket itself.

Approach

1. Initial Checks:

   • If the array has fewer than two elements, return 0 as no gap exists.

2. Determine Range and Bucket Size:

   • Calculate the maximum (hi) and minimum (lo) values in the array.
   • Determine the bucket size bsize by dividing the range (hi - lo) by the number of gaps (len(nums) - 1).
   • Create buckets to distribute the elements. The number of buckets will be (hi - lo) / bsize + 1.

3. Bucket Population:

   • Place each number into the appropriate bucket based on its value.

4. Calculate Maximum Gap:

   • Traverse through the buckets to calculate the maximum gap. The gap is the difference between the minimum value in the current bucket and the maximum value in the previous bucket.

5. Return Result:

   • Return the maximum gap found during the traversal.

Complexity

Time Complexity:

O(n). The array is traversed a few times, and each operation (like placing in buckets and calculating max/min) is constant time.

Space Complexity:

O(n). Extra space is used for the buckets, but the total number of buckets and the elements within them will not exceed O(n).

Code

C++

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) return 0;

        int hi = 0, lo = INT_MAX, ans = 0;
        for (int n : nums) {
            hi = max(hi, n);
            lo = min(lo, n);
        }

        int bsize = max(1, (hi - lo) / (int(nums.size()) - 1));
        int numBuckets = (hi - lo) / bsize + 1;
        vector<vector<int>> buckets(numBuckets);

        for (int n : nums) {
            int idx = (n - lo) / bsize;
            buckets[idx].push_back(n);
        }

        int currhi = 0;
        for (auto& b : buckets) {
            if (b.empty()) continue;
            int prevhi = currhi ? currhi : b[0], currlo = b[0];

            for (int n : b) {
                currhi = max(currhi, n);
                currlo = min(currlo, n);
            }

            ans = max(ans, currlo - prevhi);
        }

        return ans;
    }
};

Python

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0

        hi, lo, ans = max(nums), min(nums), 0
        bsize = max(1, (hi - lo) // (len(nums) - 1))
        buckets = [[] for _ in range((hi - lo) // bsize + 1)]

        for n in nums:
            idx = (n - lo) // bsize
            buckets[idx].append(n)

        currhi = 0
        for b in buckets:
            if not b:
                continue
            prevhi = currhi if currhi else b[0]
            currlo = min(b)
            currhi = max(b)

            ans = max(ans, currlo - prevhi)

        return ans

Java

class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;

        int hi = 0, lo = Integer.MAX_VALUE, ans = 0;
        for (int n : nums) {
            hi = Math.max(hi, n);
            lo = Math.min(lo, n);
        }

        int bsize = Math.max(1, (hi - lo) / (nums.length - 1));
        int numBuckets = (hi - lo) / bsize + 1;
        List<List<Integer>> buckets = new ArrayList<>(numBuckets);
        for (int i = 0; i < numBuckets; i++) {
            buckets.add(new ArrayList<>());
        }

        for (int n : nums) {
            int idx = (n - lo) / bsize;
            buckets.get(idx).add(n);
        }

        int currhi = 0;
        for (List<Integer> b : buckets) {
            if (b.isEmpty()) continue;
            int prevhi = currhi != 0 ? currhi : b.get(0), currlo = b.get(0);

            for (int n : b) {
                currhi = Math.max(currhi, n);
                currlo = Math.min(currlo, n);
            }

            ans = Math.max(ans, currlo - prevhi);
        }

        return ans;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function (nums) {

    if (nums.length < 2) return 0
    let hi = 0, lo = 2e9, ans = 0
    for (let n of nums)

        hi = Math.max(hi, n), lo = Math.min(lo, n)
    let bsize = ~~((hi - lo) / (nums.length - 1)) || 1,
        buckets = Array.from({ length: ~~((hi - lo) / bsize) + 1 }, () => [])

    for (let n of nums)
        buckets[~~((n - lo) / bsize)].push(n)
    let currhi = 0

    for (let b of buckets) {
        if (!b.length) continue
        let prevhi = currhi || b[0], currlo = b[0]
        
        for (let n of b)
            currhi = Math.max(currhi, n), currlo = Math.min(currlo, n)
        ans = Math.max(ans, currlo - prevhi)
    }
    return ans
};