Longest Mountain in Array
MedPrompt
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?
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to solve the problem in linear time. We use two auxiliary arrays, up and down, to precompute the lengths of increasing subarrays ending at each index and decreasing subarrays starting at each index, respectively.
Algorithm
- Get the length
nof the array. Ifn < 3, return 0. - Create two integer arrays,
upanddown, of sizen. - Populate
up:up[i]will store the length of the strictly increasing part of a mountain ending ati. Iterate fromi = 1ton-1. Ifarr[i] > arr[i-1], setup[i] = up[i-1] + 1. - Populate
down:down[i]will store the length of the strictly decreasing part of a mountain starting ati. Iterate fromi = n-2down to0. Ifarr[i] > arr[i+1], setdown[i] = down[i+1] + 1. - Initialize
maxLength = 0. - Iterate from
i = 0ton-1. - If
up[i] > 0anddown[i] > 0, it meansarr[i]is a peak of a valid mountain. - Calculate the length:
currentLength = up[i] + down[i] + 1. - Update
maxLength = max(maxLength, currentLength). - Return
maxLength.
Walkthrough
We create two arrays, up and down, of the same size as the input array arr. up[i] will store the length of the strictly increasing subarray ending at index i, and down[i] will store the length of the strictly decreasing subarray starting at index i. We populate the up array with a forward pass and the down array with a backward pass. After populating both arrays, we iterate through the array one more time. For each index i, if it's a peak of a mountain (up[i] > 0 and down[i] > 0), the length of the mountain is up[i] + down[i] + 1. We find the maximum of these lengths over all possible peaks i.
class Solution { public int longestMountain(int[] arr) { int n = arr.length; if (n < 3) { return 0; } int[] up = new int[n]; for (int i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) { up[i] = up[i - 1] + 1; } } int[] down = new int[n]; for (int i = n - 2; i >= 0; i--) { if (arr[i] > arr[i + 1]) { down[i] = down[i + 1] + 1; } } int maxLength = 0; for (int i = 0; i < n; i++) { if (up[i] > 0 && down[i] > 0) { maxLength = Math.max(maxLength, up[i] + down[i] + 1); } } return maxLength; }}Complexity
Time
O(N). We perform three separate passes over the array, each taking `O(N)` time. The total time complexity is `O(N) + O(N) + O(N) = O(N)`.
Space
O(N). We use two additional arrays, `up` and `down`, each of size `N`.
Trade-offs
Pros
Very efficient time complexity.
The logic is straightforward, breaking the problem down into smaller subproblems.
Cons
Requires extra space proportional to the input size, which might be a concern for memory-constrained environments.
Does not meet the follow-up requirement of
O(1)space.
This approach iterates through every possible peak in the array. A peak is an element that is greater than its immediate neighbors. For each potential peak found, we expand outwards to the left and right to determine the full extent of the mountain.
Algorithm
- Initialize
maxLength = 0. - Iterate through the array with an index
ifrom1toarr.length - 2. - At each
i, check ifarr[i]is a peak:arr[i-1] < arr[i] && arr[i] > arr[i+1]. - If it is a peak:
- Initialize
left = i - 1andright = i + 1. - Expand to the left:
while (left > 0 && arr[left - 1] < arr[left]) { left--; }. - Expand to the right:
while (right < arr.length - 1 && arr[right] > arr[right + 1]) { right++; }. - Calculate the length of the current mountain:
currentLength = right - left + 1. - Update
maxLength = max(maxLength, currentLength).
- Initialize
- After the loop, return
maxLength.
Walkthrough
The core idea is that any mountain subarray must have a peak. A peak arr[i] is defined by the condition arr[i-1] < arr[i] > arr[i+1]. We can iterate through the array from the second element to the second-to-last element (i from 1 to n-2). At each index i, we check if arr[i] can be a peak. If it is, we treat it as the center of a mountain and expand in both directions. We use one pointer, l, starting from i, moving leftwards as long as the array is strictly increasing (arr[l-1] < arr[l]). We use another pointer, r, starting from i, moving rightwards as long as the array is strictly decreasing (arr[r] > arr[r+1]). The length of the mountain found is r - l + 1. We keep track of the maximum length found across all possible peaks. This process is repeated for every potential peak in the array.
class Solution { public int longestMountain(int[] arr) { int n = arr.length; if (n < 3) { return 0; } int maxLength = 0; for (int i = 1; i < n - 1; i++) { // Check if i is a peak if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) { int left = i - 1; int right = i + 1; // Expand to the left while (left > 0 && arr[left - 1] < arr[left]) { left--; } // Expand to the right while (right < n - 1 && arr[right] > arr[right + 1]) { right++; } maxLength = Math.max(maxLength, right - left + 1); } } return maxLength; }}Complexity
Time
O(N^2). The outer loop runs `N` times. In the worst-case scenario (a long, gentle slope), the inner `while` loops for expansion could also run up to `N` times for each peak.
Space
O(1). We only use a few variables to store indices and the max length.
Trade-offs
Pros
Conceptually simple and easy to implement.
It correctly identifies all mountains by checking every possible peak.
Cons
Inefficient due to its quadratic time complexity.
It may be too slow for large input arrays and could result in a "Time Limit Exceeded" error on some platforms.
It re-scans parts of the array multiple times.
This is the most efficient approach, solving the problem in a single pass through the array and using constant extra space. It works by identifying the start, peak, and end of each mountain in one go, treating the array as a sequence of upslopes and downslopes.
Algorithm
- Initialize
maxLength = 0and a pointeri = 0. - Loop while
iis less than the array length. - Let
base = i. - Find an uphill slope: check if
i+1is in bounds andarr[i] < arr[i+1]. If so, advanceias long as this condition holds. - After the uphill walk,
iis at a potential peak. Check if a downhill slope exists:i+1is in bounds andarr[i] > arr[i+1]. - If an uphill slope was found (
i > base) and a downhill slope exists, then walk down by advancingias long as the downhill condition holds. - After the downhill walk, a valid mountain from
basetoihas been found. UpdatemaxLengthwithi - base + 1. - If no mountain was found starting at
base(e.g., it was flat or only went up), simply advanceiby one to check the next position. This prevents an infinite loop. - Continue the process until the entire array is scanned.
- Return
maxLength.
Walkthrough
We iterate through the array using a single pointer i. The pointer i will effectively traverse the start, peak, and end of each mountain sequentially. The algorithm can be thought of as a state machine: find an uphill slope, then find a downhill slope. If both are found, we have a mountain. The key insight is that after processing a mountain that ends at index end, the search for the next mountain can begin at end, ensuring each element is visited only a constant number of times.
class Solution { public int longestMountain(int[] arr) { int n = arr.length; int maxLength = 0; int i = 0; while (i < n) { int base = i; // Walk up: find the start of an uphill slope if (i + 1 < n && arr[i] < arr[i + 1]) { while (i + 1 < n && arr[i] < arr[i + 1]) { i++; } // Check if we found a peak followed by a downhill if (i + 1 < n && arr[i] > arr[i + 1]) { // Walk down while (i + 1 < n && arr[i] > arr[i + 1]) { i++; } // Update maxLength for the valid mountain found maxLength = Math.max(maxLength, i - base + 1); } } // If we didn't find a mountain starting at base, or after processing one, // move to the next position. This handles plateaus and single slopes. if (i == base) { i++; } } return maxLength; }}Complexity
Time
O(N). Although there are nested loops, the main pointer `i` is never reset. It continuously moves from the beginning to the end of the array. Each element is visited at most a constant number of times.
Space
O(1). We only use a few variables to keep track of indices and the maximum length, independent of the input size.
Trade-offs
Pros
Optimal time complexity
O(N).Optimal space complexity
O(1), satisfying the follow-up question.Highly efficient as it processes the array in a single pass.
Cons
The logic can be slightly more complex to reason about compared to the DP approach due to the pointer manipulation.
Solutions
Solution
class Solution {public int longestMountain(int[] arr) { int n = arr.length; int ans = 0; for (int l = 0, r = 0; l + 2 < n; l = r) { r = l + 1; if (arr[l] < arr[r]) { while (r + 1 < n && arr[r] < arr[r + 1]) { ++r; } if (r + 1 < n && arr[r] > arr[r + 1]) { while (r + 1 < n && arr[r] > arr[r + 1]) { ++r; } ans = Math.max(ans, r - l + 1); } else { ++r; } } } return ans; }}class Solution {public: int longestMountain(vector<int> &arr) { int n = arr.size(); int ans = 0; for (int l = 0, r = 0; l + 2 < n; l = r) { r = l + 1; if (arr[l] < arr[r]) { while (r + 1 < n && arr[r] < arr[r + 1]) { ++r; } if (r + 1 < n && arr[r] > arr[r + 1]) { while (r + 1 < n && arr[r] > arr[r + 1]) { ++r; } ans = max(ans, r - l + 1); } else { ++r; } } } return ans; }};class Solution: def longestMountain(self, arr: List[int]) -> int: n = len(arr) ans = l = 0 while l + 2 < n: r = l + 1 if arr[l] < arr[r]: while r + 1 < n and arr[r] < arr[r + 1]: r += 1 if r < n - 1 and arr[r] > arr[r + 1]: while r < n - 1 and arr[r] > arr[r + 1]: r += 1 ans = max(ans, r - l + 1) else: r += 1 l = r return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.