InterviewBit : Max Distance

[congr]

https://www.interviewbit.com/problems/max-distance/

[congr]

Interview correct answer/ TLE

public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int maximumGap(final int[] A) {
        int maxGap = -1;

        for (int i = 0; i<A.length; i++) {
            for (int j = i; j<A.length; j++) {
                if (A[i] <= A[j]) 
                    maxGap = Math.max(maxGap, j-i);
            }
        }

        return maxGap;
    }
}

[congr]

InterviewBit AC Score : 0 It's hard to make it O(NLogN). Sort a given array with pair (A[i], i), and then check the max gap. GreaterIndex and maxGap should be updated.

public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int maximumGap(final int[] A) {
        ArrayList<int[]> list = new ArrayList();
        for (int i = 0; i<A.length; i++) {
            list.add(new int[] {A[i], i});
        }

        Collections.sort(list, (o1, o2) -> o1[0] - o2[0]);

        int maxGap = 0;
        int greaterIndex = list.get(list.size()-1)[1];

        for (int i = list.size() - 2; i>=0; i-- ){
            int curIndex = list.get(i)[1];
            maxGap = Math.max (maxGap, greaterIndex - curIndex); //!!!
            greaterIndex = Math.max(greaterIndex, curIndex); //!!!
        }

        return maxGap;
    }
}