We need to find two indices i and j where i < j and nums[i] <= nums[j], and we want to maximize the gap j - i. In other words, we're looking for the widest possible "ramp" where the value at the left end doesn't exceed the value at the right end.

A brute force approach checks every pair (i, j), which is O(n^2). To do better, we need to avoid examining every pair.

The left endpoint i of an optimal ramp is always an index whose value is a "new minimum" as we scan left to right. If nums[i] is not smaller than everything before it, then some earlier index has a value less than or equal to nums[i], and that earlier index pairs with the same j to form a wider ramp. So the candidates for i form a decreasing sequence of values, which a monotonic stack captures directly.

Key Constraints:

Intuition

For each left endpoint i, the widest ramp starting there ends at the farthest j with nums[j] >= nums[i]. So instead of testing every j, scan from the right end inward and stop at the first j that works — it is already the farthest one.

The scan still touches every pair in the worst case, so it runs in O(n^2) time, but it exits early on most inputs.

Algorithm

Visualization and Code

Most of these pairs are irrelevant. If nums[i] is not a "new minimum" going left to right, an earlier index with a smaller value gives a wider ramp with the same right endpoint. The next approach removes the quadratic work by sorting on value and reducing the problem to a gap between original indices.

Intuition

Sort the elements by value while keeping their original indices. For any two elements in sorted order, the one that appears earlier has a value less than or equal to the later one, so the ramp condition nums[i] <= nums[j] holds for every earlier-later pair. The problem reduces to finding the maximum difference between original indices, where the smaller index comes first in the array.

Iterating through the sorted order, we track the minimum original index seen so far, starting it at n so the first element always claims it. For each element, if its original index is greater than that minimum, the pair forms a valid ramp and the candidate width is the difference; otherwise the element itself becomes the new minimum. The maximum across all elements is the answer. Tie-breaking by index keeps equal values in increasing index order, so equal-valued elements still form valid ramps with each other.

Algorithm

Visualization and Code

The sorting step dominates the runtime at O(n log n). The next approach identifies the useful left endpoints in one linear pass and matches them with right endpoints in another, dropping the sort and reaching O(n).

Intuition

This solution runs in O(n) time and rests on two observations.

First, the left endpoint of the optimal ramp belongs to the strictly decreasing prefix of values. If nums[i] is not a new minimum, then some i' < i has nums[i'] <= nums[i], and for any valid ramp (i, j) the pair (i', j) is also valid and at least as wide. So the only left-endpoint candidates are indices that form a strictly decreasing sequence from the start, which we collect in a stack during a left-to-right pass.

Second, for the right endpoint we want the largest possible j, so we scan from right to left. For each j, while nums[j] is at least the value at the top of the stack, that stack index is a valid left endpoint, so we pop it and record the width. The right-to-left order means the first j that satisfies a given left endpoint is the largest such j, so once we pop an index we already have its widest ramp.

Algorithm

Visualization and Code