Longest Mountain in Array solution and explanation
IBM
Google
9 more videos on this problem
Longest Mountain in Array Leetcode 845 || MediumCode with Alisha · 8:11 · 16K views
Longest Mountain in Array | Live Coding with Explanation | Leetcode #845Algorithms Made Easy · 6:39 · 9K views
Longest Mountain in Array | LeetCode 845EazyAlgo · 13:40 · 5K views
Longest Mountain in Array | Leet code 845 | Theory explained + Python codeSai Anish Malla · 13:27 · 4K views
LeetCode 845. Longest Mountain in ArrayHappy Coding · 12:05 · 1K views
Longest Mountain in Array Leetcode Solution | PythonProgramming Solutions · 8:38 · 1K views
Longest Mountain in an Array - LEETCODE 845 | Interview QuestionnETSETOS · 13:58 · 958 views
LeetCode - 845. Longest Mountain in Array | Two Pointers Technique | JavaOrkhan Gasanov · 9:24 · 545 views
Learn 2 solve Longest Mountain in Array using Dynamic Programming | Leetcode 845Joey'sTech · 10:29 · 499 views
Daily Leetcode #230: Nov 16, 2020 - 845. Longest Mountain in ArrayProgramming Live with Larry · 12:14 · 442 views
The problem
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3- There exists some index
i(0-indexed) with0 < i < arr.length - 1such that:arr[0] < arr[1] < ... < arr[i - 1] < arr[i]arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.
Example 1:
Input: arr = [2,1,4,7,3,2,5] Output: 5 Explanation: The largest mountain is [1,4,7,3,2] which has length 5.
Example 2:
Input: arr = [2,2,2] Output: 0 Explanation: There is no mountain.
Constraints:
1 <= arr.length <= 1040 <= arr[i] <= 104
Follow up:
- Can you solve it using only one pass?
- Can you solve it in
O(1)space?
Approach overview
Problem Overview: You are given an integer array and need the length of the longest mountain. A mountain is a subarray where values strictly increase to a peak and then strictly decrease. The subarray must contain at least three elements and the peak cannot be at the ends.
The challenge is identifying valid peaks while ensuring the left side strictly rises and the right side strictly falls. Efficient solutions avoid recomputing slopes for every position and instead track increasing and decreasing segments using linear scans. This problem mainly relies on array traversal patterns from Array problems combined with pointer movement techniques from Two Pointers.
Approach 1: Two-Pass Approach with Peak Detection (O(n) time, O(n) space)
This approach precomputes how long the array increases and decreases at every index. First pass from left to right builds an up[] array where up[i] stores the length of the increasing slope ending at i. Second pass from right to left builds a down[] array where down[i] stores the length of the decreasing slope starting at i. A valid mountain peak exists where both values are greater than zero. The total mountain length becomes up[i] + down[i] + 1. Iterate through all indices and track the maximum.
This method is easy to reason about because each direction is handled independently. The tradeoff is extra memory for two arrays, but the logic stays simple and deterministic. The idea resembles prefix-style preprocessing seen in Dynamic Programming problems where partial results are reused.
Approach 2: Single-Pass Gradient Tracking (O(n) time, O(1) space)
This approach scans the array once while tracking the current uphill and downhill lengths. When the sequence is increasing, increment the up counter. When it switches to decreasing, increment the down. A valid mountain appears only if both counters are positive. If the slope resets (equal values or a new increasing segment after decreasing), reset the counters accordingly.
During each step, update the answer when both up > 0 and down > 0. The length of the current mountain is up + down + 1. This solution effectively performs inline Enumeration of slope segments while maintaining only constant state. Because it avoids auxiliary arrays, it is memory efficient and performs a clean linear traversal.
Recommended for interviews: Interviewers usually expect the single-pass gradient solution. It demonstrates that you recognize the slope pattern and can maintain state while scanning once. The two-pass approach still shows strong understanding of the problem structure and is often a stepping stone toward the optimal O(1) space solution.
Approach 1: Two-Pass Approach with Peak Detection
This approach involves scanning the array to find all the peaks and then measuring the length of a mountain centered at each peak. We use two traversals: one forward scan to detect peaks and another scan to calculate maximum width of the mountains.
def longestMountain(arr):
n = len(arr)
if n < 3:
return 0
max_len = 0
i = 1
while i < n - 1:
if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
left = i - 1
right = i + 1
while left > 0 and arr[left] > arr[left - 1]:
left -= 1
while right < n - 1 and arr[right] > arr[right + 1]:
right += 1
max_len = max(max_len, right - left + 1)
i = right
else:
i += 1
return max_len
arr = [2, 1, 4, 7, 3, 2, 5]
print(longestMountain(arr))class Solution {
public int longestMountain(int[] arr) {
int n = arr.length;
if (n < 3) return 0;
int maxLen = 0;
for (int i = 1; i < n - 1; ) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
int left = i - 1, right = i + 1;
while (left > 0 && arr[left] > arr[left - 1]) left--;
while (right < n - 1 && arr[right] > arr[right + 1]) right++;
maxLen = Math.max(maxLen, right - left + 1);
i = right + 1;
} else {
i++;
}
}
return maxLen;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {2, 1, 4, 7, 3, 2, 5};
System.out.println(sol.longestMountain(arr));
}
}#include <vector>
#include <algorithm>
using namespace std;
int longestMountain(vector<int>& arr) {
int n = arr.size();
if (n < 3) return 0;
int maxLen = 0;
for (int i = 1; i < n - 1; ) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
int left = i, right = i;
while (left > 0 && arr[left] > arr[left - 1]) left--;
while (right < n - 1 && arr[right] > arr[right + 1]) right++;
maxLen = max(maxLen, right - left + 1);
i = right + 1;
} else {
i++;
}
}
return maxLen;
}
int main() {
vector<int> arr = {2, 1, 4, 7, 3, 2, 5};
printf("%d\n", longestMountain(arr));
return 0;
}function longestMountain(arr) {
const n = arr.length;
if (n < 3) return 0;
let maxLen = 0;
let i = 1;
while (i < n - 1) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
let left = i - 1;
let right = i + 1;
while (left > 0 && arr[left] > arr[left - 1]) left--;
while (right < n - 1 && arr[right] > arr[right + 1]) right++;
maxLen = Math.max(maxLen, right - left + 1);
i = right;
} else {
i++;
}
}
return maxLen;
}
const arr = [2, 1, 4, 7, 3, 2, 5];
console.log(longestMountain(arr));#include <stdio.h>
int longestMountain(int* arr, int arrSize) {
if (arrSize < 3) return 0;
int maxLen = 0;
for (int i = 1; i < arrSize - 1; ) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
int left = i - 1, right = i + 1;
while (left > 0 && arr[left] > arr[left - 1]) left--;
while (right < arrSize - 1 && arr[right] > arr[right + 1]) right++;
maxLen = fmax(maxLen, right - left + 1);
i = right + 1;
} else {
i++;
}
}
return maxLen;
}
int main() {
int arr[] = {2, 1, 4, 7, 3, 2, 5};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", longestMountain(arr, arrSize));
return 0;
}using System;
class Program {
public static int LongestMountain(int[] arr) {
int n = arr.Length;
if (n < 3) return 0;
int maxLen = 0;
for (int i = 1; i < n - 1;) {
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
int left = i - 1, right = i + 1;
while (left > 0 && arr[left] > arr[left - 1]) left--;
while (right < n - 1 && arr[right] > arr[right + 1]) right++;
maxLen = Math.Max(maxLen, right - left + 1);
i = right;
} else {
i++;
}
}
return maxLen;
}
static void Main() {
int[] arr = {2, 1, 4, 7, 3, 2, 5};
Console.WriteLine(LongestMountain(arr));
}
}The Python function adopts a similar structure to detect peaks and calculate mountain length. It manages the operation with a while loop that treats indices left and right to determine the extents of each peak-centered mountain.
Time complexity stands at O(n) as each element is assessed mainly twice. Space complexity is O(1) because only a few scalars are in use.
Approach 2: Single-Pass Approach with Gradient Tracking
This approach uses a single pass through the array to maintain both ascent and descent counts, swapping them at every ascent reset. A separate check is performed to ensure valid peaks for mountain length calculations.
def longestMountain(arr):
n = len(arr)
max_len, ascent, descent = 0, 0, 0
i = 1
while i < n:
while i < n and arr[i] == arr[i - 1]:
i += 1
while i < n and arr[i] > arr[i - 1]:
ascent += 1
i += 1
while i < n and ascent > 0 and arr[i] < arr[i - 1]:
descent += 1
i += 1
if ascent > 0 and descent > 0:
max_len = max(max_len, ascent + descent + 1)
ascent = descent = 0
return max_len
arr = [2, 1, 4, 7, 3, 2, 5]
print(longestMountain(arr))class Solution {
public int longestMountain(int[] arr) {
int n = arr.length, maxLen = 0;
int ascent = 0, descent = 0;
int i = 1;
while (i < n) {
while (i < n && arr[i] == arr[i - 1]) i++;
while (i < n && arr[i] > arr[i - 1]) ascent++,
i++;
while (i < n && ascent > 0 && arr[i] < arr[i - 1]) descent++,
i++;
if (ascent > 0 && descent > 0)
maxLen = Math.max(maxLen, ascent + descent + 1);
ascent = descent = 0;
}
return maxLen;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {2, 1, 4, 7, 3, 2, 5};
System.out.println(sol.longestMountain(arr));
}
}#include <iostream>
#include <vector>
using namespace std;
int longestMountain(vector<int>& arr) {
int i = 1, n = arr.size(), maxLen = 0, ascent = 0, descent = 0;
while (i < n) {
while (i < n && arr[i] == arr[i - 1]) i++;
while (i < n && arr[i] > arr[i - 1]) ascent++, i++;
while (i < n && ascent > 0 && arr[i] < arr[i - 1]) descent++, i++;
if (ascent > 0 && descent > 0) maxLen = max(maxLen, ascent + descent + 1);
ascent = descent = 0;
}
return maxLen;
}
int main() {
vector<int> arr = {2, 1, 4, 7, 3, 2, 5};
cout << longestMountain(arr) << endl;
return 0;
}function longestMountain(arr) {
const n = arr.length;
let maxLen = 0, ascent = 0, descent = 0, i = 1;
while (i < n) {
while (i < n && arr[i] == arr[i - 1]) i++;
while (i < n && arr[i] > arr[i - 1]) ascent++, i++;
while (i < n && ascent > 0 && arr[i] < arr[i - 1]) descent++, i++;
if (ascent > 0 && descent > 0) maxLen = Math.max(maxLen, ascent + descent + 1);
ascent = descent = 0;
}
return maxLen;
}
const arr = [2, 1, 4, 7, 3, 2, 5];
console.log(longestMountain(arr));#include <stdio.h>
int longestMountain(int* arr, int arrSize) {
int i = 1, maxLen = 0, ascent = 0, descent = 0;
while (i < arrSize) {
while (i < arrSize && arr[i] == arr[i - 1]) i++;
while (i < arrSize && arr[i] > arr[i - 1]) ascent++, i++;
while (i < arrSize && ascent > 0 && arr[i] < arr[i - 1]) descent++, i++;
if (ascent > 0 && descent > 0)
maxLen = fmax(maxLen, ascent + descent + 1);
ascent = descent = 0;
}
return maxLen;
}
int main() {
int arr[] = {2, 1, 4, 7, 3, 2, 5};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", longestMountain(arr, arrSize));
return 0;
}using System;
class Program {
public static int LongestMountain(int[] arr) {
int n = arr.Length, maxLen = 0, ascent = 0, descent = 0, i = 1;
while (i < n) {
while (i < n && arr[i] == arr[i - 1]) i++;
while (i < n && arr[i] > arr[i - 1]) ascent++;
while (i < n && ascent > 0 && arr[i] < arr[i - 1]) descent++;
if (ascent > 0 && descent > 0) maxLen = Math.Max(maxLen, ascent + descent + 1);
ascent = descent = 0;
}
return maxLen;
}
static void Main() {
int[] arr = {2, 1, 4, 7, 3, 2, 5};
Console.WriteLine(LongestMountain(arr));
}
}The Python variant blends easy syntax with extensive while loops to tally ascending and descending values, influenced by array values' relative changes. Overall, it reflects a smart cycle count.
Time complexity: O(n) through one efficient pass; space complexity: O(1) due to scarce extra requirements.
Approach 3: Default Approach
function longestMountain(arr: number[]): number {
const n = arr.length;
const f: number[] = Array(n).fill(1);
const g: number[] = Array(n).fill(1);
for (let i = 1; i < n; ++i) {
if (arr[i] > arr[i - 1]) {
f[i] = f[i - 1] + 1;
}
}
let ans = 0;
for (let i = n - 2; i >= 0; --i) {
if (arr[i] > arr[i + 1]) {
g[i] = g[i + 1] + 1;
if (f[i] > 1) {
ans = Math.max(ans, f[i] + g[i] - 1);
}
}
}
return ans;
}func longestMountain(arr []int) (ans int) {
n := len(arr)
f := make([]int, n)
g := make([]int, n)
for i := range f {
f[i] = 1
g[i] = 1
}
for i := 1; i < n; i++ {
if arr[i] > arr[i-1] {
f[i] = f[i-1] + 1
}
}
for i := n - 2; i >= 0; i-- {
if arr[i] > arr[i+1] {
g[i] = g[i+1] + 1
if f[i] > 1 {
ans = max(ans, f[i]+g[i]-1)
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pass Approach with Peak Detection | Time complexity stands at O(n) as each element is assessed mainly twice. Space complexity is O(1) because only a few scalars are in use. |
| Single-Pass Approach with Gradient Tracking | Time complexity: O(n) through one efficient pass; space complexity: O(1) due to scarce extra requirements. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Peak Detection | O(n) | O(n) | Best when clarity matters; easy to debug using explicit increasing and decreasing arrays |
| Single-Pass Gradient Tracking | O(n) | O(1) | Preferred in interviews and production due to constant memory and one traversal |
Frequently asked questions
Is Longest Mountain in Array easy or hard?
Longest Mountain in Array is considered a medium difficulty problem. The logic becomes straightforward once you recognize the increasing-then-decreasing slope pattern, but handling resets and edge cases correctly can make the implementation tricky.
Longest Mountain in Array Python/Java solution
Both Python and Java implementations typically follow the single-pass slope tracking pattern. Iterate through the array, update increasing and decreasing counters based on comparisons with the previous element, and update the maximum mountain length when both counters are positive.
How to solve Longest Mountain in Array in O(n)?
Traverse the array while tracking the length of increasing and decreasing slopes. Increase the uphill counter when values rise and the downhill counter when values fall. A valid mountain occurs when both counters are positive, and the length becomes up + down + 1. Reset counters when the slope pattern breaks.
What is the best approach for Longest Mountain in Array?
The best approach is the single-pass gradient tracking method with O(n) time and O(1) space. It scans the array once while counting increasing and decreasing slopes. When both counters are positive, a valid mountain exists and the length can be computed as up + down + 1. This avoids extra arrays and is the approach most interviewers expect.
Is Longest Mountain in Array asked at Google/Amazon/Meta?
Longest Mountain in Array is a common medium-level interview problem that appears in coding rounds at companies like Google, Amazon, and Meta. It tests pattern recognition in arrays, linear scanning techniques, and the ability to manage state transitions efficiently.
What data structure is used in Longest Mountain in Array?
The problem primarily uses arrays and simple counters. Some solutions use auxiliary arrays to track increasing and decreasing slopes, while optimized solutions maintain only two integer counters during a single pass through the input array.
What is the time complexity of Longest Mountain in Array?
The optimal solutions run in O(n) time where n is the length of the array. Each element is processed at most once during a linear scan. Some implementations use two passes with auxiliary arrays, while the most optimized version completes everything in a single pass.