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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

  1. Caesars Casino Review (2021) - Get $10 Free with No Deposit
    Caesars Casino 출장마사지 Review · 1등 사이트 1. casinosites.one Claim mens titanium wedding bands your $10 free bonus and receive up to $20 in casino https://septcasino.com/review/merit-casino/ credits (30 Free Spins) · 2. Play Slots at Caesars Casino.

    ReplyDelete

Post a Comment

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Single Number 3 LeetCode Solution - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Java Method Overloading - The Coding Shala