LeetCode 941: Valid Mountain Array

Problem Restatement

We are given an integer array arr.

Return True if and only if arr is a valid mountain array.

A valid mountain array must satisfy three rules:

1. It has at least 3 elements.
2. It strictly increases up to one peak.
3. It strictly decreases after that peak.

The peak cannot be the first element or the last element.

The official statement defines a mountain array as one where there exists an index i with 0 < i < arr.length - 1, such that values strictly increase before i and strictly decrease after i.

Input and Output

Function shape:

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

Examples

Example 1:

arr = [2, 1]

The length is less than 3.

So the answer is:

False

Example 2:

arr = [3, 5, 5]

The array increases from 3 to 5, but then has another 5.

A mountain must be strictly increasing and strictly decreasing. Equal adjacent values are not allowed.

So the answer is:

False

Example 3:

arr = [0, 3, 2, 1]

The array increases:

0 -> 3

Then decreases:

3 -> 2 -> 1

The peak is 3, which is neither first nor last.

So the answer is:

True

First Thought: Find the Peak

A valid mountain has one peak.

So we can first walk upward while the next value is larger.

When that stops, we should be at the peak.

Then we walk downward while the next value is smaller.

At the end, the array is valid only if:

1. We climbed at least once.
2. We descended at least once.
3. We reached the end of the array.

Key Insight

The strict comparisons matter.

The increasing phase uses:

arr[i] < arr[i + 1]

The decreasing phase uses:

arr[i] > arr[i + 1]

If two adjacent values are equal, neither condition is true, so the scan stops.

That correctly rejects arrays like:

[3, 5, 5]

or:

[0, 2, 2, 1]

Algorithm

Let:

n = len(arr)

If n < 3, return False.

Start at index 0.

Climb while the next value is larger:

while i + 1 < n and arr[i] < arr[i + 1]:
    i += 1

After this loop, i is the peak candidate.

If i == 0, there was no increasing part.

If i == n - 1, there was no decreasing part.

In either case, return False.

Then descend while the next value is smaller:

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

At the end, return whether i reached the last index.

Walkthrough

Use:

arr = [0, 3, 2, 1]

Start:

i = 0

Climb:

Peak candidate is index 1, value 3.

It is not the first or last index, so continue.

Descend:

Now i == n - 1.

Return:

True

Correctness

The first loop advances exactly through the longest strictly increasing prefix of the array.

When it stops, either the array ended or the next value is not larger. Therefore, the current index is the only possible peak position for a mountain shape.

If that peak candidate is index 0, then the array never increased. A valid mountain requires an increasing part, so the array is invalid.

If that peak candidate is index n - 1, then the array never decreased. A valid mountain requires a decreasing part, so the array is invalid.

The second loop advances exactly through the longest strictly decreasing suffix starting at the peak candidate.

If the second loop reaches the final index, then every element after the peak strictly decreases, so the array has the required mountain form.

If it stops before the final index, then some adjacent pair after the peak fails the strict decreasing rule. Therefore, the array cannot be a valid mountain.

So the algorithm returns True exactly for valid mountain arrays.

Complexity

Implementation

class Solution:
    def validMountainArray(self, arr: list[int]) -> bool:
        n = len(arr)

        if n < 3:
            return False

        i = 0

        while i + 1 < n and arr[i] < arr[i + 1]:
            i += 1

        if i == 0 or i == n - 1:
            return False

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

        return i == n - 1

Code Explanation

We first reject arrays that are too short:

if n < 3:
    return False

Then we climb the increasing part:

while i + 1 < n and arr[i] < arr[i + 1]:
    i += 1

After climbing, the peak must be inside the array:

if i == 0 or i == n - 1:
    return False

Then we walk down the decreasing part:

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

The array is valid only if this walk reaches the end:

return i == n - 1

Testing

def run_tests():
    s = Solution()

    assert s.validMountainArray([2, 1]) is False
    assert s.validMountainArray([3, 5, 5]) is False
    assert s.validMountainArray([0, 3, 2, 1]) is True

    assert s.validMountainArray([0, 1, 2, 3]) is False
    assert s.validMountainArray([3, 2, 1]) is False
    assert s.validMountainArray([0, 2, 3, 2, 1]) is True
    assert s.validMountainArray([0, 2, 2, 1]) is False
    assert s.validMountainArray([1, 3, 2]) is True

    print("all tests passed")

run_tests()