Blog

Introduction

• In this article, we will solve Leetcode 845, which is based on Two Pointer Solution.
• So we will see how Two pointer algorithm works.

Problem Statement

• We have been given an array and there may or may not mountain exists.
• A mountain is defined such that,
  arr[0] < arr[1] < arr[i-1] <arr[i]
  arr[i] > arr[i+1] > arr[i+2] …> arr[arr.length — 1]
• We need to return the longest mountain in the array. if we cannot find the mountain then we return 0.

Examples

Solutions

Intitution

• Our mountain has a special property where all the elements to the left are smaller than it and all the elements on the right side are smaller as well.
• So at first, we can find such an element as the Peak element.

• Once we found out such an element then, we can travel leftwards and rightwards until the next element is smaller than the current element.
  for example -> [ 2, 1, 4, 7, 3, 2, 5]

• As soon as the next element is out of the range or the next element is greater than the current element then we can stop moving in that direction and mark the count variable to store the left and right side of the length.
• Our logic would look like this

• Now we are iterating this logic for all the peaks in the array and storing the max in res variable.

Code

private int sol2(int[] arr){
        
      /**  [2,1,4,7,3,2,5] -> 
      { we find peak element -> 4<-7->3}
      go outward and measure the length,
      go left from peak until arr[left] > arr[left+1] 
      go right from peak until arr[right] > arr[right+1]
      
      then measure = left_index + right_index + 1; 
      **/
        int res = 0;
        if(arr.length < 3)  return res;
        
       for(int i=1;i<arr.length-1;i++){
           
           // find peak
         if(arr[i-1] < arr[i] && arr[i] > arr[i+1]){
           
               int left = i;
               int count = 1;
               // go left 
               while(left>0 && arr[left] > arr[left-1]){
                   left--;
                   count++;
               }

               int right = i;
               // go right
               while(right < arr.length-1 && arr[right] > arr[right+1]){
                   right++;
                   count++;
               }

               res = Math.max(res, count);
        }
       }
        
        return res;
        
    }

Result 

• Our solution is accepted by Leetcode

Complexity

• Time Complexity: O(N) , N is length of array.
   we are traversing the entire array only once.
• Space Complexity : O(1) since we are using constant space

Conclusion

• In this article, we solved Leetcode 845 problem that help us understand how we can use a two-pointer.

Entire Source Code

• The entire source code is available at GitHub.
  

Bonus Tip

• If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )

Further Reading

• DSA Blogs : https://asyncq.com/category/dsa