LeetCode 845: Longest Mountain in Array

Problem Restatement

We are given an integer array arr.

A mountain is a contiguous subarray that:

Rule	Meaning
Length	Has at least 3 elements
Up slope	Strictly increases before the peak
Peak	Has one element greater than both neighbors
Down slope	Strictly decreases after the peak

Return the length of the longest mountain.

If there is no mountain, return 0.

Input and Output

Item	Meaning
Input	Integer array arr
Output	Length of the longest mountain subarray
Subarray	Must be contiguous
Strictness	Equal adjacent values break a mountain
Minimum length	3

Function shape:

class Solution:
    def longestMountain(self, arr: list[int]) -> int:
        ...

Examples

Example 1:

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

The longest mountain is:

[1, 4, 7, 3, 2]

It strictly increases:

1 < 4 < 7

Then strictly decreases:

7 > 3 > 2

Its length is:

5

So the answer is:

5

Example 2:

arr = [2, 2, 2]

There is no strict increase or strict decrease.

So the answer is:

0

First Thought: Check Every Subarray

A brute force solution is to try every subarray of length at least 3.

For each subarray:

1. Find whether there is a valid peak.
2. Check that values strictly increase before the peak.
3. Check that values strictly decrease after the peak.
4. Update the best length.

This works, but it is too slow because there are many subarrays.

Problem With Brute Force

There are O(n^2) subarrays.

Checking whether one subarray is a mountain can take O(n) time.

So the total time can become:

O(n^3)

We need to use the structure of a mountain directly.

Key Insight

Every mountain has a peak.

A peak is an index i such that:

arr[i - 1] < arr[i] > arr[i + 1]

Once we find a peak, we can expand left while the values are strictly increasing toward the peak, and expand right while the values are strictly decreasing away from the peak.

That gives the full mountain centered at this peak.

Algorithm

Scan the array from left to right.

For each index i from 1 to n - 2:

1. Check whether i is a peak.
2. If not, continue.
3. If it is a peak:
   1. Move left left while arr[left - 1] < arr[left].
   2. Move right right while arr[right] > arr[right + 1].
   3. Compute the mountain length:

      right - left + 1
      

   4. Update the answer.
   5. Move i to right because all indices inside this mountain have already been handled.

Walkthrough

Use:

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

Check index 1:

2, 1, 4

1 is not a peak.

Check index 2:

1, 4, 7

4 is not a peak.

Check index 3:

4, 7, 3

7 is a peak.

Expand left:

1 < 4 < 7

Expand right:

7 > 3 > 2

The mountain is:

[1, 4, 7, 3, 2]

Its length is:

5

The answer becomes 5.

No later longer mountain exists, so return:

5

Correctness

A valid mountain must have a peak, because it must strictly increase first and strictly decrease afterward. Therefore, the maximum mountain can be found by checking possible peak positions.

When the algorithm finds a peak i, it expands left exactly while the slope remains strictly increasing toward i. It stops at the first position where extending farther would break strict increase or leave the array.

It expands right exactly while the slope remains strictly decreasing away from i. It stops at the first position where extending farther would break strict decrease or leave the array.

So the interval [left, right] is exactly the longest mountain with peak i.

The algorithm checks every possible peak or skips only indices already inside a mountain whose full right boundary has been processed. Such skipped indices cannot start a longer mountain with a different peak inside the same strictly decreasing side.

Thus every valid mountain's peak is considered, and the maximum length recorded is the length of the longest mountain.

Complexity

Metric	Value	Why
Time	O(n)	Each index is scanned a constant number of times
Space	O(1)	Only pointers and counters are used

Implementation

class Solution:
    def longestMountain(self, arr: list[int]) -> int:
        n = len(arr)
        answer = 0
        i = 1

        while i < n - 1:
            is_peak = arr[i - 1] < arr[i] > arr[i + 1]

            if not is_peak:
                i += 1
                continue

            left = i
            right = i

            while left > 0 and arr[left - 1] < arr[left]:
                left -= 1

            while right + 1 < n and arr[right] > arr[right + 1]:
                right += 1

            answer = max(answer, right - left + 1)
            i = right

        return answer

Code Explanation

We start checking from index 1 because a peak cannot be the first element:

i = 1

A valid peak must have a smaller neighbor on both sides:

is_peak = arr[i - 1] < arr[i] > arr[i + 1]

If i is not a peak, move forward:

i += 1

If i is a peak, expand left:

while left > 0 and arr[left - 1] < arr[left]:
    left -= 1

Then expand right:

while right + 1 < n and arr[right] > arr[right + 1]:
    right += 1

The mountain length is:

right - left + 1

After processing this mountain, we move i to right:

i = right

The next loop iteration will advance from there if it is not a peak.

Testing

def run_tests():
    s = Solution()

    assert s.longestMountain([2, 1, 4, 7, 3, 2, 5]) == 5
    assert s.longestMountain([2, 2, 2]) == 0
    assert s.longestMountain([1, 2, 3]) == 0
    assert s.longestMountain([3, 2, 1]) == 0
    assert s.longestMountain([1, 2, 1]) == 3
    assert s.longestMountain([1, 2, 3, 2, 1, 2, 3, 4, 1]) == 5
    assert s.longestMountain([1, 2, 2, 1]) == 0

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Standard example	Confirms normal mountain detection
All equal	Confirms strictness
Only increasing	Confirms no down slope
Only decreasing	Confirms no up slope
Minimum mountain	Confirms length 3 is valid
Multiple mountains	Confirms longest one is returned
Plateau near peak	Confirms equal adjacent values break a mountain