Maximum Width Ramp LeetCode Solution - The Coding Shala

Last Updated: 26-Jan-2021

Home >> LeetCode >> Maximum Width Ramp

 In this post, we will learn how to solve LeetCode's Maximum Width Ramp Problem and will implement its solution in Java.

Maximum Width Ramp Problem

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.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1]

Output: 7

Explanation: 

The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

Practice this problem on LeetCode(Click Here).

Maximum Width Ramp Java Solution

Approach 1

Brute Force Solution.

Note: This might give you a time limit error.

Java Program: 

class Solution {
    public int maxWidthRamp(int[] A) {
        int max_width = 0;
        for(int i=0; i<A.length; i++){
            for(int j= A.length-1; j>i; j--){
                if(A[j]>=A[i]){
                    max_width = Math.max(max_width, j-i);
                    break;
                }
            }
        }
        return max_width;
    }
}

Approach 2

Using Stack. 

Time Complexity: O(N log N).

Space Complexity: O(N).

Java Program: 

class Solution {
    public int maxWidthRamp(int[] A) {
        //using stack
        Stack<Integer> st = new Stack<Integer>();
        st.push(0);
        for(int i=1; i<A.length; i++){
            if(A[i]<A[st.peek()]){
                st.push(i);
            }
        }
        
        int len = 0;
        for(int i = A.length-1; i>len ; i--){
            while(!st.empty() && A[st.peek()] <= A[i]){
                len = Math.max(len, i-st.pop());
            }
        }
        return len;
    }
}

Other Posts You May Like

• LeetCode - Sort Array By Parity
• LeetCode - Valid Boomerang
• LeetCode - Detect Capital
• LeetCode - Destination City
• LeetCode - Sifting Letters

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.