Longest Mountain in Array

Medium
766.

Longest Mountain in Array

Longest Mountain in Array is a medium coding problem on arrays, dynamic programming and two pointers, asked in Amazon, Google, Adobe and Databricks interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var longestMountain = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Mountain in Array — Solution in Python, Java & C++

Longest Mountain in Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Mountain in Array is a medium coding problem on arrays, dynamic programming and two pointers, asked in Amazon, Google, Adobe and Databricks interviews.

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

Hints for Longest Mountain in Array

  1. Hint 1

    Find the peaks first: an index that is strictly greater than both neighbours.

  2. Hint 2

    From a peak, walk left while the values keep rising and right while they keep falling.

  3. Hint 3

    Restart the outer scan at the right foot — mountains found this way never overlap.

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

  1. Scan i over the interior indices looking for arr[i-1] < arr[i] > arr[i+1].
  2. Walk l left while arr[l-1] < arr[l], and r right while arr[r] > arr[r+1].
  3. 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

Java

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

C++

int longestMountain(vector<int>& arr) {
    int n = (int) arr.size(), best = 0, i = 1;
    while (i < n - 1) {
        if (!(arr[i - 1] < arr[i] && arr[i] > arr[i + 1])) { i++; continue; }
        int l = i - 1;
        while (l > 0 && arr[l - 1] < arr[l]) l--;
        int r = i + 1;
        while (r < n - 1 && arr[r] > arr[r + 1]) r++;
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming