Domain 1EasyCORE

Valid Mountain Array

The problem asks us to determine if an array of integers represents a valid mountain array. A mountain array must satisfy the following conditions: 1. The array length must be at least 3. 2. There exists a peak element such that all elements before it are strictly increasing, and all elements after it are strictly decreasing.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

941. Valid Mountain Array

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 33.0%


Problem Breakdown

The problem asks us to determine if an array of integers represents a valid mountain array. A mountain array must satisfy the following conditions:

  1. The array length must be at least 3.
  2. There exists a peak element such that all elements before it are strictly increasing, and all elements after it are strictly decreasing.

Inputs: An array of integers arr. Outputs: A boolean value indicating whether the array is a valid mountain array or not.

Implicit constraints:

  • The array can contain duplicate values, but they cannot be part of the increasing or decreasing sequence.
  • Negative numbers are allowed in the array.
  • Edge cases include arrays with fewer than 3 elements, arrays that are entirely non-decreasing or non-increasing, and arrays where the peak is at the start or end.

Intuition

A brute-force approach would involve checking all possible subarrays to see if they form a mountain. However, this would be inefficient with a time complexity of O(n^2). The key insight is that we can traverse the array in a single pass to determine if it forms a valid mountain. We need to find the peak and ensure that there are strictly increasing elements before the peak and strictly decreasing elements after the peak.

Approach

  1. Check if the array length is less than 3. If so, return false because a valid mountain must have at least three elements.
  2. Traverse the array to find the peak element where the sequence stops increasing.
  3. Ensure that there are no flat segments (i.e., consecutive equal elements) in the array.
  4. After finding the peak, ensure that all remaining elements are strictly decreasing.
  5. If both conditions are met, return true; otherwise, return false.

Complexity Analysis

  • Time complexity: O(n), where n is the length of the array. We traverse the array once to find the peak and then check the rest of the elements.
  • Space complexity: O(1), as we only use a few extra variables for tracking indices and flags.

Solution

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

# Example usage:
print(validMountainArray([2, 1]))      # Output: False
print(validMountainArray([3, 5, 5]))   # Output: False
print(validMountainArray([0, 3, 2, 1])) # Output: True

Edge Cases Handled

  • Arrays with fewer than 3 elements are immediately returned as false.
  • Arrays with flat segments (consecutive equal elements) are handled by the while loops, which only proceed if the current element is strictly less or greater than the next.
  • Arrays where the peak is at the start or end are caught by checking if i remains at 0 or reaches the last index after the first traversal.