We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Mountain Array

Difficulty: Easy

Problem Description

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

  • arr.length >= 3
  • There exists some i with 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]

Key Insights

  • The array must first strictly increase to a peak and then strictly decrease.
  • The peak must not be at the ends of the array (i.e., the first and last elements).
  • Both parts (increasing and decreasing) must contain at least one element.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the array, because we traverse the array once. Space Complexity: O(1) - no additional space is used that grows with input size.

Solution

To determine if the array is a valid mountain array, we can use a two-pass approach:

  1. Traverse the array from the start to find the peak. Ensure that each subsequent element is greater than the previous one until we reach the peak.
  2. Traverse the array from the peak to the end to ensure that each subsequent element is less than the previous one.

If we find a valid peak and both conditions are satisfied, we can return true; otherwise, we return false.

Code Solutions

def validMountainArray(arr):
    n = len(arr)
    if n < 3:
        return False

    i = 0
    # Climb up to the peak
    while i + 1 < n and arr[i] < arr[i + 1]:
        i += 1

    # Check if peak is at the start or end
    if i == 0 or i == n - 1:
        return False

    # Climb down from the peak
    while i + 1 < n and arr[i] > arr[i + 1]:
        i += 1

    # If we reach the end, it's a valid mountain array
    return i == n - 1
← Back to All Questions