Code Implementation

class Solution:
    def maxWidthRamp(self, nums):
        stack = []
        for i, num in enumerate(nums):
            if not stack or num < nums[stack[-1]]:
                stack.append(i)
        max_width = 0
        for j in reversed(range(len(nums))):
            while stack and nums[j] >= nums[stack[-1]]:
                i = stack.pop()
                max_width = max(max_width, j - i)
        return max_width
      

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        vector<int> stack;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (stack.empty() || nums[i] < nums[stack.back()]) {
                stack.push_back(i);
            }
        }
        int maxWidth = 0;
        for (int j = n - 1; j >= 0; --j) {
            while (!stack.empty() && nums[j] >= nums[stack.back()]) {
                maxWidth = max(maxWidth, j - stack.back());
                stack.pop_back();
            }
        }
        return maxWidth;
    }
};
      

class Solution {
    public int maxWidthRamp(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (stack.isEmpty() || nums[i] < nums[stack.peek()]) {
                stack.push(i);
            }
        }
        int maxWidth = 0;
        for (int j = n - 1; j >= 0; --j) {
            while (!stack.isEmpty() && nums[j] >= nums[stack.peek()]) {
                maxWidth = Math.max(maxWidth, j - stack.pop());
            }
        }
        return maxWidth;
    }
}
      

var maxWidthRamp = function(nums) {
    let stack = [];
    for (let i = 0; i < nums.length; ++i) {
        if (stack.length === 0 || nums[i] < nums[stack[stack.length - 1]]) {
            stack.push(i);
        }
    }
    let maxWidth = 0;
    for (let j = nums.length - 1; j >= 0; --j) {
        while (stack.length > 0 && nums[j] >= nums[stack[stack.length - 1]]) {
            maxWidth = Math.max(maxWidth, j - stack.pop());
        }
    }
    return maxWidth;
};
      

Problem Description

You are given an array of integers nums. A ramp in this array is a pair of indices (i, j) such that i < j and nums[i] <= nums[j].

The width of such a ramp is defined as j - i. Your goal is to find the maximum width ramp in the array—that is, the largest possible value of j - i for which nums[i] <= nums[j] and i < j.

• Each element of nums can be used at most once in a ramp.
• There is always at least one valid solution (since i < j is required, and the array has at least two elements).
• Indices must be distinct and i < j.

Input: nums (an array of integers)
Output: The maximum width of a ramp in nums.

Thought Process

At first glance, the most direct way to solve the problem is to check every possible pair of indices (i, j) where i < j and see if nums[i] <= nums[j]. For each valid pair, we compute j - i and keep track of the maximum. However, this brute-force approach requires checking all pairs, which leads to a time complexity of O(n²), making it too slow for large arrays.

To optimize, we need a way to avoid redundant comparisons and quickly identify, for each possible j, the smallest i such that nums[i] <= nums[j] and i < j. This naturally leads us to consider data structures that can efficiently track potential starting indices for ramps.

By thinking about the problem from the end of the array backward, and keeping track of indices where nums[i] is smaller than all previously seen values, we can efficiently find the widest ramp.

Solution Approach

The optimized solution uses a monotonic stack to keep track of candidate starting indices for ramps. Here's how the algorithm works step by step:

1. Build a Decreasing Stack:
   • Iterate through nums from left to right.
   • For each index i, if nums[i] is less than the value at the index on top of the stack (or the stack is empty), push i onto the stack.
   • This stack will store indices in strictly decreasing order of their values in nums. These are candidate starting points for ramps.
2. Scan from Right to Left:
   • Iterate through nums from right to left using index j.
   • For each j, while the stack is not empty and nums[j] >= nums[stack[-1]] (the value at the top of the stack), pop the index i from the stack and compute j - i. Update the maximum width if necessary.
   • This works because popping from the stack ensures we always consider the smallest possible i for each j.
3. Return the Maximum Width:
   • After processing all j, return the largest width found.

This approach is efficient because each index is pushed and popped at most once, leading to linear time complexity.

Example Walkthrough

Let's consider the input nums = [6, 0, 8, 2, 1, 5].

1. Build the Decreasing Stack:
   • i = 0: stack = [0] (6)
   • i = 1: 0 < 6, stack = [0, 1] (0)
   • i = 2: 8 > 0, do not push
   • i = 3: 2 > 0, do not push
   • i = 4: 1 > 0, do not push
   • i = 5: 5 > 0, do not push

   Final stack: [0, 1] (indices where nums is strictly decreasing from the left)

2. Scan from Right to Left:
   • j = 5: nums[5]=5, nums[1]=0. 5 >= 0, pop 1, width=5-1=4, maxWidth=4. Next, nums[0]=6, 5 < 6, stop.
   • j = 4: nums[4]=1, nums[0]=6, 1 < 6, stop.
   • j = 3: nums[3]=2, nums[0]=6, 2 < 6, stop.
   • j = 2: nums[2]=8, nums[0]=6, 8 >= 6, pop 0, width=2-0=2, maxWidth remains 4.
   • j = 1: stack empty, stop.
   • j = 0: stack empty, stop.
3. Result: The maximum width ramp is 4 (from index 1 to 5).

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²) because we check all pairs (i, j).
  • Space Complexity: O(1), as no extra space is needed beyond variables.
• Optimized (Monotonic Stack) approach:
  • Time Complexity: O(n) because each index is pushed and popped from the stack at most once.
  • Space Complexity: O(n) for the stack storing indices.

The optimized approach is much more efficient and suitable for large input sizes.

Summary

To solve the Maximum Width Ramp problem, we leverage a monotonic stack to efficiently find the widest ramp in linear time. The key insight is to track candidate starting indices where nums[i] is smaller than all previous values, and then scan from the end to match as many of these as possible with larger or equal values. This avoids redundant checks and makes the solution both elegant and performant.