Scale Engineer

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 <= 104
  • 0 <= arr[i] <= 104

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.

class Solution {    public boolean validMountainArray(int[] arr) {        int n = arr.length;        if (n < 3) {            return false;        }         // Find the peak index        int maxVal = -1;        int peakIndex = -1;        for (int i = 0; i < n; i++) {            if (arr[i] > maxVal) {                maxVal = arr[i];                peakIndex = i;            }        }         // Peak cannot be the first or last element        if (peakIndex == 0 || peakIndex == n - 1) {            return false;        }         // Check the uphill part        for (int i = 0; i < peakIndex; i++) {            if (arr[i] >= arr[i + 1]) {                return false;            }        }         // Check the downhill part        for (int i = peakIndex; i < n - 1; i++) {            if (arr[i] <= arr[i + 1]) {                return false;            }        }         return true;    }}

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.

Solutions

class 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 ; } }

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 →

Next problem