Maximum Gap

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.

----------------------------------- good codes --------------------------------------------------------------

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;
        }
    }
}