MediumArraysSliding WindowTwo Pointers

Longest Mountain in Array

1 approach, code in every language

A mountain inside an array is a run of at least three elements that first climbs strictly upward to a single peak and then falls strictly downward. Given an integer array, determine the length of the longest such mountain, and return 0 when the array holds no mountain at all.

The trick is to treat every strict peak as the crest of a potential mountain and stretch outward in both directions as long as the strict up-then-down shape holds.

Example 1

Input: arr = [2,1,4,7,3,2,5]

Output: 5

The stretch 1,4,7,3,2 rises to the peak 7 and then descends, spanning five elements.

Example 2

Input: arr = [2,2,2]

Output: 0

No element ever rises above its neighbours, so there is no valid peak and no mountain.

Constraints

1 ≤ arr.length ≤ 10^4
0 ≤ arr[i] ≤ 10^4

Expand around each peak

Scan for positions that are strictly greater than both neighbours, then widen the window left and right along the strictly increasing and decreasing slopes.

Loading animation…

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

1Start an index at position 1 so it always has a left and right neighbour to compare.
2If the current element is strictly greater than both neighbours, it is a peak; set left and right pointers to the neighbours.
3Slide the left pointer down while the slope keeps rising and slide the right pointer up while the slope keeps falling.
4Record the window width if it beats the best seen, then resume scanning just past the right edge of this mountain.
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

Time

O(n)

Space

O(1)

After a mountain is measured the scan jumps past it, so every element is visited a constant number of times.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Longest Ridge in the Profile is our own problem on the technique behind Longest Mountain in Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free