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