DEV Community

Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu

Posted on • Updated on

Leetcode - 845. Longest Mountain in Array

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

Image description

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]
Enter fullscreen mode Exit fullscreen mode

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++;
        }
Enter fullscreen mode Exit fullscreen mode

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++;
        }
Enter fullscreen mode Exit fullscreen mode

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
};
Enter fullscreen mode Exit fullscreen mode

Image description
Please do follow the series if you are struggling with leetcode questions 😇

Top comments (0)