Valid Mountain Array

Easy

#0895Time: O(N). The first pass to find the peak takes O(N). The subsequent two passes to verify the slopes take O(peakIndex) and O(N - peakIndex) respectively, which sum up to O(N). The total time complexity is O(N) + O(N) = O(N).Space: O(1). We only use a few variables to store the peak index and loop counters.

Data structures

Array

Prompt

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⁴
0 <= arr[i] <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach breaks the problem into two distinct steps. First, we iterate through the array to find the peak (the maximum element). Then, we perform two more traversals: one from the start to the peak and another from the peak to the end, to verify the mountain properties.

Algorithm

If the array length n is less than 3, it cannot be a mountain array, so return false.
Find the index of the maximum element in the array. Let's call this peakIndex.
If there are multiple maximum elements, the index of the first one is typically found.
According to the definition, the peak cannot be the first or the last element. If peakIndex is 0 or n - 1, return false.
Verify the strictly increasing part (the 'uphill' slope). Iterate from index 0 to peakIndex - 1. If arr[i] >= arr[i+1] for any i, it's not a valid mountain. Return false.
Verify the strictly decreasing part (the 'downhill' slope). Iterate from peakIndex to n - 2. If arr[i] <= arr[i+1] for any i, it's not a valid mountain. Return false.
If all the above checks pass, the array is a valid mountain. Return true.

Walkthrough

The core idea is to first locate the highest point of the potential mountain. We traverse the array to find the index of the maximum element. Let's call this peakIndex.

According to the definition of a mountain array, the peak cannot be the first or the last element. So, if peakIndex is 0 or arr.length - 1, we can immediately return false. This also handles arrays that are purely increasing or decreasing.

Next, we need to verify the two slopes of the mountain.

We check the 'uphill' part: from the beginning of the array up to peakIndex. We iterate from index 0 to peakIndex - 1 and ensure that arr[i] < arr[i+1] for all i in this range. If we find any pair that violates this (i.e., arr[i] >= arr[i+1]), it's not a valid mountain, so we return false.
Then, we check the 'downhill' part: from peakIndex to the end of the array. We iterate from peakIndex to arr.length - 2 and ensure that arr[i] > arr[i+1] for all i in this range. If we find any pair that violates this (i.e., arr[i] <= arr[i+1]), it's not a valid mountain, so we return false.

If the array passes all these checks, it is a valid mountain array, and we return true. A preliminary check for arr.length < 3 is also necessary at the beginning.

1class Solution {2    public boolean validMountainArray(int[] arr) {3        int n = arr.length;4        if (n < 3) {5            return false;6        }7 8        // Find the peak index9        int maxVal = -1;10        int peakIndex = -1;11        for (int i = 0; i < n; i++) {12            if (arr[i] > maxVal) {13                maxVal = arr[i];14                peakIndex = i;15            }16        }17 18        // Peak cannot be the first or last element19        if (peakIndex == 0 || peakIndex == n - 1) {20            return false;21        }22 23        // Check the uphill part24        for (int i = 0; i < peakIndex; i++) {25            if (arr[i] >= arr[i + 1]) {26                return false;27            }28        }29 30        // Check the downhill part31        for (int i = peakIndex; i < n - 1; i++) {32            if (arr[i] <= arr[i + 1]) {33                return false;34            }35        }36 37        return true;38    }39}

Complexity

Time

O(N). The first pass to find the peak takes O(N). The subsequent two passes to verify the slopes take O(peakIndex) and O(N - peakIndex) respectively, which sum up to O(N). The total time complexity is O(N) + O(N) = O(N).

Space

O(1). We only use a few variables to store the peak index and loop counters.

Trade-offs

Pros

Conceptually straightforward and easy to understand.
Separates the logic of finding the peak and verifying the slopes, which can make debugging easier.

Cons

Requires multiple passes over the array (one to find the peak, and up to two more to verify the slopes), which can be slightly less performant in practice than a single-pass solution.
The logic is split into separate parts, which might make the code slightly longer.

This is the most efficient approach, solving the problem in a single pass through the array. The idea is to simulate walking up the mountain from the left and then walking down to the right, ensuring we reach the end.

Algorithm

Let n be the length of the array. If n < 3, return false.
Initialize a pointer i = 0.
Climb up: Use a while loop to increment i as long as i+1 < n and arr[i] < arr[i+1]. This loop continues as long as the array is strictly increasing.
Check peak validity: After the first loop, i is at the peak. The peak cannot be the first or last element. So, if i == 0 (never climbed up) or i == n - 1 (only climbed up), return false.
Climb down: Use another while loop to increment i as long as i+1 < n and arr[i] > arr[i+1]. This loop continues as long as the array is strictly decreasing.
Final check: If the pointer i has reached the end of the array (i == n - 1), it means we successfully climbed up and then climbed down to the very end. This is a valid mountain, so return true. Otherwise, return false.

Walkthrough

We use a single pointer, let's call it i, to traverse the array. The entire process can be thought of as a single journey over the mountain.

First, we handle the base case: if the array has fewer than 3 elements, it cannot be a mountain, so we return false.

We start i at index 0 and 'climb up' the mountain. We advance i as long as we are within the array bounds and the next element is strictly greater than the current one (arr[i] < arr[i+1]). This loop finds the start of the peak or the end of the increasing sequence.

After the 'climb up' loop, i points to the potential peak. We must perform a crucial check here. If i is still 0, it means the array never increased (e.g., [5,4,3]). If i has reached the last index (arr.length - 1), it means the array only increased (e.g., [1,2,3]). In both cases, it's not a valid mountain, so we return false. This ensures the peak is not at the ends of the array.

Next, we 'climb down' from the peak. We continue advancing i as long as we are within bounds and the next element is strictly smaller than the current one (arr[i] > arr[i+1]).

After the 'climb down' loop, if we have successfully traversed a valid mountain, our pointer i should have landed exactly on the last index of the array (arr.length - 1). The final step is to check if i == arr.length - 1. If it is, it means we climbed up to a peak and then climbed down to the very end, with no flat parts or upward slopes on the way down. This confirms a valid mountain, and we return true. Otherwise, we return false.

1class Solution {2    public boolean validMountainArray(int[] arr) {3        int n = arr.length;4        if (n < 3) {5            return false;6        }7 8        int i = 0;9 10        // Walk up the mountain11        while (i + 1 < n && arr[i] < arr[i + 1]) {12            i++;13        }14 15        // Peak can't be the first or last element16        if (i == 0 || i == n - 1) {17            return false;18        }19 20        // Walk down the mountain21        while (i + 1 < n && arr[i] > arr[i + 1]) {22            i++;23        }24 25        // If we reached the end, it's a valid mountain26        return i == n - 1;27    }28}

Complexity

Time

O(N). The pointer `i` traverses each element of the array at most once.

Space

O(1). We only use a constant amount of extra space for the pointer `i` and length `n`.

Trade-offs

Pros

Highly efficient, as it solves the problem in a single pass.
Elegant and concise code.
Avoids the overhead of multiple loops over the same data.

Cons

The logic, while concise, might be slightly less intuitive at first glance compared to explicitly finding the peak and then verifying.

Solutions

Solution

1class Solution { public boolean validMountainArray ( int [] arr ) { int n = arr . length ; if ( n < 3 ) { return false ; } int l = 0 , r = n - 1 ; while ( l + 1 < n - 1 && arr [ l ] < arr [ l + 1 ]) { ++ l ; } while ( r - 1 > 0 && arr [ r ] < arr [ r - 1 ]) { -- r ; } return l == r ; } }

1class Solution { public: bool validMountainArray ( vector < int >& arr ) { int n = arr . size (); if ( n < 3 ) return 0 ; int l = 0 , r = n - 1 ; while ( l + 1 < n - 1 && arr [ l ] < arr [ l + 1 ]) ++ l ; while ( r - 1 > 0 && arr [ r ] < arr [ r - 1 ]) -- r ; return l == r ; } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem