LeetCode 845: Longest Mountain in Array

Problem Restatement

We are given an integer array arr.

A mountain is a contiguous subarray that:

Return the length of the longest mountain.

If there is no mountain, return 0.

Input and Output

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

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: