0947MediumArrayTwo PointersStackMonotonic Stack

Widest Span That Does Not Fall

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Readings are given as nums.

A span is a pair of positions i before j where the later reading is at least the earlier one. Its width is the difference of the positions.

Return the widest span, or 0 when no span exists.

Examples

Example 1

Input: nums = [14, 3, 27, 9, 3, 41]
Output: 5

The reading 14 at the front pairs with the 41 at the end, five apart, which is as wide as the list allows.

Example 2

Input: nums = [9, 8, 7, 6, 5, 4]
Output: 0

Every reading falls below the one before it, so no pair qualifies.

Example 3

Input: nums = [7, 7, 7, 7, 7]
Output: 4

Equal readings count, since the later one only has to be at least the earlier, so the two ends pair up.

Constraints

2 <= nums.length <= 5 * 10^4
0 <= nums[i] <= 5 * 10^4

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_width_ramp(nums: list[int]) -> int:

Java

public int maxWidthRamp(int[] nums)

The intended approach

Time O(n) for n readings: one pass to build the run and one to match it.Space O(n) for the run of candidate left ends.

Only some positions are worth using as the left end of a span. If a reading has an earlier reading that is no larger, then any span starting here is beaten by one starting there, so the position is useless. What is left, walking from the front and keeping a position only when it is strictly below everything kept so far, is a run of positions whose readings strictly fall. That run is sorted both by position and, backwards, by reading, which is what lets the right end be matched greedily. Walk the positions from the back; while the last kept left end has a reading at most this one, that pairing is a span, so record the width and drop that left end, since no later right end could pair with it more widely. Each left end is dropped once, so the whole sweep is linear after the run is built.

Pythonentry point: max_width_ramp

def max_width_ramp(nums):
    n = len(nums)
    candidates = []
    for i in range(n):
        if not candidates or nums[i] < nums[candidates[-1]]:
            candidates.append(i)
    best = 0
    for j in range(n - 1, -1, -1):
        while candidates and nums[candidates[-1]] <= nums[j]:
            width = j - candidates.pop()
            if width > best:
                best = width
    return best

The obvious version

Try every pair of positions, keep those where the later reading is at least the earlier one, and take the widest. Quadratic in the reading count and it keeps nothing.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_width_ramp(nums):
    n = len(nums)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            if nums[j] >= nums[i] and j - i > best:
                best = j - i
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in