[Arrays] Valid Mountain Array

📋 This is my note-taking from what I learned in LeetCode!

Problem

Problem Link

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 <= 10^4
• 0 <= arr[i] <= 10^4

Hint #1:

It’s very easy to keep track of a monotonically increasing or decreasing ordering of elements. You just need to be able to determine the start of the valley in the mountain and from that point onwards, it should be a valley i.e. no mini-hills after that. Use this information in regards to the values in the array and you will be able to come up with a straightforward solution.

Solution

Solution Link

Approach 1: One Pass

If we walk along the mountain from left to right, we have to move strictly up, then strictly down.

Algorithm:

1. Let’s walk up from left to right until we can’t: that has to be the peak.
2. We should ensure the peak is not the first or last element.
3. Then, we walk down.
4. If we reach the end, the array is valid, otherwise its not.

def validMountainArray(arr: list[int]) -> bool:
    N = len(arr)
    i = 0

    # walk up
    while i + 1 < N and arr[i] < arr[i + 1]:
        i += 1

    # peak can't be first or last
    if i == 0 or i == N - 1:
        return False

    # walk down
    while i + 1 < N and arr[i] > arr[i + 1]:
        i += 1

    return i == N - 1

arr = [2, 3, 5, 7, 8, 6, 4]
result = validMountainArray(arr)
print(result)  # Output: True

Complexity Analysis

• Time Complexity: O(n), where N is the length of A.
• Space Complexity: O(1).

---

Back to Top

See other articles in Category Arrays