Longest Mountain in Array

Patrick Leaton
Published: March 20, 2021, 9:11 p.m.
Problem Description

Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

  • B.length >= 3
  • There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain. 

Return 0 if there is no mountain.

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.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

Note:

  1. 0 <= A.length <= 10000
  2. 0 <= A[i] <= 10000

Follow up:

  • Can you solve it using only one pass?
  • Can you solve it in O(1) space?

 

The description taken from https://leetcode.com/problems/longest-mountain-in-array/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def longestMountain(self, A: List[int]) -> int:
        longest = 0
        for i in range(1, len(A)-1):
            is_peak = A[i-1] < A[i] and A[i] > A[i+1]
            if is_peak:
                left, right = i-1, i+1
                while left >= 0 and A[left] < A[left + 1]:
                    left -= 1
                while right < len(A) and A[right] < A[right - 1]:
                    right += 1
                longest = max(longest, right - left - 1)
        return longest

Problem Explanation

We are given an array and are asked to find the longest subarray where the middle index is greater than its two neighbors and each additional neighbor is lesser than its previous one.  That may be an indication that two pointers can be applied to the peak and expand outward until they find a greater neighbor or another peak.

We can solve this problem by traversing the array and whenever we see a peak, which is an element that is greater than its left and right neighbors, we will descend down both sides of the peak index by using two pointers expanding outwards until they reach the bounds of the array or another peak. 

Let's start by initializing our longest mountain to zero.

        longest = 0

 

Now we can begin traversing the mountains, we'll need to start from the second index and stop second to last since we are comparing each index with the one before and after.  This way, we won't get an index out of bounds error.

        for i in range(1, len(A)-1):

 

Within each iteration, we'll check if we are at a peak index.

We will know this is the case if the current value is greater than both its left and right neighbors.

            is_peak = A[i-1] < A[i] and A[i] > A[i+1]

 

If that is the case, then we will set the left and the right pointer to the left and right of the peak index and while those pointers haven't gone outside the bounds of the array and are greater than their next neighbor, we will continue expanding them.

                left, right = i-1, i+1
                while left >= 0 and A[left] < A[left + 1]:
                    left -= 1
                while right < len(A) and A[right] < A[right - 1]:
                    right += 1

 

If the pointers' loops break, then that means they are either out of bounds or they are at the base of other mountains.  That means their current place is invalid so we will want to subtract one from their distance in our final calculation.

We'll compare that distance to the longest distance we have saved so far, updating the longest count if it is greater.

                longest = max(longest, right - left - 1)

 

Once we have traversed the entire array, we will return the longest mountain we found.

        return longest