Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements.

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

For example, the following array
 3 5 1 2 9
After sort it becomes 1 2 3 5 9
The max gap is 9-5 = 4

class Solution {
public:
    int maximumGap(vector &num) {
        int mx = INT_MIN;
        int mn = INT_MAX;
        for(int i : num) {
            mx = max(mx, i);
            mn = min(mn, i);
        }
        
        // all element's are the same or there is less than 2 elements
        if (mx == mn || mx == INT_MIN) return 0;
        
        int n = num.size();
        int dist = (mx - mn + n - 1) / n;
        
        vector maxs(n, -1);
        vector mins(n, -1);
        
        for(int i : num) {
            int idx = (i-mn)/dist;
            maxs[idx] = maxs[idx] == -1 ? i : max(maxs[idx], i);
            mins[idx] = mins[idx] == -1 ? i : min(mins[idx], i);
        }
        
        int prevMX = mn;
        int ret = 0;
        for(int i = 0; i < n; i++)
        {
            if (mins[i] != -1) {
                ret = max(ret, mins[i]-prevMX);
                prevMX = maxs[i];
            }
        }
        
        return ret;
    }
};