962. Maximum Width Ramp — step by step approach

3 min readApr 7, 2021

Question link: here

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i.

Find the maximum width of a ramp in A. If one doesn't exist, return 0.

Example 1:

Input: [6,0,8,2,1,5]
Output: 4
Explanation: 
The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Let's see how we can deal with this question. First, we will go with the very first logic that comes to mind and then we will see if we can make it better without consulting the solution provided in the discussion.

Initial Approach:

Use 2 for loops and calculate the ramp distance by checking both the arrays.

Something like this:

public static int maxWidthRamp(int[] A) {
    int length=0;
    int max=0;
    for (int i = 0; i < A.length; i++) {
        length=0;
        for (int j = i; j < A.length; j++) {
            if(A[j]>=A[i]){
                length=j-i;
            }
        }
        if(max<length){
            max=length;
        }
    }
    return max;
}

Works fine but the time limit is exceeded.

So, now we need to come up with a different approach. Let's see what can we do.

One thing that we can do is skip checking further if the longest length calculated is greater than the remaining array to check.

For example, if we know already that the longest chain so far is 6 and the remaining array length to check is 5, we need not continue. So I added that check.

if(max>A.length-i){
    break;
}

here is the full code and the results after that.

public static int maxWidthRamp(int[] A) {
    int length=0;
    int max=0;
    for (int i = 0; i < A.length; i++) {
        length=0;
        if(max>A.length-i){
            break;
        }
        for (int j = i+1; j < A.length; j++) {
            if(A[j]>=A[i]){
                length=j-i;
            }else{
                System.out.println(A[i]+" "+A[j]);
                break;
            }
        }
        if(max<length){
            max=length;
        }
    }
    return max;
}

After submitting it, we can check the solution provided by Leetcode to see where we could have improved.

Solution provided by LeetCode

class Solution {
    public int maxWidthRamp(int[] A) {
        int N = A.length;
        Integer[] B = new Integer[N];
        for (int i = 0; i < N; ++i)
            B[i] = i;

        Arrays.sort(B, (i, j) -> ((Integer) A[i]).compareTo(A[j]));

        int ans = 0;
        int m = N;
        for (int i: B) {
            ans = Math.max(ans, i - m);
            m = Math.min(m, i);
        }

        return ans;
    }
}

Well it sucks.

For all elements like A[i] = v, let's write the indices i in sorted order of their values v. For example with A[0] = 7, A[1] = 2, A[2] = 5, A[3] = 4, we can write the order of indices i=1, i=3, i=2, i=0.

Then, whenever we write an index i, we know there was a ramp of width i - min(indexes_previously_written) (if this quantity is positive). We can keep track of the minimum of all indexes previously written as m.

962. Maximum Width Ramp — step by step approach

Written by Noobnoob