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
iwith0 < i < arr.length - 1such 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 <= 1040 <= 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).