# Maximum Width Ramp
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-width-ramp)
Canonical: https://scaleengineer.com/dsa/problems/maximum-width-ramp
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Zepto](https://scaleengineer.com/companies/zepto)
---
## Problem
A **ramp** in an integer array `nums` is a pair `(i, j)` for which `i < j` and `nums[i] <= nums[j]`. The **width** of such a ramp is `j - i`.

Given an integer array `nums`, return _the maximum width of a **ramp** in_ `nums`. If there is no **ramp** in `nums`, return `0`.

**Example 1:**

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

**Example 2:**

**Input:** nums = [9,8,1,0,1,9,4,0,4,1]
**Output:** 7
**Explanation:** The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.

**Constraints:**

* `2 <= nums.length <= 5 * 104`
* `0 <= nums[i] <= 5 * 104`

# Approaches
## Brute Force
This approach exhaustively checks every possible pair of indices `(i, j)` where `i < j`. For each pair, it verifies if it forms a ramp (`nums[i] <= nums[j]`) and, if so, calculates its width `j - i`. The maximum width found across all pairs is the result.
**Time:** O(N^2), where N is the length of `nums`. The nested loops lead to a quadratic number of comparisons. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.
### Explanation
The brute-force solution is the most straightforward way to solve the problem. We simply follow the definition of a ramp and its width. We iterate through all possible pairs of indices `(i, j)` such that `i` comes before `j`. For every such pair, we check if `nums[i]` is less than or equal to `nums[j]`. If this condition holds, we have found a valid ramp. We then calculate its width, which is `j - i`, and compare it with the maximum width found so far, updating it if the new width is larger. This process is repeated until all possible pairs have been considered.

```java
class Solution {
    public int maxWidthRamp(int[] nums) {
        int n = nums.length;
        int maxWidth = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] <= nums[j]) {
                    maxWidth = Math.max(maxWidth, j - i);
                }
            }
        }
        return maxWidth;
    }
}
```
### Algorithm
- Initialize a variable `maxWidth` to 0.
- Use a nested loop. The outer loop iterates through each possible starting index `i` from `0` to `n-2`.
- The inner loop iterates through each possible ending index `j` from `i + 1` to `n-1`.
- Inside the inner loop, check the ramp condition: `nums[i] <= nums[j]`.
- If the condition is true, it means we've found a valid ramp. We calculate its width `j - i` and update `maxWidth` to be the maximum of its current value and the new width.
- After checking all pairs, `maxWidth` will hold the maximum width of any ramp in the array.

## Sorting with Index Preservation
This approach improves upon the brute-force method by sorting. The key idea is to not sort the array values directly, but to sort their original indices based on the values they point to. After sorting, we can efficiently find the maximum ramp width in a single pass.
**Time:** O(N log N), dominated by the sorting step. The subsequent scan is O(N). · **Space:** O(N) to store the array of indices for sorting.
**Pros:** Significantly more efficient than brute force, with O(N log N) time complexity.; Passes the time limits for the given constraints.
**Cons:** Requires extra space proportional to the input size.; Not the most optimal solution in terms of time complexity.
### Explanation
To maximize `j - i` for a ramp, for any given `j`, we need to find an `i < j` with `nums[i] <= nums[j]` such that `i` is as small as possible. We can reframe the problem by processing the numbers in increasing order of their values. By doing so, for any number `nums[j]`, any number `nums[i]` processed before it will satisfy `nums[i] <= nums[j]`. 

We can implement this by creating pairs of `(value, index)` and sorting them by value. Then, we iterate through the sorted list. To maximize `j - i`, we need to pair the current `index_j` with the smallest `index_i` seen so far. We can maintain a variable `min_index` that tracks the minimum index encountered as we iterate. For each element, we calculate the potential width using its index and `min_index`, update our `maxWidth`, and then update `min_index` with the current element's index if it's smaller.

```java
import java.util.Arrays;

class Solution {
    public int maxWidthRamp(int[] nums) {
        int n = nums.length;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }

        // Sort indices based on the values in nums
        Arrays.sort(indices, (a, b) -> Integer.compare(nums[a], nums[b]));

        int maxWidth = 0;
        int minIndex = n;
        for (int index : indices) {
            maxWidth = Math.max(maxWidth, index - minIndex);
            minIndex = Math.min(minIndex, index);
        }
        return maxWidth;
    }
}
```
### Algorithm
- Create an array or list of indices from `0` to `n-1`.
- Sort this index array based on the corresponding values in `nums`. If values are equal, the relative order of indices doesn't matter for correctness.
- Initialize `maxWidth = 0` and `minIndex` to a large value (e.g., `n`).
- Iterate through the sorted indices array. For each `index`:
  - Calculate a potential width: `width = index - minIndex`.
  - Update `maxWidth = max(maxWidth, width)`.
  - Update `minIndex = min(minIndex, index)` to keep track of the smallest original index seen so far.
- Return `maxWidth`.

## Monotonic Stack
This is the most optimal approach with linear time complexity. It uses a monotonic stack to identify potential starting points of a ramp in one pass, and then finds the maximum width by scanning from the end of the array in a second pass.
**Time:** O(N). Each index is pushed and popped from the stack at most once. Both passes are linear scans of the array. · **Space:** O(N) in the worst case for the stack (e.g., when the input array is strictly decreasing).
**Pros:** Most efficient solution with linear time complexity.; Guaranteed to pass within time limits for large inputs.
**Cons:** Can be less intuitive to understand compared to sorting or brute-force approaches.; Requires extra space for the stack.
### Explanation
The core idea is to efficiently find the best candidates for the start of a ramp, `i`. A good candidate `i` should have a small value `nums[i]`. If we have two indices `i1 < i2` with `nums[i1] <= nums[i2]`, `i1` is always a better or equal candidate than `i2` for starting a ramp. This implies that the best candidates for `i` will have values that form a strictly decreasing sequence.

**Pass 1: Build a monotonic stack.** We iterate through the array and build a stack of indices. We only push an index `i` onto the stack if `nums[i]` is smaller than the value at the index on top of the stack. This results in a stack where indices are increasing and their corresponding values in `nums` are strictly decreasing. These are our optimal candidates for the start of a ramp.

**Pass 2: Find the maximum width.** We iterate backwards from the end of the array (`j` from `n-1` to `0`). For each `j`, we check if `nums[j]` can form a ramp with the index `i` at the top of the stack (`nums[i] <= nums[j]`). If it can, we've found a valid ramp `(i, j)`. We calculate the width `j - i`, update our `maxWidth`, and pop `i` from the stack. We pop because we've found the best possible `j` for this `i` (since we're iterating `j` backwards). We continue this process with the new top of the stack until the condition is no longer met or the stack is empty.

```java
import java.util.Stack;

class Solution {
    public int maxWidthRamp(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int n = nums.length;

        // Pass 1: Build a stack of candidate indices for the start of the ramp.
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty() || nums[stack.peek()] > nums[i]) {
                stack.push(i);
            }
        }

        int maxWidth = 0;
        // Pass 2: Iterate from the end to find the maximum width.
        for (int j = n - 1; j >= 0; j--) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[j]) {
                int i = stack.pop();
                maxWidth = Math.max(maxWidth, j - i);
            }
        }
        return maxWidth;
    }
}
```
### Algorithm
- Initialize an empty stack.
- **First Pass (Build Candidates):** Iterate `i` from `0` to `n-1`. If the stack is empty or `nums[i]` is less than `nums` at the index on top of the stack, push `i` onto the stack. This creates a stack of indices corresponding to a monotonically decreasing sequence of values.
- Initialize `maxWidth = 0`.
- **Second Pass (Find Ramps):** Iterate `j` from `n-1` down to `0`.
  - While the stack is not empty and `nums` at the index on top of the stack (`i`) is less than or equal to `nums[j]`:
    - We have a valid ramp `(i, j)`. Update `maxWidth = max(maxWidth, j - i)`.
    - Pop the index `i` from the stack, as it has been matched with its best possible `j`.
- Return `maxWidth`.

# Solutions
### Java

```java
class Solution {
public
  int maxWidthRamp(int[] nums) {
    int n = nums.length;
    Deque<Integer> stk = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      if (stk.isEmpty() || nums[stk.peek()] > nums[i]) {
        stk.push(i);
      }
    }
    int ans = 0;
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
        ans = Math.max(ans, i - stk.pop());
      }
      if (stk.isEmpty()) {
        break;
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
function maxWidthRamp ( nums ) { let [ ans , n ] = [ 0 , nums . length ]; const stk = []; for ( let i = 0 ; i < n - 1 ; i ++ ) { if ( stk . length === 0 || nums [ stk . at ( - 1 )] > nums [ i ]) { stk . push ( i ); } } for ( let i = n - 1 ; i >= 0 ; i -- ) { while ( stk . length && nums [ stk . at ( - 1 )] <= nums [ i ]) { ans = Math . max ( ans , i - stk . pop ()); } if ( stk . length === 0 ) break ; } return ans ; }
```

### CPP

```cpp
class Solution {
public:
  int maxWidthRamp(vector<int> &nums) {
    int n = nums.size();
    stack<int> stk;
    for (int i = 0; i < n; ++i) {
      if (stk.empty() || nums[stk.top()] > nums[i])
        stk.push(i);
    }
    int ans = 0;
    for (int i = n - 1; i; --i) {
      while (!stk.empty() && nums[stk.top()] <= nums[i]) {
        ans = max(ans, i - stk.top());
        stk.pop();
      }
      if (stk.empty())
        break;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int: stk = [] for i, v in enumerate(nums): if not stk or nums[stk[- 1]] > v: stk . append(i) ans = 0 for i in range(len(nums) - 1, - 1, - 1): while stk and nums[stk[- 1]] <= nums[i]: ans = max(ans, i - stk . pop()) if not stk: break return ans

```