### 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 = 0 and A = 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 = 1 and A = 1.

## 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

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.