962. Maximum Width Ramp

How to solve Maximum Width Ramp (LeetCode 962): the approach in brief

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

Pattern

Maximum Width Ramp is a Stack Patterns problem, in the Monotonic Stack subpattern. The pattern covers parentheses matching, monotonic stack, histogram, and expression evaluation

Master monotonic stack for next greater element, daily temperatures, and stock span problems.

Approach outline

1. Consider using a data structure that helps you efficiently track indices where the array values are in a certain order, like a stack.
2. Try building a monotonic stack that stores indices of nums in increasing order based on their values to identify potential starting points for ramps.
3. Once you have the stack, iterate through the array from the end to the beginning to find the farthest index j where nums[j] is greater than or equal to nums[i] from the stack.

Complexity

The reference solution runs in O(n) time and O(n) space.

Asked at

Maximum Width Ramp has been reported in interviews at Facebook.