Use Average Gap to achieve O(n) run time (Java Solution)


  • 2
    S

    My idea comes from this: Since the question only allow O(n) run time, I cannot do sorting, (sorting takes at least O(n log n). I can only make use of the O(n) space. Considering the worst case, where the integers are spread by equal distance, like {1,3,5,7,9}. Then the maximum gap is the 2, change any integer in between will leads to larger gap.

    So I keep a gaps array which has equal gap distance and non-overlapping range. Like the example {1,3,5,7,9} become {[1,3),[3,5),[5,7),[7,9]}. Let me add some number into it without changing the minimum and maximum bound. {1,3,2,4,5,7,9}. Then, go through the num array, assign lower bound and upper bound for each gap.

    The example {1,3,2,4,5,7,9} has gaps

    [1,3) with lower bound = 1 and upper bound = 2;

    [3,5) with lower bound = 3 and upper bound = 4;

    [5,7) with lower bound = 5 and upper bound = 5;

    [7,9] with lower bound = 7 and upper bound = 9;

    Then go through the gaps array once, you'll be able to find out the maximum gap.

    public class Solution {
        public int maximumGap(int[] num) {
            int maxGap = 0;
            
            // edge case
            if(num.length < 2){return maxGap;}
            
            // get maximum and minimum
            int min = num[0];
            int max = num[0];
            for(int i = 0;i < num.length;i++){
                if(num[i] < min)
                    min = num[i];
                if(num[i] > max)
                    max = num[i];
            }
            
            // divide into identical gaps
            Gap[] gaps = new Gap[num.length-1];
            boolean[] Engaged = new boolean[num.length-1];
            double gap = (double)(max-min)/(double)(num.length-1);
            for(int i = 0;i < gaps.length;i++)
                Engaged[Math.min((int)Math.floor((double)(num[i]-min)/gap),gaps.length-1)] = true;
                
            // assign maximum and minimum for each gap
            for(int i = 0;i < gaps.length;i++)
                gaps[i] = new Gap();
            for(int i = 0;i < num.length;i++){
                int index = (int)Math.floor((double)(num[i]-min)/gap);
                index = Math.min(index,gaps.length-1);
                
                // lower bound
                if(gaps[index].low == -1)
                    gaps[index].low = num[i];
                else
                    gaps[index].low = Math.min(gaps[index].low, num[i]);
                        
                // upper bound
                if(gaps[index].high == -1)
                    gaps[index].high = num[i];
                else
                    gaps[index].high = Math.max(gaps[index].high, num[i]);
            }
            
            // find maximum gap
            for(int i = 0;i < gaps.length;i++){
                if(Engaged[i]){
                    // check its inner gap
                    maxGap = Math.max(gaps[i].high-gaps[i].low, maxGap);
                    
                    // lower all the way
                    int j = i;
                    while(--j >= 0){
                        if(Engaged[j])
                            break;
                    }
                    if(j >= 0)
                        maxGap = Math.max(gaps[i].low - gaps[j].high,maxGap);
                        
                    // upper all the way
                    j = i;
                    while(++j < num.length-2){
                        if(Engaged[j])
                            break;
                    }
                    if(j < gaps.length)
                        maxGap = Math.max(gaps[j].low - gaps[i].high, maxGap);
                }
            }
            
            return maxGap;
        }
        
        class Gap{
            int low;
            int high;
            Gap(){
                low = -1;
                high = -1;
            }
            Gap(int x,int y){
                low = x;
                high = y;
            }
        }
    }

  • 0
    M

    I think it can be considered as bucket sort.


  • 6
    C

    Same solution to OP.
    For more detailed proof, please check http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf

    public class Solution {
    public int maximumGap(int[] num) {
        if (num.length <= 1) return 0;
        if (num.length == 2) return num[0] > num[1] ? (num[0] - num[1]) : (num[1] - num[0]);
        // array length must be larger than 2
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < num.length; i++) {
            if (num[i] > max) max = num[i];
            if (num[i] < min) min = num[i];
        }
        double bucketDelta = ((double)(max - min)) / (num.length - 1);
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < num.length - 1; i++)
            buckets.add(new ArrayList<Integer>());
            
        for (int i = 0; i < num.length; i++) {
            if (num[i] > min && num[i] < max)
                buckets.get((int)((num[i] - min) / bucketDelta)).add(num[i]);
        }
        int prevMax = min;
        ArrayList<Integer> buck;
        int idx;
        for (idx = 0; idx < num.length - 1; idx++) {
            buck = buckets.get(idx);
            if (buck.size() == 0) continue;
            for (int i : buck)
                if (i > prevMax) prevMax = i;
            break;
        }
        
        int currMin = prevMax, currMax = prevMax;   
        int maxDiff = 0, diff;
        for (++idx; idx < num.length - 1; idx++) {
            buck = buckets.get(idx);
            if (buck.size() == 0) continue;
            currMax = Integer.MIN_VALUE;
            currMin = Integer.MAX_VALUE;
            for (int j : buck) {
                if (j > currMax) currMax = j;
                if (j < currMin) currMin = j;  
            }
            diff = currMin - prevMax;
            if (diff > maxDiff) maxDiff = diff;
            prevMax = currMax;
        }
        return maxDiff > (max - prevMax) ? maxDiff : max - prevMax;
    }}

  • 0
    D

    good explanation on the link.


Log in to reply
 

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