0969MediumArrayTwo PointersDynamic ProgrammingEnumeration

Longest Ridge in the Profile

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.

Ground heights along a track are given as arr.

A ridge is a stretch of at least three heights that rises strictly for a while and then falls strictly for a while: there is a position inside it, neither end, where everything before rises strictly up to it and everything after falls strictly away from it.

Return the length of the longest ridge, or 0 when the track holds none.

Examples

Example 1

Input: arr = [3, 8, 14, 9, 4, 4, 11, 2]
Output: 5

The heights rise 3, 8, 14 and then fall 9, 4, which is a ridge of five. The fall stops at the level pair of fours, so the ridge cannot reach further.

Example 2

Input: arr = [1, 2, 3, 4, 5]
Output: 0

The track only rises, so there is no peak and no ridge.

Example 3

Input: arr = [1, 2, 2, 1]
Output: 0

The two level heights in the middle mean neither is a peak, since a peak needs its neighbours strictly lower.

Constraints

1 <= arr.length <= 10^4
0 <= arr[i] <= 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 longest_mountain(arr: list[int]) -> int:

Java

public int longestMountain(int[] arr)

The intended approach

Time O(n) for a track of n heights: each position is walked over a bounded number of times.Space O(1).

Walk the track looking for the peaks. A position is a peak when its neighbour on the left is strictly lower and its neighbour on the right is strictly lower too. From a peak, run back while the heights keep falling and forward while they keep falling, and the ridge is everything between where those two runs stop. Because the runs from a peak never overlap the runs from another peak, walking every position and extending only from the peaks costs a linear amount of work in total. Take the longest ridge found, and nothing at all when no peak exists.

Pythonentry point: longest_mountain

def longest_mountain(arr):
    n = len(arr)
    best = 0
    for peak in range(1, n - 1):
        if arr[peak - 1] >= arr[peak] or arr[peak] <= arr[peak + 1]:
            continue
        left = peak
        while left > 0 and arr[left - 1] < arr[left]:
            left -= 1
        right = peak
        while right < n - 1 and arr[right] > arr[right + 1]:
            right += 1
        if right - left + 1 > best:
            best = right - left + 1
    return best

The obvious version

Try every stretch of at least three heights and every position inside it as the peak, checking that the heights rise strictly up to that position and fall strictly after it. Cubic in the track's length and it looks for no peaks in advance.

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_mountain(arr):
    n = len(arr)
    best = 0
    for start in range(n):
        for end in range(start + 2, n):
            for peak in range(start + 1, end):
                ok = True
                for i in range(start, peak):
                    if arr[i] >= arr[i + 1]:
                        ok = False
                        break
                if ok:
                    for i in range(peak, end):
                        if arr[i] <= arr[i + 1]:
                            ok = False
                            break
                if ok and end - start + 1 > best:
                    best = end - start + 1
    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