Longest Mountain in Array — Medium Problem & Solution

A mountain is a subarray of length at least 3 that strictly increases to a single peak and then strictly decreases.

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Two Pointers
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A mountain is a subarray of length at least 3 that strictly increases to a single peak and then strictly decreases. The peak may not be the first or last element of the subarray.

Return the length of the longest mountain, or 0 if there is none.

Example 1

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The mountain [1,4,7,3,2] has length 5.

Example 2

Input: arr = [2,2,2]
Output: 0
Explanation: No strict increase anywhere.

Example 3

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

Constraints

1 <= arr.length <= 10000
0 <= arr[i] <= 10000

How to solve Longest Mountain in Array

Every mountain has exactly one peak, so enumerate peaks and expand outwards. Because the descent of one mountain cannot be the ascent of another, resuming the outer scan at the right foot keeps the whole thing linear.

Approach

Scan i over the interior indices looking for arr[i-1] < arr[i] > arr[i+1].
Walk l left while arr[l-1] < arr[l], and r right while arr[r] > arr[r+1].
Record r - l + 1 as a candidate and continue the outer scan from r.

Why it works

A mountain is determined by its peak, and the two walks find the maximal strictly monotone runs around it. Resuming at r is safe because any later mountain's ascent must begin at or after r — the stretch from the peak to r is strictly decreasing and so cannot be part of another ascent.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Plateaus break strictness, so arr[i-1] <= arr[i] is the wrong test.
A mountain needs both a rise and a fall; a purely increasing run scores 0.
Restarting the outer loop at i + 1 still works but re-walks the descent, making it quadratic in the worst case.

Reference solution

Python

from typing import List

def longestMountain(arr: List[int]) -> int:
    n = len(arr)
    best = 0
    i = 1
    while i < n - 1:
        if not (arr[i - 1] < arr[i] > arr[i + 1]):
            i += 1
            continue
        l = i - 1
        while l > 0 and arr[l - 1] < arr[l]:
            l -= 1
        r = i + 1
        while r < n - 1 and arr[r] > arr[r + 1]:
            r += 1
        best = max(best, r - l + 1)
        i = r
    return best

JavaScript

var longestMountain = function(arr) {
    var n = arr.length, best = 0, i = 1;
    while (i < n - 1) {
        if (!(arr[i - 1] < arr[i] && arr[i] > arr[i + 1])) { i++; continue; }
        var l = i - 1;
        while (l > 0 && arr[l - 1] < arr[l]) l--;
        var r = i + 1;
        while (r < n - 1 && arr[r] > arr[r + 1]) r++;
        if (r - l + 1 > best) best = r - l + 1;
        i = r;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue