Skip to content

Maximum Width Ramp⚓︎

Link

Description⚓︎

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 * 10^4
  • 0 <= nums[i] <= 5 * 10^4

Solution⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        stack<int> stk;
        int n = nums.size();
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (stk.empty() || nums[stk.top()] > nums[i])
                stk.push(i);
        }

        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && nums[i] >= nums[stk.top()]) {
                res = max(i - stk.top(), res);
                stk.pop();
            }
        }

        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).

The algorithm can be broken down into the following steps:

  1. Initialization: Use a stack to keep track of indices. The stack will help us efficiently find the leftmost index for a potential ramp as we scan through the array from right to left.

  2. Creating a Monotonic Stack:

    • Iterate through the array from left to right.
    • For each element, if the stack is empty or the current element is less than or equal to the element at the top of the stack (comparing the values in the array at those indices), push the current index onto the stack. This process builds a stack that maintains indices of elements in non-increasing order. The purpose is to potentially use these indices as the starting points (left side) of ramps.

  3. Finding the Maximum Width Ramp:

    • Iterate through the array from right to left. For each element during this iteration, we're considering it as the right end of a potential ramp.
    • While the stack is not empty and the current element is greater than or equal to the element at the index on the top of the stack (indicating a valid ramp), calculate the width of the ramp (current index - top of the stack) and update the maximum width if necessary.
    • Pop the top of the stack. This step is valid because if the current element forms a ramp with the top of the stack, it can also form ramps with elements before the top (due to the non-increasing order maintained in the stack), potentially finding a wider ramp as we continue.

A monotonic stack is used in this solution for several reasons:

  1. Efficiency in Identifying Potential Start Points: By maintaining a stack of indices where the array elements are in non-increasing order, we effectively mark potential start points of ramps. This ordering ensures that if an element can serve as the right end of a ramp with a certain start point, it can also serve as the right end for all previous start points in the stack, allowing us to efficiently find the maximum width.

  2. Simplifying the Search for Ramps: The non-increasing order of elements corresponding to the indices in the stack simplifies the logic for checking potential ramps. We only need to consider the current element (as the end of a ramp) and indices in the stack (as potential starts). This greatly reduces the complexity compared to other approaches that might require nested loops.

  3. Optimization: By iterating from right to left in the second part and using the stack's ordering property, we ensure that once an index is no longer useful (cannot form a wider ramp than already found), it is removed from consideration. This optimization prevents unnecessary comparisons and updates, contributing to the overall efficiency of the algorithm.