Firstly i couldn't solve on my own š , so i went through this video
U can visualize the mountains of this problem as shown in this image
You can see 2 mountains in this image , But which is biggest mountain , its not the one whose peak value is more but the mountain which is formed by many points . ie in this image its the first mountain because it is formed by 6 points where as the other is formed by only 4 points
so the answer will be 6 !!
How can we say it's a mountain ? , it's a mountain if it has a peak . ok now how can we say it has peak ? , it's a peak if its value is greater than it's neighbour's
In code it goes like
arr[i] >arr[i-1] && arr[i]>arr[i+1]
where arr is the give array
and i goes from 1 to n-2 , ok but why n-2 , because n-1 is the index of last element and we cant have a peak at last element.
Ok now we got the peak now we calculate how many points its made of , to do this we need to traverse left first and then to right , while we traverse we keep and counter and increment its value .
In code it goes like
For traversing left side of mountain
_
let j = i
let points = 1;
while(j>0 && arr[j]> arr[j-1]){
j--;
points++;
}
Here i is the peak point index we got.
For traversing right side of mountain
while(i<n-1 && arr[i] > arr[i+1]){
i++;
points++;
}
Now we need to find mountain which has max points
so for that we declare a var outside and keep overriding it with the max value
so finally the entire code is
/**
* @param {number[]} arr
* @return {number}
*/
var longestMountain = function(arr) {
const n = arr.length;
let ans = 0;
for(let i = 1 ; i <= n-2 ;){
if(arr[i] >arr[i-1] && arr[i]>arr[i+1]){ // greater than both neighbours
//is peak point
//traverse and find length
let j = i
let points = 1;
while(j>0 && arr[j]> arr[j-1]){
j--;
points++;
}
while(i<n-1 && arr[i] > arr[i+1]){
i++;
points++;
}
ans = Math.max(points, ans)
}else{
i++
}
}
return ans
};
Please do follow the series if you are struggling with leetcode questions š
Top comments (0)