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] <= 104Follow up:
O(1) space?The goal of Longest Mountain in Array is to identify the longest contiguous subarray that strictly increases and then strictly decreases, forming a valid "mountain". A mountain must have at least three elements with a clear peak in the middle.
A common strategy is to analyze the array using dynamic programming or two-pointer enumeration. One idea is to precompute the length of increasing sequences ending at each index and decreasing sequences starting from each index. If both values are greater than zero at a position, that index can serve as the peak of a mountain. The total mountain length can then be derived from these two values.
Another efficient method uses a two-pointer or single-pass scan to expand around potential peaks while tracking increasing and decreasing slopes. Both approaches ensure that every element is processed only a limited number of times, leading to an overall O(n) time complexity with O(n) or O(1) additional space depending on the implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (increasing & decreasing arrays) | O(n) | O(n) |
| Two Pointers / Single Pass Enumeration | O(n) | O(1) |
NeetCode
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.
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.
1#include <stdio.h>
2
3int longestMountain(int* arr, int arrSize) {
4 if (arrSize < 3) return 0;
5 int maxLen = 0;
6 for (int i = 1; i < arrSize - 1; ) {
7 if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
8 int left = i - 1, right = i + 1;
9 while (left > 0 && arr[left] > arr[left - 1]) left--;
10 while (right < arrSize - 1 && arr[right] > arr[right + 1]) right++;
11 maxLen = fmax(maxLen, right - left + 1);
12 i = right + 1;
13 } else {
14 i++;
15 }
16 }
17 return maxLen;
18}
19
20int main() {
21 int arr[] = {2, 1, 4, 7, 3, 2, 5};
22 int arrSize = sizeof(arr) / sizeof(arr[0]);
23 printf("%d\n", longestMountain(arr, arrSize));
24 return 0;
25}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.
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.
Time complexity is O(n) for a single well-managed loop, with O(1) space thanks to a fixed set of variables.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A valid mountain requires a strictly increasing sequence followed by a strictly decreasing sequence. This structure needs at least three elements: one for the ascent, one peak element, and one for the descent.
Yes, variations of this problem appear in technical interviews at large tech companies. It tests array traversal, pattern recognition, and the ability to optimize from brute force to linear-time solutions.
The optimal approach scans the array to detect increasing and decreasing slopes around potential peaks. Many solutions either precompute increasing and decreasing lengths or use a single-pass two-pointer technique. Both approaches achieve O(n) time complexity.
The problem mainly relies on array traversal rather than complex data structures. Simple arrays for dynamic programming or pointer variables for a single-pass scan are sufficient to track increasing and decreasing sequences.
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.