962. Maximum Width Ramp - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Maximum Width Ramp is a problem where we need to find the widest pair of indices (i, j) in an array such that i < j and the value at the left index is less than or equal to the value at the right index (nums[i] <= nums[j]). The width of such a ramp is defined as j - i. In other words, we're looking for two positions in the array, with the left one coming before the right one, where the left value is not greater than the right value, and we want the largest possible distance between those two indices.

Example 1:
Input: nums = [6, 0, 8, 2, 1, 5]
Output: 4
Explanation: The maximum width ramp is between index 1 and index 5 (0-based). At these indices, nums[1] = 0 and nums[5] = 5, and indeed 0 <= 5. The width is 5 - 1 = 4, which is the largest possible. No other valid pair of indices has a larger difference.
Example 2:
Input: nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1]
Output: 7
Explanation: The maximum width ramp here is between index 2 and index 9. We have nums[2] = 1 and nums[9] = 1, satisfying 1 <= 1, and the width is 9 - 2 = 7 . No other (i, j) with i < j yields a wider gap under the required condition.
Example 3:
Input: nums = [1, 2, 3, 4]
Output: 3
Explanation: The array is already non-decreasing, so the smallest index 0 and the largest index 3 form a valid ramp (since 1 <= 4), with width 3 - 0 = 3. This is the maximum possible width because the array is sorted in increasing order.
Example 4:
Input: nums = [5, 4, 3, 2]
Output: 0
Explanation: No valid ramp exists because the array is strictly decreasing. There is no pair (i, j) with i < j that satisfies nums[i] <= nums[j]. According to the problem, if no ramp exists we return 0 (the output 0 here signifies no valid ramp).

The task is to return the maximum width among all such valid ramps in the given array. If there is no valid ramp at all, the result should be 0.

The array can be quite large (length up to 50,000) and values range from 0 to 50,000. This means an efficient solution is needed – a naive approach may not finish in a reasonable time for the worst-case input sizes.

Hints to Guide the Solution

Brute Force Clue: A straightforward approach would be to check every possible pair of indices to see if they form a valid ramp and track the largest distance. However, consider the array length can be up to 50k – iterating over all pairs would be extremely slow (on the order of $N^2$ comparisons). This brute force idea helps understand the problem, but we’ll need to optimize it.
Think in Terms of Extremes: We want a large index difference (j - i), so ideally i should be as small as possible (far left) and j as large as possible (far right) with nums[i] <= nums[j]. If the array were sorted in non-decreasing order, the answer would simply be the distance between the first and last index. The array isn’t sorted, but maybe we can reorder or preprocess the data to mimic this effect.
Monotonic Stack Hint: Often, when we want to enforce an order (like ensuring one element is smaller than another that comes later), a monotonic stack can help. Try thinking from the left side: which indices could serve as good starting points i for a ramp? Perhaps an index that has a very small value and is located early in the array is a good candidate. We might maintain a stack of indices where the array values are in decreasing order. This way, any index on the stack only has larger or equal values to its left, making it a potential ramp start.
Sorting Hint: Another perspective is sorting. If we sort the array values, we lose the original positions – but what if we sort pairs of (value, index)? By sorting based on values, whenever we see a larger value later in the sorted list, its original index could pair with a smaller value’s index that appeared earlier in the sorted order. Think about scanning through a sorted list of values while remembering the smallest index seen so far – this can directly give a candidate width because sorted order guarantees the value condition.
Two-Pointer Insight (Alternative): As an aside hint, consider if you had two arrays: one that for each position gives the minimum value seen up to that position from the left, and another that gives the maximum value seen from that position to the right. Using two pointers on such precomputed arrays is another way some people solve this problem. This isn’t required if you use the above hints, but it’s a useful thought exercise on how to eliminate the need for nested loops.

Using these hints, you should try to reason out an approach that avoids checking every pair explicitly. In particular, hint (3) leads to a stack-based linear solution, and hint (4) leads to a sorting-based solution. Let’s explore the brute force first to cement understanding, then move on to optimized methods.

Brute Force Approach

The brute force solution is direct: check all possible pairs (i, j) with i < j and find the pair that satisfies nums[i] <= nums[j] with the largest difference j - i. We can use two nested loops for this:

Outer loop picks a candidate starting index i (from 0 to n-1).
Inner loop scans for a larger index j (from i+1 to n-1) that has nums[j] >= nums[i]. For each valid pair, compute the width j - i and track the maximum.

A slight improvement is possible by recognizing that if we are at a certain i, and we already found a ramp of width W in a previous iteration, then we don't need to check any j that is closer than W from i – because it wouldn't beat the current maximum. In other words, if (j - i) can never exceed the best found so far, we can break out of the inner loop early. This optimization prunes some unnecessary checks but does not change the worst-case time complexity, which is still quadratic in the worst scenario.

Why it's inefficient: In the worst case (e.g., an array sorted in increasing order), the inner loop runs almost fully for each i, resulting in roughly $N(N-1)/2$ comparisons, which is on the order of $50{,}000^2 \approx 2.5$ billion checks for the maximum input size. This is far too slow. Even with minor pruning, the complexity is $O(N^2)` in the worst case, which will time out.

Brute Force Example: Consider nums = [6,0,8,2]. A brute force approach would check:

i=0: compare with j=1,2,3 → among these, nums[0]=6 <= nums[2]=8 and j-i=2 is valid; also check j=3 (2 is not >=6, so not valid).
i=1: compare with j=2,3 → nums[1]=0 <= nums[2]=8 (width 1), nums[1]=0 <= nums[3]=2 (width 2) valid.
i=2: compare with j=3 → nums[2]=8 <= nums[3]=2 not valid.
i=3: no j > i. The largest width found is 2 (from i=1 to j=3). You can see this approach does a lot of redundant comparisons.

Why it fails for large inputs: With $N=50,000$ , even if each comparison is fast, doing on the order of $10^9$ operations is not feasible in a reasonable time frame. We need a more clever approach that cuts down the problem, leveraging the structure of the problem to avoid brute-force checking of every pair.

Optimized Approaches

We will discuss two efficient approaches to solve this problem: one using a monotonic stack and another using sorting. Both approaches bring the complexity down dramatically by ensuring we don't check every possible pair explicitly.

Monotonic Stack Approach (O(n) time)

Idea: Use a stack to keep track of candidate starting indices (i values) that could potentially form wide ramps. The trick is to maintain this stack in a way that the values at those indices are in decreasing order. By doing this, we ensure that for any index on the stack, all indices below it have larger values (and came earlier in the array). These become our pool of "best candidates" for the left end of a ramp.

Step 1 – Build the Stack: Traverse the array from left to right, and push indices onto a stack such that the array values at those indices form a decreasing sequence. Concretely:

Initialize an empty stack (we will store indices in it).
For each index i from 0 to n-1:
- If the stack is empty, or if the current value nums[i] is smaller than the value at the index on top of the stack (nums[stack.top()]), then push i onto the stack.
- If nums[i] is larger or equal to nums[stack.top()], we do not push it, because a larger or equal value at a later index is not a better candidate than the value already on top (the top has a smaller or equal value and appeared earlier, which would yield a bigger ramp width for any future j). In other words, we only push when we find a new lower value than any seen so far, ensuring the stack’s values are strictly decreasing.

After this first pass, the stack will contain a list of indices where each index has a value less than the value at the previous index in the stack. Importantly, these indices are in increasing order (because we traversed left-to-right), but their values are in decreasing order. Essentially, the stack holds indices of potential ramp starting points sorted by how small their nums values are. Any index not in this stack has some smaller or equal value to its left, which means there's another index that would be a better (more leftward or smaller-valued) start for a ramp.

Step 2 – Find the Widest Ramp: Now we traverse from right to left (from the end of the array toward the start) to find a valid j for the candidates on the stack. For each index j from n-1 down to 0:

While the stack isn’t empty and nums[stack.top()] <= nums[j], it means the top index of the stack (call it i) can form a ramp with the current j (because nums[i] <= nums[j]). We calculate the width j - i and update our answer if this is larger than the best so far.
We pop the stack after counting that ramp, because once index i has found a match at j, any smaller j' < j won’t produce a larger width (since j is as far right as we've gotten so far). We want to remove i to possibly expose the next candidate below it on the stack (which might be another slightly larger value, but still could form a ramp with some slightly smaller j).
Continue this popping as long as the stack’s top can pair with the current j. Once the top of the stack has a value greater than nums[j] (meaning nums[i] > nums[j] for that top i), we stop popping for this j and move j one step to the left.

We do this until we either run out of j (reach the left end) or the stack becomes empty (meaning we've matched all candidate start indices with some right index). We can stop early if the stack gets empty because then we’ve already found ramps for the smallest candidates and no further improvement is possible.

Why it works: The decreasing stack ensures that when we pop an index i off, any remaining index on the stack has a value even smaller than nums[i]. So after handling one index, we are effectively considering the next best candidate for a left index. By scanning from rightmost j to left, we try to give each candidate the farthest possible partner on the right. This greedy approach finds the maximum distance. Once a candidate i is popped (meaning it found a j that works), you never need to consider that i again for smaller j because any smaller j gives a smaller width anyway.

Stack Approach Example:
Consider nums = [6, 0, 8, 2, 1, 5] (the Example 1 array). Let’s walk through the monotonic stack method step by step:

Stack Construction (first pass left-to-right):
- Start with empty stack.
- i = 0: Stack empty, push 0. Stack now [0] (holds indices; values: [6]).
- i = 1: Current value 0 is smaller than nums[stack.top()] = nums[0] = 6, so push 1. Stack now [0, 1] (values: [6, 0] – decreasing order).
- i = 2: Current value 8 is not smaller than nums[stack.top()] = nums[1] = 0 (actually 8 > 0). So we do not push 2. (Why not? Because index 1 has a smaller value 0 and is to the left of 2; any ramp starting at 2 could also start at 1 and be wider or equal width since 0 <= 8.) Stack remains [0, 1].
- i = 3: Current value 2 is not smaller than nums[stack.top()] = 0 (2 > 0), so do not push. Stack remains [0, 1].
- i = 4: Current value 1 is also > 0, do not push. Stack remains [0, 1].
- i = 5: Current value 5 is > 0, do not push. Stack remains [0, 1].
After this pass, stack = [0, 1]. These are the candidate start indices. Indeed, nums[0]=6 and nums[1]=0 are in decreasing order (6 > 0). Index 1 has the smallest value in the array up to that point, and index 0 was the previous smaller record.
Find Ramp (second pass right-to-left):
- Initialize ans = 0.
- j = 5 (value 5): Compare with stack.top = 1 (value 0). Since nums[1] = 0 <= 5 = nums[5], we found a ramp! Width = 5 - 1 = 4. Update ans = 4. Pop the stack (pop index 1). Stack now [0]. We popped 1 because we've found a partner for index 1 at j=5.
  Now stack.top = 0 (value 6). Check nums[0] = 6 <= 5 = nums[5] – this is false (6 > 5), so stop popping.
- j = 4 (value 1): stack.top = 0 (value 6). 6 <= 1 is false, so no pop (no ramp here). Stack still [0].
- j = 3 (value 2): stack.top = 0 (value 6). 6 <= 2 false, no pop.
- j = 2 (value 8): stack.top = 0 (value 6). 6 <= 8 is true, so we found a ramp. Width = 2 - 0 = 2. ans is currently 4, so it stays 4 (since 4 > 2). Pop the stack (pop index 0). Stack now [] .
  Now the stack is empty, meaning all candidate i have been matched with the farthest possible j that worked for them. We can terminate early here. (No need to check j = 1 or j = 0 in the loop because there are no more start candidates left.)
The maximum ans found is 4, which matches the expected output. We successfully identified the ramp (1,5) with width 4.

This approach examined each index at most twice (once pushing, once popping) and avoided redundant comparisons. The example above corresponds to the operations shown in Huahua’s analysis, confirming the correctness of the stack method.

Time Complexity: Building the stack takes O(n) and the second pass also takes O(n) – each index is pushed at most once and popped at most once. Thus, the overall time is O(n) for this approach. This is a huge improvement over brute force.

Space Complexity: O(n) in the worst case for the stack (if the array is strictly decreasing, we push every index). This is acceptable for n up to 50k.

Sorting-Based Approach (O(n log n) time)

Idea: If we sort the array by values, then for any two elements in sorted order, the one that comes later has a value that is greater or equal to the one before (since it's sorted). This sorted order naturally satisfies the value condition nums[i] <= nums[j]. The challenge is relating this back to original indices to compute the distance. The strategy is:

Create a list of pairs (value, index) for each element.
Sort this list primarily by value (in non-decreasing order). If two values are equal, sort by index in increasing order (to preserve the original order for equal values, though equal values also satisfy the condition <= regardless of order).
Iterate through this sorted list, and keep track of the smallest index seen so far as we go. For each new pair (val, idx) in the sorted order, the smallest index seen before represents a potential i (left end) with a value <= current val. So we compute a candidate width idx - min_index_so_far and update the answer if it's larger.
Update the min_index_so_far if the current idx is smaller than the current minimum. Then move to the next pair.

The intuition here is: in sorted order of values, whenever we encounter a new element, all the elements before it have values <= its value. Among those earlier elements, the one with the smallest original index would make the widest ramp with the current element (because it’s the farthest to the left in the array). By tracking the minimum index as we go, we always know the leftmost position from among all values up to the current one.

Sorting Approach Example:
Take the same example nums = [6, 0, 8, 2, 1, 5].

Form (value, index) pairs: [(6,0), (0,1), (8,2), (2,3), (1,4), (5,5)].
Sort by value (ascending): [(0,1), (1,4), (2,3), (5,5), (6,0), (8,2)]. (We list by increasing value; if indices had same value, they'd appear in increasing index order here.)
Now, traverse this sorted list and compute widths:
- Start with min_index_so_far = +∞ (or use a large number or initialize with the first pair’s index).
- (0, 1): The smallest index seen so far is initially large, update min_index_so_far = 1. No earlier index to compare with yet, so we don’t get a ramp here (or think of it as width 1 - inf which we treat as 0).
- (1, 4): Now min_index_so_far = 1 from before. Current index = 4. Width candidate = 4 - 1 = 3. Update ans = 3 (starting from 0). Also update min_index_so_far = min(1,4) = 1 (it stays 1 because 1 is still the smallest index seen so far).
- (2, 3): min_index_so_far = 1. Current index = 3. Width = 3 - 1 = 2. ans remains 3 (since 3 > 2). Update min_index_so_far = min(1,3) = 1.
- (5, 5): min_index_so_far = 1. Current index = 5. Width = 5 - 1 = 4. Update ans = 4 (now we found a larger width). Update min_index_so_far = min(1,5) = 1.
- (6, 0): min_index_so_far = 1. Current index = 0. Width = 0 - 1 = -1 (negative width means current index is to the left of the min_index_so_far; this isn’t a valid ramp in the forward direction, so we can ignore negative or just treat it as not improving the answer). Update min_index_so_far = min(1,0) = 0 (now 0 becomes the smallest index seen so far).
- (8, 2): min_index_so_far = 0. Current index = 2. Width = 2 - 0 = 2. ans remains 4. Update min_index_so_far = min(0,2) = 0.
The largest width encountered was 4 (from index 1 to index 5), which is correct. Essentially, when we hit the pair (5,5), the smallest index seen before was 1 (from the pair (0,1)), yielding width 5-1=4. After processing all pairs, we have our answer.

Note: Another way to visualize this is: after sorting, we look for how far apart we can get an increasing sequence of indices. We found that in the sorted-by-value list, index 1 (value 0) appears before index 5 (value 5), giving a valid ramp (because 0 <= 5) with distance 4. Sorting made it easy to find that pair without explicitly checking the original array order for every combination of values.

Time Complexity: Sorting the list of n pairs takes O(n log n). The subsequent single pass through the sorted list is O(n). So overall complexity is O(n log n). For n = 50k, this is very manageable. (50k log 50k is on the order of 50k * ~15.6 ≈ 780k operations, which is fine.)

Space Complexity: O(n) extra space for the list of pairs (and additional space overhead from sorting). This is acceptable for n up to 50k.

Both approaches above (monotonic stack and sorting) are efficient and will work for the maximum input sizes. The stack approach is optimal in time (O(n)), while the sorting approach is a bit slower (O(n log n)) but still well within limits. Next, let's see concrete implementations of these approaches in code.

Code Implementations

Python Implementation

Python3

. . . .

Both functions maxWidthRamp_stack and maxWidthRamp_sort should return the same correct result. The stack method builds the candidate list in the first loop and then finds the ramp in the second loop . The sorting method uses a single pass after sorting to compute the max width .

Java Implementation

Java

. . . .

In the Java stack approach, we use a Stack<Integer> to store indices. The logic mirrors the Python version: first loop builds the stack of candidate start indices, second loop scans from the end and computes distances while popping. In the sorting approach, we sort a 2D array arr where each element is [value, index], then iterate through it updating minIndexSoFar and maxWidth similarly to the Python version.

Note: We could also implement the sorting approach in Java by sorting indices using a custom comparator that compares nums[i] values, but using a separate array of pairs might be more straightforward to understand.

Complexity Analysis

Let's break down the complexity for each approach:

Brute Force: Time complexity is $O(N^2)$ in the worst case. For each of the $N$ possible i values, we might scan up to $N$ j values (though on average fewer due to breaks). This is infeasible for large N (e.g., $50,000^2$ operations). Space complexity is $O(1)$ (just a few variables for tracking indices and max, no significant extra storage).
Monotonic Stack Approach: Time complexity is $O(N)$ . We traverse the array twice (one build, one scan) and each index is pushed and popped at most once. All comparisons and operations are constant-time, so it scales linearly with the array length. Space complexity is $O(N)` in the worst case (if every element gets pushed to the stack). For example, if the array is strictly decreasing, the stack will end up holding all indices; if the array is increasing, the stack holds only the first index and maybe a few subsequent drops. Either way, at most N elements in the stack.
Sorting-Based Approach: Time complexity is $O(N\log N) \$ due to sorting the array of pairs. Sorting dominates the complexity, with the post-processing loop being O(N). For N=50k, this is efficient. Space complexity is $O(N)` for creating the list/array of pairs and any sorting overhead.

Both optimized approaches are efficient enough for the given constraints. The stack approach uses more algorithmic insight to achieve linear time, while the sorting approach leverages Python/Java sorting which is highly optimized and quite fast for 50k elements.

Step-by-Step Walkthrough of Solutions

To solidify understanding, let’s do a step-by-step walkthrough with a visual aid for each optimized approach using a small example. We will use the array from Example 1: nums = [6, 0, 8, 2, 1, 5].

Monotonic Stack Walkthrough (Example 1):

Imagine the array indices and values laid out as follows:

Index:  0  1  2  3  4  5
Value:  6  0  8  2  1  5

First Pass (build stack of start indices): We iterate left to right.
1. i=0: stack is empty, push 0. (Stack = [0] representing value [6])
2. i=1: current value = 0, compare with value at stack top (index 0 -> value 6). Since 0 < 6, push 1. (Stack = [0, 1], values = [6, 0] – strictly decreasing)
3. i=2: current value = 8, stack top = index 1 (value 0). 8 is not less than 0 (it's greater), so do not push index 2. (Stack remains [0,1])
4. i=3: current value = 2, stack top = index 1 (value 0). 2 > 0, so do not push. (Stack remains [0,1])
5. i=4: current value = 1, stack top = index 1 (value 0). 1 > 0, so do not push. (Stack remains [0,1])
6. i=5: current value = 5, stack top = index 1 (value 0). 5 > 0, so do not push. (Stack remains [0,1])
After this pass, our stack contains [0, 1]. These are the candidate i indices. In terms of array values, that's [6, 0] – notice 6 > 0, so values on stack are in decreasing order. Index 1 is a better starting candidate than 2,3,4,5 because it has the smallest value seen so far.
Second Pass (find maximum ramp using stack): Now we scan from the rightmost index down to 0, trying to pair each j with the smallest possible i from the stack.
1. j = 5 (value = 5):
  - Stack top = 1 (value = 0). Check nums[1] <= nums[5] i.e. 0 <= 5 – true. So (i=1, j=5) is a valid ramp. Width = 5 - 1 = 4. Update max_width = 4. Pop index 1 from stack (we’ve used index 1). (Stack now = [0]) .
  - Now stack top = 0 (value = 6). Check nums[0] <= nums[5] i.e. 6 <= 5 – false. So we stop popping for j=5. (We don't pop index 0.)
2. j = 4 (value = 1):
  - Stack top = 0 (value = 6). Check 6 <= 1 – false. No pop. (Stack = [0] still.)
3. j = 3 (value = 2):
  - Stack top = 0 (value = 6). Check 6 <= 2 – false. No pop.
4. j = 2 (value = 8):
  - Stack top = 0 (value = 6). Check 6 <= 8 – true! So (i=0, j=2) is a valid ramp. Width = 2 - 0 = 2. Update max_width = max(4, 2) = 4 (it remains 4 since we already found 4). Pop index 0 from stack. (Stack now = []).
  - Stack is now empty, meaning we have no more candidate start indices left. We can break out early.
5. We stop because the stack is empty, even though j would go to 1 and 0 next – there's no need since we have no more i candidates to check.
During this process, we found the best ramp width was 4 (from i=1 to j=5). We successfully avoided checking many unnecessary pairs by always pairing current j with the best available i (smallest value) first. The popping ensures each candidate i is considered with the furthest possible j that can work for it, and then removed once it's done.

We can visualize the critical step where we found the width 4 ramp:

At j=5 (value 5), the stack had [0,1] corresponding to values [6,0]. We popped 1 because 0 <= 5 (valid ramp). That gave width 4. Then index 0 remained, but 6 > 5 so it didn't pop at j=5.
Later, at j=2 (value 8), we popped 0 because 6 <= 8, giving width 2. By then we already had our answer 4.

Sorting-Based Walkthrough (Example 1):

Let's walk through the same example using the sorting approach, with the array and indices:

Index:  0  1  2  3  4  5
Value:  6  0  8  2  1  5

Sort by value: List out pairs (value, index) and sort:
- Original pairs: (6,0), (0,1), (8,2), (2,3), (1,4), (5,5)
- Sorted by value: (0,1), (1,4), (2,3), (5,5), (6,0), (8,2).
  (Let's verify: smallest value 0 at index1, next value 1 at index4, then 2 at index3, 5 at index5, 6 at index0, 8 at index2. Yes.)
Scan through sorted pairs: We will keep track of the minimum index seen so far as we go.
- Initialize min_index_so_far = +∞ (a very large number) and max_width = 0.
1. Pair (0, 1):
  - Current index = 1.
  - min_index_so_far is +∞, so update it to 1 (the first index we see).
  - No earlier index to form a ramp with yet (this is the first element), so we move on.
  - (After this, min_index_so_far = 1, max_width = 0.)
2. Pair (1, 4):
  - Current index = 4.
  - The smallest index seen before is 1. We check the width: 4 - 1 = 3.
  - Update max_width = 3 (because 3 > 0).
  - Update min_index_so_far = min(1, 4) = 1 (still 1).
  - (Now min_index_so_far = 1, max_width = 3.)
3. Pair (2, 3):
  - Current index = 3.
  - min_index_so_far = 1. Width = 3 - 1 = 2.
  - max_width remains 3 (since 2 < 3).
  - Update min_index_so_far = min(1, 3) = 1.
  - (Now min_index_so_far = 1, max_width = 3.)
4. Pair (5, 5):
  - Current index = 5.
  - min_index_so_far = 1. Width = 5 - 1 = 4.
  - Update max_width = 4 (because 4 > 3).
  - Update min_index_so_far = min(1, 5) = 1.
  - (Now min_index_so_far = 1, max_width = 4.)
5. Pair (6, 0):
  - Current index = 0.
  - min_index_so_far = 1. Width = 0 - 1 = -1 (negative width indicates this current index is actually smaller than the min seen so far – essentially, we found an even smaller index, which will help future pairs but doesn't form a valid ramp with anything earlier).
  - max_width stays 4.
  - Update min_index_so_far = min(1, 0) = 0. (We found a new smallest index.)
  - (Now min_index_so_far = 0, max_width = 4.)
6. Pair (8, 2):
  - Current index = 2.
  - min_index_so_far = 0. Width = 2 - 0 = 2.
  - max_width stays 4 (since 2 < 4).
  - Update min_index_so_far = min(0, 2) = 0.
We have finished scanning all pairs. The maximum width found is 4. This corresponds to the ramp between index 1 and index 5, which is the correct answer.

Notice how the sorted list method effectively considered pairs of indices out-of-order by value. For instance, it considered index1 (val0) and index5 (val5) together when it reached index5’s pair, because index1 was the smallest index seen so far. The negative width we got at (6,0) step is a byproduct of updating the minimum index; it basically indicates "hey, we found a new leftmost index". After that point, that new index (0) could pair with later values (like with value 8 at index2, giving width 2) but in this case, it didn’t beat the width=4 we already had.

Both the monotonic stack and sorting approaches arrive at the same answer through different means: one by structural decreasing stack and scanning from the right, and the other by sorting values and tracking indices. In either approach, each element’s index is considered in a way that avoids exhaustive pair checking.

Common Mistakes

Beginners may run into a few pitfalls with this problem:

Confusing the Conditions: It’s important to remember the condition is nums[i] <= nums[j] for i < j. Forgetting the equality (<=) can cause you to miss ramps where values are equal. Conversely, assuming it’s strictly less when it’s not, or vice versa, will lead to wrong answers. Always double-check the problem statement for the correct inequality.
Using Brute Force on Large Inputs: Writing a double loop to check all pairs will work on small examples but time out for large arrays. A common mistake is to implement brute force first and assume it might pass; for N = 50,000 it definitely won’t. Make sure to analyze the input size and recognize when $O(N^2)$ is not feasible.
Misusing the Stack Conditions: When building the monotonic stack, the condition should be strictly if stack.empty() or nums[i] < nums[stack.top()] then push. If you use <= to push, you might end up pushing indices that have equal values, which is unnecessary and can cause you to pop a suboptimal index later. We want the stack to hold indices of strictly decreasing values so that each index on the stack is the best candidate (smallest value seen so far up to that point) for a ramp start. Using the wrong comparison can break this invariant.
Forgetting to Pop Correctly: In the stack approach, make sure to pop inside a loop while the condition holds (as shown above). Popping only once per j (or not using a loop) would be wrong, because a single j might satisfy the condition for multiple stack indices. For example, in our walkthrough, j=5 was able to pop index 1 off the stack; if there had been another candidate with value <=5, it should pop that too. Not popping in a loop could miss those cases.
Off-by-One Errors: When calculating the width j - i, ensure you use the correct indices. This might sound trivial, but if you accidentally swap or use the wrong indices (especially in a complex loop), you could compute meaningless values. In the context of these algorithms, i always comes from the stack or from the min seen so far, and j comes from the current loop index.
Not Resetting Tracking Variables: If you implement multiple test cases or run your function multiple times, ensure that global or static variables (if any) like max_width or min_index_so_far are reset each time. In our code, we define them within the function, so it’s not an issue. But it’s a common bug to accidentally carry over a value from a previous run if not careful.
Not Handling No Ramp Case: If no ramp exists, the answer should be 0. Our algorithms naturally result in 0 in that scenario (because max_width would remain at initial 0). However, if someone initialized max_width differently or returns -1 for no found ramp, that would be incorrect as per the problem (should be 0, not -1 or any other value). Make sure the output for "no valid pair" is handled as 0.

By being mindful of these issues – particularly the stack conditions and loop structures – you can avoid common errors. If you implement one of the optimized approaches carefully, you should get the correct result for all cases.

Edge Cases

Let's consider some edge cases and how the solution handles them:

Smallest Array (length 2): With 2 elements, the answer is either 1 if nums[0] <= nums[1], or 0 if not. For example, [a, b] yields 1 if a <= b, else 0. Our algorithms handle this: the stack approach would push index 0, then check j=1 against it; the sorting approach would sort two elements and compute the difference if applicable. Both will correctly yield 1 or 0 as needed.
All Increasing (sorted ascending): e.g. nums = [1, 2, 3, 4, 5]. Here every later element is >= earlier elements, so the maximum ramp is the whole array from index 0 to 4 (width 4). The stack solution would push index 0, then never push any other index (because every new value is >= the last, so it fails the nums[i] < nums[stack.top()] check). In the second pass, when j reaches the end, it will pop index 0 giving width = lastIndex - 0. The sorting solution will find min index 0 and max index 4 through iteration. Both give the correct answer 4.
All Decreasing (sorted descending): e.g. nums = [5, 4, 3, 2, 1]. No valid ramp because no element to the right is ever >= an element to its left. The stack approach would push every index (since each new element is smaller than the previous), so stack = [0,1,2,3,4]. Then in the second pass, it will check from the rightmost j:
- j=4 compares with stack.top=4 immediately (value equal), pops it (width 0, but max stays 0).
- j=3 compares with next top=3, pops, etc. In the end, max_width remains 0. The sorting approach would find that the smallest index seen so far always comes from the rightmost value (since values are decreasing, the last element will have the smallest index in sorted order, but that yields negative or zero widths with others). It would also result in max_width 0. So output is 0, as expected. Edge-case: if strictly decreasing, the only “ramps” are of width 0 (same index), which we don't count because i < j is required, hence we return 0.
All Equal Values: e.g. nums = [7, 7, 7, 7]. Here any i < j satisfies nums[i] <= nums[j] because all values are equal. The widest ramp would be from index 0 to 3 (width 3). The stack approach will push index 0 (value 7), then not push any further indices (because each new value 7 is not less than the stack top’s 7 — note our push condition is strict < to keep values decreasing, so we don't push equal values). Thus the stack ends up with just [0]. Then in the second pass, when j=3 (or any j), it will pop 0 on the first comparison since nums[0] (=7) <= nums[j] (=7) is true, giving width = j - 0. For j=3 that’s 3, which will be the max. The sorting approach will sort pairs by value (they're all the same value 7, so effectively it sorts by index ascending). It will then find min index 0 first, and for each subsequent index j, it will compute j - 0 as the width, updating the max_width as it goes. It will correctly end up with 3. So both approaches handle equal values gracefully.
Random Distribution / Typical Cases: The solutions don’t rely on special structure beyond the conditions we enforce (stack decreasing order, sorted order). They work for any pattern – alternating up/down, plateaus of equal values, etc. For example, nums = [2, 2, 1, 2, 2]: Here the best ramp is likely from index 2 (value 1) to index 4 (value 2) with width 2 (or possibly index 0 to index 4 if equal counts, which gives 4-0=4 since 2 <= 2 is true; actually yes, index 0 to 4 is valid because nums[0]=2, nums[4]=2). It's good to verify such scenarios. The stack approach: stack would get [0] (2), then not push 1 (since 2 is not >2? Actually nums[stack.top()]=2, nums[1]=2, since 2 is not less than 2, we do not push index1), then push index 2 because 1 < 2, etc. It will find the width 4 eventually. The sorting approach will sort by values and also yield width 4. So it's fine.
No Ramp vs 0 Difference: Remember that a result of 0 could mean either no ramp was found or that the best ramp has width 0. But width 0 would imply i and j are the same, which isn't allowed (i<j), so effectively 0 means "no valid pair". Our algorithms naturally give 0 in that case. It's worth noting this distinction: if the array had any valid pair, the minimum width would be 1 (from adjacent pair that works). So 0 is unambiguously "no ramp".

The solutions cover these edge cases. The monotonic stack approach, in particular, is robust in handling descending or equal values sequences because of how we handle the push condition and the pops. The sorting approach inherently covers all by considering all elements in value order.

This problem is essentially about finding two indices with a condition on their values and maximizing the distance between the indices. A very similar classic problem is often known as the Maximum Index Difference problem: “Given an array, find the maximum j - i such that arr[i] <= arr[j].” This is exactly the same formulation as our ramp problem. If you want more practice, you can look up this problem on interview prep sites. (In some versions, they require arr[i] < arr[j] strictly, which changes it slightly, but the approach remains similar.) For instance, a known GeeksforGeeks problem statement reads: “Given an array A[] of N positive integers, find the maximum of j - i such that A[i] <= A[j].” ([Given an array arr[], find the maximum j – i such that arr[j] > arr[I] which is word-for-word our problem.

Some variations and related problems or techniques include:

Two-Pointer Approach on Sorted Auxiliary Arrays: An alternative solution for this same problem uses a two-pointer technique with precomputed prefix minima and suffix maxima. You create an array minLeft[i] = minimum of nums[0...i] and maxRight[j] = maximum of nums[j...n-1]. Then, you move two pointers i and j starting at 0:
- If minLeft[i] <= maxRight[j], that means there exists some index i' ≤ i and some index j' ≥ j such that nums[i'] <= nums[j']. So you record width = j - i as a candidate (because for the current i, j is the farthest right that satisfies the condition), then increment j to try for a bigger gap.
- If minLeft[i] > maxRight[j], it means even the smallest value up to i is bigger than the largest value from j to end, so this particular i can't form a ramp with this j; increment i to narrow the left side.
  This approach also runs in O(n) and is a classic solution for the "maximum index difference" problem. It’s a bit different in structure but arrives at the same result.
Next Greater Element / Nearest Smaller Element Problems: The monotonic stack approach we used is reminiscent of problems like Next Greater Element, Daily Temperatures, or Trapping Rain Water (which uses a stack for boundaries). In those, you often maintain a stack of indices with certain order (increasing or decreasing) to find the next element that is higher or lower. The twist in Maximum Width Ramp is that we are looking for the furthest element to the right that satisfies the condition, not just the next. Our use of scanning from the right after building the stack is a common pattern for these "furthest element" problems. If you found this problem interesting, practicing "Next Greater Element I/II" or "Daily Temperatures" on LeetCode can help solidify your understanding of monotonic stacks.
“Container With Most Water” Problem: While the problem is different (that one asks for two lines that can hold most water, using two pointers), there's a conceptual similarity in trying to maximize distance under a constraint. However, the techniques differ (two-pointer from both ends for that problem). It’s a reminder that not all “max distance” problems use the same method – here the condition nums[i] <= nums[j] made a monotonic structure viable.
Other Related LeetCode Problems: Problems like “Car Fleet” (uses a sort and stack approach for a different scenario), “Longest Valid Parentheses” (stack usage for valid substring lengths), or “Maximum Gap” (which is about values, not indices, but involves sorting) are all examples where either sorting or stack techniques are used to optimize a solution. While the content differs, improving at recognizing when a monotonic stack or sorting trick can be applied will help in many of these problems.
GeeksforGeeks Practice: The exact problem (maximum index difference) is a common question on GfG. There, they often expect either the two-pointer method or sorting method as the answer. If you want to try an alternate implementation, you could implement the prefix-min and suffix-max two-pointer approach described above and verify it against the same test cases.