Is Maximum Width Ramp easy or hard?

Maximum Width Ramp is classified as a Medium difficulty problem. The challenge comes from recognizing that brute force is too slow and that a monotonic stack can track optimal left candidates efficiently. Once the pattern is recognized, the implementation is straightforward.

How to solve Maximum Width Ramp in O(n)?

Build a decreasing monotonic stack of indices while iterating left to right. Then traverse the array from right to left and check whether the current value can form a ramp with the stack's top index. When nums[j] >= nums[i], update the width and pop the index. Each element is processed at most twice, giving O(n) time.

Maximum Width Ramp Python or Java solution?

Python solutions typically implement the monotonic stack using a list and perform a reverse scan to compute widths. Java implementations often follow the same algorithm with a Stack or ArrayDeque. Both achieve O(n) time complexity and O(n) auxiliary space.

What is the best approach for Maximum Width Ramp?

The most efficient approach uses a monotonic decreasing stack. First store candidate starting indices whose values keep decreasing. Then scan the array from right to left and pop indices while nums[j] >= nums[stack.top], updating the ramp width. This method runs in O(n) time and O(n) space and is the solution most interviewers expect.

What data structure is used in Maximum Width Ramp?

The primary data structure is a monotonic stack that stores indices in decreasing order of their values. This structure ensures the left side of potential ramps always contains the smallest candidates, allowing efficient width checks while scanning from the right.

What is the time complexity of Maximum Width Ramp?

The optimal algorithms run in O(n) time. The monotonic stack solution pushes each index once and pops it at most once while scanning from the right. Alternative linear solutions using two pointers with a suffix maximum array also achieve O(n) time with O(n) additional space.

Is Maximum Width Ramp asked at Google, Amazon, or Meta?

Maximum Width Ramp appears in interview preparation lists for companies like Amazon, Google, and Meta because it tests monotonic stack patterns and array scanning techniques. Variations of the problem are also common in competitive programming and coding interviews that focus on stack-based optimizations.

Description Solution Video 14:47

962. Maximum Width Ramp

Medium56.0% acceptance8 companies

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

Asked at 8 companies

Zepto Accenture

Google Amazon Tiktok D. E. Shaw Microsoft Bloomberg

Topics

14:47

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxWidthRamp(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[6,0,8,2,1,5]

Input

[9,8,1,0,1,9,4,0,4,1]

Your code is saved on this device.Solution