LeetCode 941. Valid Mountain Array

Description

https://leetcode.com/problems/valid-mountain-array/

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

Explanation

We can have two pass to check if array is valid mountain. The first pass stops at the peak of mountain, the second pass find if all the elements remaining were smaller than the peak element.

Python Solution

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        if len(arr) < 3:
            return False
        
        
        prev = None
        max_index = None
        for i, num in enumerate(arr):
            if prev != None and num <= prev:
                break

            prev = num
            max_index = i
        
        
        if max_index == 0 or max_index == len(arr) - 1:
            return False
        
        for i, num in enumerate(arr[max_index + 1:]):
            if num >= prev:
                print (num, prev)
                return False
            
            prev = num
            
        return True
            
            
                
  • Time Complexity: O(N).
  • Space Complexity: O(1).

Leave a Reply

Your email address will not be published.