LeetCode 941 - Valid Mountain Array

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem asks us to determine whether a given integer array forms a valid mountain array. A mountain array has a very specific structure. The values must first strictly increase until they reach a single peak, then strictly decrease after the peak.

More formally, there must exist an index i such that:

Everything before i is strictly increasing
Everything after i is strictly decreasing
The peak cannot be the first or last element

This means a valid mountain array looks like climbing uphill to a summit, then descending downhill afterward.

For example, the array [0,3,2,1] is valid because:

0 < 3
3 > 2 > 1

The value 3 acts as the mountain peak.

On the other hand, [3,5,5] is invalid because the increase is not strictly increasing. The repeated 5 violates the requirement.

The input is an integer array arr, and the output is a boolean value:

Return true if the array is a valid mountain
Return false otherwise

The constraints tell us:

The array length can be as large as 10^4
Values are non-negative integers

This size is small enough for linear solutions to run comfortably within limits. Since the problem only requires checking a pattern in the array, we should aim for an O(n) traversal.

Several edge cases are important:

Arrays shorter than length 3 can never form a mountain
Arrays that only increase are invalid
Arrays that only decrease are invalid
Arrays with equal adjacent values are invalid
The peak cannot be at index 0 or n - 1

A naive implementation can easily miss one of these conditions, especially equal adjacent elements or invalid peak placement.

Approaches

Brute Force Approach

The brute-force strategy is to test every possible index as the mountain peak.

For each index i, we can:

Check whether all elements before i are strictly increasing
Check whether all elements after i are strictly decreasing

If we find an index satisfying both conditions, we return true.

This works because the definition of a mountain array is directly based on the existence of such a peak.

However, this approach repeatedly scans large portions of the array for every candidate peak. In the worst case, this leads to quadratic time complexity.

For an array of length n, each peak check may require O(n) work, and there are O(n) candidate peaks.

Optimal Two-Pointer / Single Traversal Approach

The key observation is that we do not need to test every index independently.

A valid mountain has exactly two phases:

Strictly increasing
Strictly decreasing

We can simulate climbing the mountain:

Start from the beginning
Move upward while values increase
Once increasing stops, we should be at the peak
Then continue moving downward while values decrease

At the end:

We must have reached the last index
The peak must not be the first or last element

This works because a valid mountain contains exactly one turning point.

Instead of rescanning sections repeatedly, we process the array once in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Tries every index as a possible peak
Optimal	O(n)	O(1)	Single traversal with uphill and downhill phases

Algorithm Walkthrough

First, check whether the array length is less than 3. A mountain requires at least three elements because it needs an ascent, a peak, and a descent.
Initialize a pointer index = 0. This pointer will move through the array as we climb the mountain.
Traverse the strictly increasing portion. While the next element is larger than the current one, move the pointer forward. This simulates climbing uphill.
After the uphill traversal stops, verify that the peak is valid. The peak cannot be:

The first element, meaning no uphill movement occurred
The last element, meaning no downhill movement exists

If either condition is true, return false. 5. Traverse the strictly decreasing portion. While the next element is smaller than the current one, continue moving the pointer forward. 6. After the downhill traversal finishes, check whether the pointer reached the final index. If it did, the entire array formed one valid mountain. Otherwise, some invalid pattern exists. 7. Return whether the pointer ended at the final position.

Why it works

The algorithm maintains the invariant that the pointer always follows a valid mountain shape:

During the first phase, it only advances through strictly increasing values
During the second phase, it only advances through strictly decreasing values

If the pointer reaches the last index exactly after completing both phases, then the array satisfies the mountain definition. Any plateau, multiple peaks, or invalid ordering prevents the traversal from reaching the end correctly.

Python Solution

from typing import List

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

        if n < 3:
            return False

        index = 0

        # Walk uphill
        while index + 1 < n and arr[index] < arr[index + 1]:
            index += 1

        # Peak cannot be first or last
        if index == 0 or index == n - 1:
            return False

        # Walk downhill
        while index + 1 < n and arr[index] > arr[index + 1]:
            index += 1

        return index == n - 1

The implementation closely follows the algorithm walkthrough.

The variable n stores the array length so we can avoid repeated calls to len(arr).

The first condition handles arrays that are too short to form a mountain.

The index pointer represents our current position while traversing the mountain.

The first while loop processes the uphill section. It only advances while values strictly increase.

After the uphill phase, we validate the peak location. If the peak is at either boundary, the array cannot be a valid mountain.

The second while loop processes the downhill section. It only advances while values strictly decrease.

Finally, the function checks whether the pointer reached the last index. If not, some invalid structure interrupted the traversal.

Go Solution

func validMountainArray(arr []int) bool {
    n := len(arr)

    if n < 3 {
        return false
    }

    index := 0

    // Walk uphill
    for index+1 < n && arr[index] < arr[index+1] {
        index++
    }

    // Peak cannot be first or last
    if index == 0 || index == n-1 {
        return false
    }

    // Walk downhill
    for index+1 < n && arr[index] > arr[index+1] {
        index++
    }

    return index == n-1
}

The Go implementation mirrors the Python logic almost exactly.

Go uses for loops instead of Python while loops, but the traversal behavior remains identical.

There are no concerns about integer overflow because the problem constraints are small and we only perform comparisons.

Slices in Go already track their length, so len(arr) gives the array size efficiently.

Nil slices are handled naturally because len(nil) is 0, which correctly fails the minimum length check.

Worked Examples

Example 1

Input: [2,1]
Output: false

The array length is only 2.

Step	Action	Result
1	Check length	`n = 2`
2	`n < 3` is true	Return `false`

The array cannot form a mountain because it lacks enough elements.

Example 2

Input: [3,5,5]
Output: false

Step	Index	Comparison	Action
Start	0	`3 < 5`	Move uphill
Uphill	1	`5 < 5` is false	Stop climbing
Peak Check	1	Peak valid so far	Continue
Downhill	1	`5 > 5` is false	Cannot descend

Final state:

index = 1
n - 1 = 2

Since the traversal did not reach the last index, return false.

The equal adjacent values violate strict increasing/decreasing rules.

Example 3

Input: [0,3,2,1]
Output: true

Step	Index	Comparison	Action
Start	0	`0 < 3`	Move uphill
Uphill	1	`3 < 2` is false	Stop climbing
Peak Check	1	Valid peak	Continue
Downhill	1	`3 > 2`	Move downhill
Downhill	2	`2 > 1`	Move downhill
End	3	Reached last index	Return `true`

The array has one strict ascent and one strict descent.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is visited at most once
Space	O(1)	Only a few variables are used

The algorithm performs a single pass through the array. The pointer only moves forward and never revisits elements, so the total work is linear.

No extra data structures are required. The algorithm uses constant additional memory regardless of input size.

Test Cases

sol = Solution()

assert sol.validMountainArray([2, 1]) == False  # too short to form mountain
assert sol.validMountainArray([3, 5, 5]) == False  # plateau at peak
assert sol.validMountainArray([0, 3, 2, 1]) == True  # valid mountain

assert sol.validMountainArray([0, 1, 2, 3]) == False  # only increasing
assert sol.validMountainArray([3, 2, 1]) == False  # only decreasing

assert sol.validMountainArray([0, 1, 0]) == True  # smallest valid mountain
assert sol.validMountainArray([0, 1, 2, 1, 0]) == True  # larger valid mountain

assert sol.validMountainArray([0, 0, 1]) == False  # equal values at start
assert sol.validMountainArray([1, 2, 2, 1]) == False  # plateau in middle
assert sol.validMountainArray([1, 2, 3, 2, 2]) == False  # plateau during descent

assert sol.validMountainArray([1]) == False  # single element
assert sol.validMountainArray([1, 2]) == False  # two elements only

assert sol.validMountainArray([0, 2, 3, 4, 5, 2, 1, 0]) == True  # long valid mountain
assert sol.validMountainArray([0, 2, 3, 3, 5, 2, 1, 0]) == False  # repeated value uphill

Test Summary

Test	Why
`[2,1]`	Verifies minimum length requirement
`[3,5,5]`	Detects plateau at peak
`[0,3,2,1]`	Standard valid mountain
`[0,1,2,3]`	Rejects missing descent
`[3,2,1]`	Rejects missing ascent
`[0,1,0]`	Smallest valid mountain
`[0,1,2,1,0]`	Valid larger mountain
`[0,0,1]`	Rejects equal adjacent values
`[1,2,2,1]`	Plateau in center
`[1,2,3,2,2]`	Plateau during descent
`[1]`	Single-element boundary case
`[1,2]`	Two-element boundary case
`[0,2,3,4,5,2,1,0]`	Long valid mountain
`[0,2,3,3,5,2,1,0]`	Repeated value during ascent

Edge Cases

One important edge case is an array that only increases, such as [1,2,3,4]. A naive implementation might incorrectly assume that reaching a maximum value automatically forms a mountain. However, a valid mountain requires a descending phase after the peak. The implementation handles this by rejecting cases where the peak ends up at the final index.

Another critical edge case is equal adjacent values, such as [1,2,2,1]. Since the problem requires strictly increasing and strictly decreasing sequences, duplicate neighboring values invalidate the mountain structure. The implementation uses strict comparison operators (< and >) instead of non-strict comparisons, ensuring plateaus are rejected correctly.

A third important edge case is when the peak occurs at the beginning or end of the array. Arrays like [3,2,1] or [1,2,3] fail because they lack one side of the mountain. The implementation explicitly checks whether the peak index is 0 or n - 1, immediately rejecting such cases.

A final subtle edge case involves very short arrays, such as [1] or [1,2]. These arrays cannot possibly contain both an ascent and descent. The initial length check ensures these invalid cases are handled immediately without unnecessary traversal.