Valid Mountain Array — Leetcode 941 — Solution
Problem asked in Google and Amazon Interview
In this article, we will see how we can solve Leetcode 941 — Valid Mountain Array in One Pass. The difficulty of the problem is Easy.
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
with0 < 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
Solution
We will see the array as a mountain that we can climb on from both sides.
We are going to traverse from both sides in other words we will start climbing from both sides and if they meet at the same point then that means it’s a Valid Mountain Array and i should be greater than 0 also j should be less than n(n is the length of the array).
Code
def validMountainArray(arr: List[int]) -> bool:
n = len(arr)
if n < 3:
return False
i, j = 0, n - 1
while i + 1 < n and arr[i] < arr[i + 1]:
i += 1
while j > 0 and arr[j] < arr[j - 1]:
j -= 1
return i == j and 0 < i and j < n - 1
Complexity Analysis
The time complexity of the following solution will be O(N) where N is the length of the array and space complexity will be O(1) because we are not using any extra space.