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.

Notice

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Have you met this question in a real interview?

Yes

Example

Given[1, 9, 2, 5], the sorted form of it is[1, 2, 5, 9], the maximum gap is between5and9=4.

Challenge

Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.

name error
line 15 std::max works with variable name max 
line 32 not buckets.empty()
line 9 error not nums.empty() < 2
line 52 struct definition missing semicolon
line 18 needs to check max = min case in case len is equal to 0; runtime error

class Solution {
public:
    /**
     * @param nums: a vector of integers
     * @return: the maximum difference
     */
    int maximumGap(vector<int> nums) {
        // write your code here
        if (nums.size() < 2) {
            return 0;
        }
        int n = nums.size();
        int max = nums[0], min = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            max = std::max(max, nums[i]);
            min = std::min(min, nums[i]);
        }
        if (max == min) {
            return 0;
        }
        int len = static_cast<int>(std::ceil((max - min)*1.0/(n - 1)));
        int bucket_size = (max - min) / len + 1;
        vector<Bucket> buckets(bucket_size);
        for (auto num : nums) {
            int idx = (num - min) / len;
            buckets[idx].isEmpty = false;
            buckets[idx].min = std::min(num, buckets[idx].min);
            buckets[idx].max = std::max(num, buckets[idx].max);
        }
        int maxGap = 0, preMax = buckets[0].max;
        for (int i = 1; i < buckets.size(); ++i) {
            if (buckets[i].isEmpty) {
                continue;
            }
            maxGap = std::max(maxGap, buckets[i].min - preMax);
            preMax = buckets[i].max;
        }

        return maxGap;
    }

private :
    struct Bucket {
        Bucket() {
            min = INT_MAX;
            max = INT_MIN;
            isEmpty = true;
        }
        int min;
        int max;
        bool isEmpty;
    };
};