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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Mountain Array

Number: 978

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, Uber, Adobe, Flipkart

Problem Description

Given an array of integers arr, determine whether the array forms a valid mountain. A valid mountain array must have at least three elements, strictly increase to a single peak, then strictly decrease after the peak. The peak cannot be the first or last element.

Key Insights

  • The array must have at least 3 elements.
  • There must be an ascending part followed by a descending part.
  • The peak element (maximum) cannot be the first or last element.
  • Use two while loops: one for the ascent and one for the descent.
  • Verify that after the descent the pointer reaches the end of the array.

Space and Time Complexity

Time Complexity: O(n) – We traverse the array at most twice (once for the ascent and once for the descent).
Space Complexity: O(1) – Only a few extra variables are used regardless of input size.

Solution

The algorithm begins by checking that the array has at least three elements. It then walks through the array from the beginning to find the highest point where the sequence is strictly increasing. If this highest point is at the beginning or end, the array is not a valid mountain. From the peak, the algorithm continues walking through the array to ensure that all subsequent elements are strictly decreasing. If we reach the last element with these conditions satisfied, then the array forms a valid mountain. The approach uses two simple pointer iterations and constant extra space.

Code Solutions

# Define the function to check for valid mountain array
def validMountainArray(arr):
    n = len(arr)
    # The array must have at least 3 elements
    if n < 3:
        return False

    i = 0
    # Walk up: Until elements are strictly increasing
    while i + 1 < n and arr[i] < arr[i + 1]:
        i += 1

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

    # Walk down: Ensure elements are strictly decreasing
    while i + 1 < n and arr[i] > arr[i + 1]:
        i += 1

    # Check if the pointer reached the end of the array
    return i == n - 1

# Test cases
print(validMountainArray([2, 1]))      # Expected output: False
print(validMountainArray([3, 5, 5]))    # Expected output: False
print(validMountainArray([0, 3, 2, 1])) # Expected output: True
← Back to All Questions