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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Two Pointers
- Asked at: Amazon, Google, Adobe, Databricks
- 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 <= 100000 <= arr[i] <= 10000
Hints for Longest Mountain in Array
Hint 1
Find the peaks first: an index that is strictly greater than both neighbours.
Hint 2
From a peak, walk left while the values keep rising and right while they keep falling.
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
- Scan
iover the interior indices looking forarr[i-1] < arr[i] > arr[i+1]. - Walk
lleft whilearr[l-1] < arr[l], andrright whilearr[r] > arr[r+1]. - Record
r - l + 1as a candidate and continue the outer scan fromr.
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 + 1still 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 bestJava
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