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.
1
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.
1def longestMountain(arr):
2 n = len(arr)
3 max_len, ascent, descent = 0, 0, 0
4 i = 1
5 while i < n:
6 while i < n and arr[i] == arr[i - 1]:
7 i += 1
8 while i < n and arr[i] > arr[i - 1]:
9 ascent += 1
10 i += 1
11 while i < n and ascent > 0 and arr[i] < arr[i - 1]:
12 descent += 1
13 i += 1
14 if ascent > 0 and descent > 0:
15 max_len = max(max_len, ascent + descent + 1)
16 ascent = descent = 0
17 return max_len
18
19arr = [2, 1, 4, 7, 3, 2, 5]
20print(longestMountain(arr))The Python variant blends easy syntax with extensive while loops to tally ascending and descending values, influenced by array values' relative changes. Overall, it reflects a smart cycle count.