#941

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Valid Mountain Array

The 'Valid Mountain Array' problem requires determining if an array meets the conditions of a valid mountain array using array-driven techniques.

array

Problem Statement

Given an integer array 'arr', determine if it forms a valid mountain array. A valid mountain array must satisfy the following conditions:

The array must first strictly increase, followed by a strict decrease. 2. The array must contain at least three elements. 3. The first and last elements must not be part of the peak.

Examples

Example 1

Input: arr = [2,1]

Output: false

Example details omitted.

Example 2

Input: arr = [3,5,5]

Output: false

Example details omitted.

Example 3

Input: arr = [0,3,2,1]

Output: true

Example details omitted.

Constraints

1 <= arr.length <= 104
0 <= arr[i] <= 104

Solution Approach

Identify the peak of the mountain

To check if the array is a valid mountain, start by finding the peak, which must occur at a position where the array increases and then decreases. Track the peak position by comparing adjacent elements.

Verify the strictly increasing and decreasing sequences

Once the peak is located, check that elements before it form a strictly increasing sequence, and elements after it form a strictly decreasing sequence. If either condition fails, return false.

Handle edge cases

Consider edge cases where the array is too short or doesn't have a peak (e.g., arr = [1, 1]). Ensure the array has at least three elements and that the peak is not at the start or end.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on traversing the array twice, which results in O(n) time complexity. The space complexity is O(1), as we are only using a few additional variables for tracking the peak and the sequence states.

What Interviewers Usually Probe

The candidate demonstrates an understanding of monotonic sequences.
The candidate correctly identifies and handles edge cases like short arrays.
The candidate approaches the problem efficiently, with an O(n) solution.

Common Pitfalls or Variants

Common pitfalls

Forgetting that the peak must be neither the first nor last element of the array.
Mistaking non-strictly increasing or decreasing sequences as valid.
Not handling cases where the array is too short or contains duplicate elements properly.

Follow-up variants

Handle arrays with duplicate values, where the peak may not be strictly increasing or decreasing.
Extend the problem to handle arrays with more complex conditions, like multiple peaks.
Optimize for large arrays by considering early exits when the array fails any of the conditions.

FAQ

What is a valid mountain array?

A valid mountain array increases strictly to a peak and then decreases strictly. It must contain at least three elements.

How can I efficiently find the peak in the array?

The peak is the element where the array stops increasing and starts decreasing. Track the position as you traverse the array from left to right.

Why does the solution check for strictly increasing and decreasing sequences?

The problem requires the array to have distinct, ordered increases and decreases. Non-strict sequences would invalidate the mountain array.

What is the time complexity of the solution?

The time complexity is O(n), as you only need to traverse the array twice: once for finding the peak and once for verifying the sequence conditions.

What if the array has duplicate values?

An array with duplicates, like [1, 1, 2, 3], is not valid because the sequences must be strictly increasing and decreasing.

terminal

Solution

Solution 1: Two Pointers

First, we check if the length of the array is less than $3$. If it is, then it definitely is not a mountain array, so we return `false` directly.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        n = len(arr)
        if n < 3:
            return False
        i, j = 0, n - 1
        while i + 1 < n - 1 and arr[i] < arr[i + 1]:
            i += 1
        while j - 1 > 0 and arr[j - 1] > arr[j]:
            j -= 1
        return i == j

Continue Practicing

#942 di string match #939 minimum area rectangle #943 find the shortest superstring