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

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.