0845.Longest Mountain in Array

Link: 845. Longest Mountain in Array - Medium
Track: Amazon Tag

Question

Restate

• Q: Duplicate number: yes

Edge Case

• no mountain, return 0
• len(arr) < 3, reurn 0
• [2,2,3,2,2], return 3

---

Method 1 - (Optimal) Scan
Method 2 - Two pointer

Method 1

Approach

Use a pointer peak to scan from left to right:

1. Identify a peak: arr[peak-1] < arr[peak] > arr[peak+1].
2. If it’s a peak, expand:
   • Move left leftward
     • while the slope is strictly increasing (arr[left-1] < arr[left]).
   • Move right rightward
     • while the slope is strictly decreasing (arr[right] > arr[right+1]).
3. Update the best answer with right - left + 1.
4. Skip the whole mountain by setting peak = right + 1 to avoid rescanning.

Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

Code

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        if n < 3:
            return 0
        
        peak = 1
        res = 0
        while peak < n - 1:
            
            if arr[peak - 1] < arr[peak] and arr[peak] > arr[peak + 1]:
                left = peak - 1
                while left > 0 and arr[left - 1] < arr[left]:
                    left -= 1
                right = peak + 1
                while right < n - 1 and arr[right + 1] < arr[right]:
                    right += 1
                
                res = max(res, right - left + 1)
                peak = right + 1
            else:
                peak += 1
        
        return res
 
 

Method 2

Complexity

• Time Complexity: O($n^2$)
• Space Complexity: O(1)

Code

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        
        n = len(arr)
        if n < 3:
            return 0
 
        def expend(peak): 
            left = peak - 1  
            right = peak + 1
            
            while left >= 0:               
                if arr[left] < arr[left + 1]:
                    left -= 1 
                else:
                    break
 
            while right < n:
                if arr[right] < arr[right - 1]: 
                    right += 1           
                else:
                    break 
            
            if peak == right - 1:
                return 0
            if peak == left + 1:
                return 0
            return right - left - 1
            
        res = 0
        for peak in range(1, n - 1):
            if arr[peak - 1] < arr[peak] and arr[peak] > arr[peak + 1]:
                mountain = expend(peak)
                res = max(res, mountain)
        
        return res if res >= 3 else 0

---

History

• Feb-17-2026 Peeked