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 <vector>
2#include <algorithm>
3using namespace std;
4
5int longestMountain(vector<int>& arr) {
6 int n = arr.size();
7 if (n < 3) return 0;
8 int maxLen = 0;
9 for (int i = 1; i < n - 1; ) {
10 if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
11 int left = i, right = i;
12 while (left > 0 && arr[left] > arr[left - 1]) left--;
13 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;
}The C++ solution follows the same logic, utilizing standard libraries for vector manipulation. The code finds peaks and then determines the extent of the mountain using a left and right index, updating the maximum mountain length found so far.
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
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));
}
}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.
The C# approach iterates using typical logical controls, maintaining ascent and descent variables to facilitate efficient mountain detection throughout the array iteration.