LeetCode 941: Valid Mountain Array

Description

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 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]

Constraints

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Examples

• Example 1:
  Input: arr = [2, 1]
Output: false
• Example 2:
  Input: arr = [3, 5, 5]
Output: false
• Example: 3
  Input: arr = [0, 3, 2, 1]
Output: true

Solution 1: One Pass

Steps

1. Base Case: According to the definition of a mountain array, if the length of the array arr is less than 3 or if arr is in a descending state from the beginning (arr[0] > arr[1]), we can directly return False here.
2. Declare a variable peak_reached to indicate whether we have reached the peak.
3. Iterate through the arr:
   1. If the current element arr[i] is equal to the next element arr[i + 1], according to the definition, this is an invalid mountain array, so we can directly return False here.
   2. If the current element arr[i] is greater than the next element arr[i + 1], it means we have reached the peak, and the subsequent elements can only be in descending order. Set peak_reached to True in this case.
   3. Otherwise, if we have already reached the peak (peak_reached is True), but the current element arr[i] is smaller than the next element arr[i + 1], it means we are climbing the mountain again, which is invalid according to the definition of a mountain array. In this case, we can directly return False.
4. After the iteration is complete, return peak_reached to ensure that we have reached the peak at some point because a strictly increasing (monotone increasing) array is not a valid mountain array.

Codes

def valid_mountain_array(arr: List[int]) -> bool:
    if len(arr) < 3 or arr[0] > arr[1]:
        return False

    peak_reached = False
    for i in range(len(arr) - 1):
        if arr[i] == arr[i + 1]:
            return False
        elif arr[i] > arr[i + 1]:
            peak_reached = True
        else:
            if peak_reached:
                return False

    return peak_reached

Complexities

• Time Complexity: O(N), where N is the length of the arr array.
• Space Complexity: O(1)

References

• LeetCode link: Valid Mountain Array – LeetCode