My accepted java code, time O(n), space O(n)


  • 5
    S
    public int maximumGap(int[] num) {
            int n;
            if(num == null || (n = num.length) < 2) {
                return 0;
            }
            int min = num[0];
            int max = num[0];
            for(int i : num) {
               if(i > max) {
                   max = i;
               } else if(i < min) {
                   min = i;
               }
            }
            double dist = (double)(max-min)/(double)(n-1);
            int[] mins = new int[n-1];
            int[] maxs = new int[n-1];
            Arrays.fill(mins, -1);
            Arrays.fill(maxs, -1);
            for(int i : num) {
                int idx = (i == max ? n-2 : (int) ((i-min)/dist));
                if(mins[idx] == -1 || i < mins[idx]) {
                    mins[idx] = i;
                }
                if(maxs[idx] == -1 || i > maxs[idx]) {
                    maxs[idx] = i;
                }
            }
            int prevMax = maxs[0];
            int maxGap = maxs[0]-mins[0];
            for(int i = 1; i < n-1; i++) {
                if(mins[i] == -1) {
                    continue;
                }
                int gap = mins[i] - prevMax;
                if(gap > maxGap) {
                    maxGap = gap;
                }
                prevMax = maxs[i];
            }
            return maxGap;
        }

  • 0
    B
    class Solution {
    public:
    int maximumGap(vector<int> &num) {
        if (num.size()<2) return 0;
        
        int max = *max_element(num.begin(), num.end());
        int min = *min_element(num.begin(), num.end());
        int n = num.size();
        vector<int> max_idx(n, -1);
        vector<int> min_idx(n, -1);
        
        for (int i=0; i<n; ++i) {
            int idx = ((double) (num[i]-min) * (n-1)) / (max-min);
            if (num[i] > max_idx[idx]) max_idx[idx] = num[i];
            if (num[i] < min_idx[idx] || min_idx[idx] == -1) min_idx[idx] = num[i];
        }
        
        int max_gap = 1;
        int i=0, j=1;
        while (i<n && j<n) {
            while (j<n && min_idx[j] == -1) ++j;
            if (j == n) break;
            if (min_idx[j] - max_idx[i] > max_gap)
                max_gap = min_idx[j] - max_idx[i];
            i = j;
            j = j+1;
        }
        
        
        return max_gap;
    }
    };
    

    This is a short C++ version.


  • 2
    A

    I guess it is not quite easy to see what is going on in the code. It takes me some time to figure out, to benefit future viewers, I will just write my understanding here. The idea is to split the range [min, max] evenly int n-1 intervals. The interval length would be (max - min)/(n-1). According to the pigeon hole principle, the max range cannot be smaller than (max - min)/(n-1). Which means if there are two numbers generates the max difference, they must be in different intervals. Then we just need to compute the max difference between successive elements that lies in adjacent intervals. To do that, we just need to record min and max value for each interval.


  • 0
    C

    Very nice explanations, thanks adamlhh


  • 0
    S

    Thank you for your explanations, i just can not understand this question's intention at first.


  • 0
    S

    thanks adamlhh for the explanation.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.