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#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.
1using System;
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));
}
}The C# approach iterates using typical logical controls, maintaining ascent and descent variables to facilitate efficient mountain detection throughout the array iteration.