Sponsored
Sponsored
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.
1def longestMountain(arr):
2 n = len(arr)
3 if n < 3:
4 return 0
5 max_len = 0
6 i = 1
7 while i < n - 1:
8 if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
9 left = i - 1
10 right = i + 1
11 while left > 0 and arr[left] > arr[left - 1]:
12 left -= 1
13 while right < n - 1 and arr[right] > arr[right + 1]:
14 right += 1
15 max_len = max(max_len, right - left + 1)
16 i = right
17 else:
18 i += 1
19 return max_len
20
21arr = [2, 1, 4, 7, 3, 2, 5]
22print(longestMountain(arr))The Python function adopts a similar structure to detect peaks and calculate mountain length. It manages the operation with a while loop that treats indices left and right to determine the extents of each peak-centered mountain.
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
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.