Maximum Width Ramp - Solution & Explanation

Q: 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.

Q: 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.

MediumArray Stack Monotonic Stack12 min readAsked at: Amazon, Microsoft, Accenture +5

Practice this problem

Problem Statement

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⁴

Approach Overview

Problem Overview: You are given an integer array nums. A ramp is a pair of indices (i, j) such that i < j and nums[i] <= nums[j]. The width of the ramp is j - i. The goal is to find the maximum possible width among all valid ramps.

Approach 1: Monotonic Stack (O(n) time, O(n) space)

This approach builds a decreasing monotonic stack of indices while scanning the array from left to right. Push an index onto the stack only if its value is smaller than the value at the index currently on top of the stack. This ensures the stack contains candidate starting positions for ramps where each new index represents a smaller value than all previous candidates.

Next, iterate from the rightmost index toward the left. For each position j, check whether nums[j] can form a ramp with the index at the top of the stack. While the stack is not empty and nums[j] >= nums[stack.top], compute the width j - stack.top and update the maximum. Pop the index because any later j will produce a smaller width. Each index is pushed and popped at most once, giving O(n) time complexity with O(n) extra space for the stack. This technique is a classic pattern when solving problems with stack structures and monotonic constraints.

Approach 2: Two Pointers with Suffix Maximums (O(n) time, O(n) space)

This approach uses a preprocessing step instead of a stack. First build a suffix array where maxRight[j] stores the maximum value from index j to the end of the array. This tells you the largest possible value that could serve as the right side of a ramp starting at or after j.

Then use two pointers i and j. If nums[i] <= maxRight[j], a valid ramp can exist ending somewhere at or after j. Update the answer with j - i and move j forward to try increasing the width. If the condition fails, increment i because the left value is too large and cannot form a ramp with any future element. Both pointers move forward at most n times, giving linear O(n) time and O(n) extra space for the suffix array. This technique works well for problems involving comparisons across ranges in an array.

Recommended for interviews: The monotonic stack solution is the most common interview answer because it directly models the search for the smallest left candidates and efficiently checks them from the right side. Showing the brute-force idea (O(n^2)) demonstrates baseline reasoning, but implementing the O(n) monotonic stack approach signals strong understanding of stack-based optimization patterns.

Approach 1: Monotonic Stack Approach

This approach utilizes a stack to keep track of indices in a monotonically decreasing order, which helps to quickly find the maximum possible ramp width.

This solution first creates a stack that holds indices of nums in a decreasing manner. It then traverses the array from right to left, popping elements from the stack to calculate potential maximum widths.

Code

Python C++

Python

C++

Complexity

Time Complexity: O(n), where n is the number of elements in the array - because each element is pushed and popped from the stack at most once.
Space Complexity: O(n) for the stack of indices.

Try this approach in the editor →

Approach 2: Two Pointer Approach

This approach uses two pointers to find the maximum width ramp by initially sorting potential endpoints and then finding the earliest start point that forms a valid ramp.

This solution sorts the indices based on their values and then iteratively updates the maximum width by finding the smallest index encountered so far, to ensure the widest ramp.

Code

Java C#

Java

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing indices.

Try this approach in the editor →

Approach 3: Monotonic Stack

According to the problem, we can find that the subsequence formed by all possible nums[i] must be monotonically decreasing. Why is that? Let's prove it by contradiction.

Suppose there exist i_1<i_2 and nums[i_1]leqnums[i_2], then actually nums[i_2] cannot be a candidate value, because nums[i_1] is more to the left and would be a better value. Therefore, the subsequence formed by nums[i] must be monotonically decreasing, and i must start from 0.

We use a monotonically decreasing stack stk (from bottom to top) to store all possible nums[i]. Then we traverse j starting from the right boundary. If we encounter nums[stk.top()]leqnums[j], it means a ramp is formed at this point. We cyclically pop the top elements from the stack and update ans.

The time complexity is O(n) and the space complexity is O(n), where n represents the length of nums.

Code

Python Java C++Go TypeScript JavaScript

Python

Java

C++

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Monotonic Stack Approach	Time Complexity: O(n), where n is the number of elements in the array - because each element is pushed and popped from the stack at most once. Space Complexity: O(n) for the stack of indices.
Two Pointer Approach	Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing indices.
Monotonic Stack	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Check All Pairs	O(n^2)	O(1)	Useful only for understanding the definition of a ramp or when n is very small.
Monotonic Stack	O(n)	O(n)	Best general solution. Common interview approach using a decreasing stack of candidate indices.
Two Pointers with Suffix Maximum	O(n)	O(n)	Good alternative when you prefer pointer scanning and preprocessing instead of a stack.

Video Solution

Maximum Width Ramp - Leetcode 962 - Python • NeetCodeIO • 23,816 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Maximum Width Ramp with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance55.5%

Approaches3

Reading time12 min

Asked at

Amazon Microsoft Accenture Google Zepto

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Monotonic Stack Approach

Code

Complexity

Approach 2: Two Pointer Approach

Code

Complexity

Approach 3: Monotonic Stack

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents