941. Valid Mountain Array

• python3
• Review : 20240704

📎 Problem

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]

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

Constraints:

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 104

Pseudocode

1. check arr.length
2. set left pointer starting from zero
3. set right pointer starting from end of the array
4. check strictly increasing with left pointer
5. check strictly decreasing with right pointer
6. compare the two pointers

Code

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:

        if len(arr) < 3:
            return False
        left = 0
        right = len(arr) - 1
        while left + 1 < len(arr) - 1 and arr[left] < arr[left + 1]:
            left += 1
        while right - 1 > 0 and arr[right] < arr[right - 1]:
            right -= 1

        return left == right

Result

• Time Complexity : O(N) as we are traveling the array only once.
• Space Complexity : O(1) as we are not using any extra space.

Review

I usually don't consider the two-pointers technique. My skills will improve significantly by solving many more problems...