0798MediumArrayDynamic Programming

Longest Settled Pylon Stretch

Tracked in this browser only

Trains the technique from

LeetCode 3738Longest Non-Decreasing Subarray After Replacing at Most One Element

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.

A cable crew surveys the pylons of a ski lift from the bottom station upward. Pylon i sits at height[i], measured in centimetres against a survey datum, so a pylon below the datum has a negative height.

A run of consecutive pylons is settled when the heights never drop as you walk it upward: for every neighbouring pair in the run, the later pylon is at least as high as the earlier one. Two pylons at exactly the same height are fine.

Before the survey is signed off, the crew may regrade at most one pylon: pick a single index and change height[i] to any integer you like, positive or negative, with no restriction to the heights already recorded. Every other pylon keeps its height.

Return the greatest number of pylons in a settled run of consecutive pylons that the crew can end up with. Regrading is optional, so a line that is already settled from end to end needs no change.

Examples

Example 1

Input: height = [-3, 4, -1, 6, 6]
Output: 5

Regrading pylon 1 to -2 leaves the heights -3, -2, -1, 6, 6, which never drop, so the whole line of 5 pylons is settled.

Example 2

Input: height = [-5, 8, -4, 7, -6, 2]
Output: 4

Regrading pylon 1 to -5 leaves the heights -5, -5, -4, 7, -6, 2. Pylons 0 through 3 read -5, -5, -4, 7 with no drop, a settled run of 4 pylons.

Example 3

Input: height = [-7, -7, 0, 5]
Output: 4

The recorded heights -7, -7, 0, 5 never drop as they stand, so all 4 pylons are already one settled run and the crew regrades nothing.

Constraints

1 <= height.length <= 10^5
-10^9 <= height[i] <= 10^9

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 longest_settled_stretch(height: list[int]) -> int:

Java

public int longestSettledStretch(int[] height)

The intended approach

Time O(n) for n pylons: two linear passes to fill the tables and one linear pass over the candidate regrade positions.Space O(n) for the two tables.

Precompute two tables in single passes: `rise[i]`, the length of the longest never-dropping run finishing at pylon i, and `fall[i]`, the length of the longest never-dropping run starting at pylon i. Then treat each index in turn as the one pylon that gets regraded: it can always be pulled up to sit on the run ending just before it, or pushed down to sit under the run starting just after it, and the two runs can be welded into one only when the pylon before it is no higher than the pylon after it. The largest value seen over the untouched runs and those three candidates is the answer.

Pythonentry point: longest_settled_stretch

def longest_settled_stretch(height):
    n = len(height)
    # rise[i]: pylons in the longest never-dropping run that ends at pylon i
    rise = [1] * n
    for i in range(1, n):
        if height[i - 1] <= height[i]:
            rise[i] = rise[i - 1] + 1
    # fall[i]: pylons in the longest never-dropping run that starts at pylon i
    fall = [1] * n
    for i in range(n - 2, -1, -1):
        if height[i] <= height[i + 1]:
            fall[i] = fall[i + 1] + 1
    best = max(rise)
    for i in range(n):
        before = rise[i - 1] if i > 0 else 0
        after = fall[i + 1] if i + 1 < n else 0
        if before + 1 > best:
            best = before + 1
        if 1 + after > best:
            best = 1 + after
        if 0 < i < n - 1 and height[i - 1] <= height[i + 1]:
            if before + 1 + after > best:
                best = before + 1 + after
    return best

The obvious version

Try every run of consecutive pylons, every pylon inside it as the regraded one, and every candidate height drawn from the recorded heights plus one below the lowest and one above the highest, then check the run for a drop directly. Any workable regrade can be shifted to one of those candidates, so the enumeration misses nothing. Roughly O(n^4) with the candidate pool folded in.

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_longest_settled_stretch(height):
    n = len(height)
    marks = sorted(set(height))
    pool = marks + [marks[0] - 1, marks[-1] + 1]
    best = 1
    for lo in range(n):
        for hi in range(lo, n):
            span = hi - lo + 1
            if span <= best:
                continue
            for spot in range(span):
                for value in pool:
                    trial = height[lo:hi + 1]
                    trial[spot] = value
                    settled = True
                    for t in range(span - 1):
                        if trial[t] > trial[t + 1]:
                            settled = False
                            break
                    if settled:
                        best = span
                        break
                if best == span:
                    break
    return best

How this problem was checked

Reference solution executed against 18 test cases — 18 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