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?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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time complexity is O(n) for a single well-managed loop, with O(1) space thanks to a fixed set of variables.
| 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. |
Leetcode 128 - LONGEST CONSECUTIVE SEQUENCE • NeetCode • 455,447 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