Valid Mountain Array

Difficulty: Easy | Acceptance: 35.20% | Paid: No Topics: Array

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

arr.length >= 3 There exists some index i (0 < i < arr.length - 1) such that: arr[0] < arr[1] < … < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > … > arr[arr.length - 1]

• Examples
• Constraints
• Linear Scan
• Two Pointers
• State Machine

Examples

Example 1: Input: arr = [2,1] Output: false Explanation: Length is less than 3.

Example 2: Input: arr = [3,5,5] Output: false Explanation: Not strictly increasing (plateau).

Example 3: Input: arr = [0,3,2,1] Output: true Explanation: Strictly increasing to 3, then strictly decreasing.

Constraints

2 <= arr.length <= 10⁴
0 <= arr[i] <= 10⁴

Linear Scan

Intuition We can simulate the walk up and down the mountain. First, climb up while the next element is greater. Then, check if we are at a valid peak (not at the start or end). Finally, climb down while the next element is smaller. If we reach the end, it is a valid mountain.

Steps

• Initialize a pointer i at 0.
• Walk from left to right as long as arr[i] < arr[i+1], stopping at the peak.
• If the peak is at the start (i == 0) or end (i == n-1), return false.
• Walk from the peak to the end as long as arr[i] > arr[i+1].
• Return true if we reached the last element (i == n-1).

class Solution:
    def validMountainArray(self, arr: list[int]) -> bool:
        n = len(arr)
        if n < 3:
            return False
        i = 0
        
        # Walk up
        while i + 1 < n and arr[i] < arr[i + 1]:
            i += 1
            
        # Peak can't be first or last
        if i == 0 or i == n - 1:
            return False
            
        # Walk down
        while i + 1 < n and arr[i] > arr[i + 1]:
            i += 1
            
        return i == n - 1

Complexity

• Time: O(n) — We traverse the array at most twice.
• Space: O(1) — We only use a few variables.
• Notes: Simple and efficient, handles all edge cases explicitly.

Two Pointers

Intuition We can find the peak from the left and the peak from the right simultaneously. If the array is a valid mountain, both pointers should meet at the same index, and that index should not be at the boundaries.

Steps

• Initialize left = 0 and right = n - 1.
• Move left forward while arr[left] < arr[left + 1].
• Move right backward while arr[right - 1] > arr[right].
• Check if left == right and left != 0 and right != n - 1.

class Solution:
    def validMountainArray(self, arr: list[int]) -> bool:
        n = len(arr)
        if n < 3:
            return False
        left = 0
        right = n - 1
        
        # Climb from left
        while left + 1 < n and arr[left] < arr[left + 1]:
            left += 1
            
        # Climb from right
        while right > 0 and arr[right - 1] > arr[right]:
            right -= 1
            
        return left == right and left != 0 and right != n - 1

Complexity

• Time: O(n) — In the worst case, we traverse the array twice.
• Space: O(1) — Constant extra space.
• Notes: Elegant approach that validates the mountain shape from both ends.

State Machine

Intuition We can model the problem as a state machine with states: 0 (start), 1 (going up), 2 (going down), and 3 (invalid). We transition between states based on the comparison between consecutive elements.

Steps

• Initialize state = 0.
• Iterate through the array comparing arr[i] and arr[i+1].
• If arr[i] < arr[i+1]: if state is 2 (down), invalid; else set state to 1 (up).
• If arr[i] > arr[i+1]: if state is 0 (start), invalid; else set state to 2 (down).
• If arr[i] == arr[i+1]: invalid (plateau).
• Return true if final state is 2 (down).

class Solution:
    def validMountainArray(self, arr: list[int]) -> bool:
        n = len(arr)
        if n < 3:
            return False
        state = 0 # 0: start, 1: up, 2: down
        
        for i in range(n - 1):
            if arr[i] < arr[i + 1]:
                if state == 2:
                    return False
                state = 1
            elif arr[i] > arr[i + 1]:
                if state == 0:
                    return False
                state = 2
            else:
                return False
                
        return state == 2

Complexity

• Time: O(n) — Single pass through the array.
• Space: O(1) — Only state variable is used.
• Notes: Structured approach that clearly defines valid transitions.