You may recall that an array arr is a mountain array if and only if:
arr.length >= 3i (0-indexed) with 0 < i < arr.length - 1 such 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:
O(1) space?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.
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.
The C solution iterates through the array looking for peaks (where arr[i] is greater than its neighbors). Upon finding a peak, it expands outwards to calculate the total length of the mountain by decrementing and incrementing indices as long as the mountain shape holds. The maxLen keeps track of the longest mountain found.
Time complexity is O(n) as each element is processed at most twice. Space complexity is O(1) since we use only a few extra variables.
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.
This C implementation leverages variable ascent to track climbing phase and descent for descent. A valid mountain forms when both ascent and descent qualities exceed zero. The inner loop skips flat sections to align with mountain criteria.
Time complexity is O(n) for a single well-managed loop, with O(1) space thanks to a fixed set of variables.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Two-Pass Approach with Peak Detection | Time complexity is O(n) as each element is processed at most twice. Space complexity is O(1) since we use only a few extra variables. |
| Single-Pass Approach with Gradient Tracking | Time complexity is O(n) for a single well-managed loop, with O(1) space thanks to a fixed set of variables. |
| Default Approach | — |
| 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 |
Longest Mountain in Array Leetcode 845 || Medium • Code with Alisha • 15,841 views views
Watch 9 more video solutions →Practice Longest Mountain in Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor