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

Caesars Casino Review (2021) - Get $10 Free with No Deposit

ReplyDeleteCaesars 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.