Leetcode – Valid Mountain Array Solution in Python

Spread the love

In this comprehensive article, we aim to unpack the Valid Mountain Array problem, shed light on the conceptual underpinnings, and present a Python-based solution.

Problem Statement

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 i (0-indexed) 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]

Problem Insights

A valid mountain array can be visualized as a sequence that strictly increases to a peak, and then strictly decreases after the peak. It’s akin to climbing a mountain from its base to its peak and then descending to the other base.

Algorithm to Solve the Problem

  1. Traverse the array until you reach the peak (i.e., the next number is smaller than the current one).
  2. Check if the peak is neither the first nor the last element.
  3. Continue traversing and ensure that the rest of the array is in a strictly decreasing order.
  4. If the end of the array is reached under these conditions, then it’s a valid mountain array.

Python Code Solution

Here’s how you can implement the solution in Python:

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

    i = 0

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

    # Check if we are at the beginning or end of the array
    if i == 0 or i == n - 1:
        return False

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

    # If we reached the end, it's a valid mountain array
    return i == n - 1

Complexity Analysis

  • Time Complexity: O(N) – The algorithm traverses the entire array once, where N is the number of elements in the array.
  • Space Complexity: O(1) – The solution only uses a constant amount of extra space irrespective of the input size.

Testing the Solution

It’s always crucial to validate the solution using various test cases:

print(validMountainArray([2, 1]))         # Expected output: False (Too short)
print(validMountainArray([3, 5, 5]))      # Expected output: False (Plateau is not allowed)
print(validMountainArray([0, 3, 2, 1]))   # Expected output: True (Valid mountain array)
print(validMountainArray([0, 1, 2, 3, 5, 4, 3, 2, 0]))  # Expected output: True (Valid mountain array)
print(validMountainArray([0, 1, 2, 3, 5, 6, 7]))        # Expected output: False (No descent)

Conclusion

The “Valid Mountain Array” problem offers a nuanced take on array traversal by introducing conditions that need to be satisfied throughout the journey. It’s a testament to the fact that even simple problems can sometimes be dressed in slightly complex narratives. The crux of solving such problems lies in understanding the requirements and ensuring that the algorithm caters to all the edge cases.

Leave a Reply