Longest Mountain in Array

The mountain at index i in array arris defined such that

arr[i-N]..arr[i-1]< arr[i] > arr[i+1] arr[i+N] 

where i cannot be 0 and arr.length-1 which means that the index(i) cannot be at the extreme ends in the array (start and end of an array). Given an array A of integers, return the length of the longest mountain.  Return 0 if there is no mountain. Minimum length of a mountain subarray should 3.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Thought process

Question is to find the mountain which has longest length which means the length of the increasing array ending at arr[i] + the length of the decreasing array starting at arr[i] should be longest among all the mountains in an array, then we can return that length as longest mountain length.

Also if there is a flattening curve as in case of [2,3,3] there is no peak, the flat curve will not be a part of a mountain. The answer for [2,3,3] is 0. Here are couple of inputs and expected answers. This is a good clarifying question in an interview.

Idea is that for each index i, we will keep a track of how many numbers are there towards the left of the indexiare in increasing order and how many numbers on the right side of the index i, which are in decreasing order. If the length of the mountain with index i has its peak is longer than earlier seen mountains, we update the longest length.

It is important to note that both side subarray should be monotonically increasing and decreasing. As soon as we hit a flat curve (consecutive duplicates numbers), the duplicate elements can not part of the mountain array .

Also note that we jump the left to the next number to the mountain array, because no index in this mountain array will make a bigger mountain than the current one. See why?

show me the solution

 public int longestMountain(int[] arr) {
        
        if(arr==null || arr.length<3) return 0;
        
        int left=1;
        int len=arr.length-1;
        int ans=0;
        
       while(left<=len){
           
           int upHill=0;
           int downHill=0;
           
           // if there are duplicates on the left ,
           //they wont be the part of the mountain
           while(left<=len && arr[left]==arr[left-1]) left++;
           
           while(left<=len && arr[left]>arr[left-1]) {
               upHill++;
               left++;
           }
           
           while(left<=len && arr[left]<arr[left-1]) {
               downHill++;
               left++;
           }
           
           // if the sequence is 2, 3, 3, 5 , then the 
           // downHill will not be greter than 0 at left = 2
           if(upHill>0 && downHill>0) {
               ans=Math.max(ans,upHill+downHill+1);
           }
           
       }
        return ans;
    }

The time complexity of the implementation is O(n)

.