962. Maximum Width Ramp

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

Approach 01:

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        int maxRampWidth = 0;
        stack<int> indexStack;

        // First pass: find the indices of decreasing elements
        for (int i = 0; i < nums.size(); ++i) {
            if (indexStack.empty() || nums[i] < nums[indexStack.top()]) {
                indexStack.push(i);
            }
        }

        // Second pass: check for the maximum ramp width
        for (int i = nums.size() - 1; i > maxRampWidth; --i) {
            while (!indexStack.empty() && nums[i] >= nums[indexStack.top()]) {
                maxRampWidth = max(maxRampWidth, i - indexStack.top());
                indexStack.pop();
            }
        }

        return maxRampWidth;
    }
};

class Solution:
    def maxWidthRamp(self, nums):
        maxRampWidth = 0
        indexStack = []

        # First pass: find the indices of decreasing elements
        for i, num in enumerate(nums):
            if not indexStack or num < nums[indexStack[-1]]:
                indexStack.append(i)

        # Second pass: check for the maximum ramp width
        for i in range(len(nums) - 1, maxRampWidth, -1):
            while indexStack and nums[i] >= nums[indexStack[-1]]:
                maxRampWidth = max(maxRampWidth, i - indexStack.pop())

        return maxRampWidth

Time Complexity

• First pass (building the stack):

  The function iterates through the input vector once to find indices of decreasing elements and pushes them onto a stack. This takes \(O(n)\), where \(n\) is the size of the input vector.

• Second pass (finding maximum ramp width):

  The function iterates through the input vector a second time, starting from the end, to find the maximum ramp width by popping from the stack. This also takes \(O(n)\), as each element is processed at most once during the second pass.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the input vector, since both passes together take linear time.

Space Complexity

• Auxiliary Space:

  The function uses a stack to store the indices of decreasing elements. In the worst case, where all elements in the array are decreasing, the stack will store \(n\) elements. Thus, the space complexity is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the size of the input vector, due to the space required by the stack.