Longest Mountain in Array

Intuition

Every mountain has exactly one crest. If you locate a crest, the whole mountain is uniquely determined: walk left while the values keep rising toward the crest and walk right while they keep falling away from it. After measuring one mountain, you can jump past it because its downslope cannot serve as another mountain's upslope, keeping the whole process linear.

Algorithm walkthrough

1. 1Start an index at position 1 so it always has a left and right neighbour to compare.
2. 2If the current element is strictly greater than both neighbours, it is a peak; set left and right pointers to the neighbours.
3. 3Slide the left pointer down while the slope keeps rising and slide the right pointer up while the slope keeps falling.
4. 4Record the window width if it beats the best seen, then resume scanning just past the right edge of this mountain.
5. 5If the current element is not a peak, simply advance by one and keep looking.

Implementation

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