Longest Mountain in Array
- 3 min read
- LC-Medium
- Two Pointers
3 years ago
Solution - O(n)
- Single loop, however at each loop, check all 3 conditions for a mountain:
-
- Increasing slope
-
- One one peak point (i.e. no flat tops)
-
- Decrease slope after peak
-
- Just check the code, you will understand
- The condition
i > startis just to check if ouripointer moved. If it did not move, it means we did not see an increasing slope - The secondary condition after that just checks to see if the very next point is decreasing. This condition both lets us skip flat tops and non-inclines
| Time | Space | Explanation |
|---|---|---|
O() | O() |
function longestMountain(arr: number[]): number {
const n = arr.length;
let i = 0;
let longest_mountain = 0;
while (i < n) {
let start = i;
while ((i + 1) < n && arr[i + 1] > arr[i]) {
i++;
}
if(i > start && (i + 1) < n && arr[i + 1] < arr[i]) {
let j = i;
while ((j + 1) < n && arr[j + 1] < arr[j]) {
j++;
}
longest_mountain = Math.max(longest_mountain, j - start + 1);
i = j;
} else {
i++;
}
}
return longest_mountain;
};
O(n^2) solution
- Go through each number in the list, assume each number could be a peak
- At each point, keep expanding till mountain conditions are valid (i.e. both left and right strictly decrease)
- Whenever this condition is violated, stop expanding
- Another edge case we need to be mindful of is the fact that a mountain should slope both ways
- We do an initial check to see if the current point is a minimal mountain (i.e. 3 points long and slope down both ways), this way, when we later update
longest_mountain, it is in fact the longest mountain - TC - O(n^2)
function longestMountain(arr: number[]): number {
let longest_mountain = 0;
for(let i = 1; i < arr.length - 1; i++) {
if (arr[i - 1] >= arr[i] || arr[i] <= arr[i + 1]) {
continue;
}
let l = i;
while ((l - 1) >= 0 && arr[l - 1] < arr[l]) {
l--;
}
let r = i;
while((r + 1) <= arr.length - 1 && arr[r + 1] < arr[r]) {
r++;
}
longest_mountain = Math.max(longest_mountain, r - l + 1);
}
return longest_mountain;
};