Valid Mountain Array

Easy
1100.

Valid Mountain Array

Valid Mountain Array is an easy coding problem on arrays and two pointers, asked in Amazon, Google and Adobe interviews.

An array is a mountain when it has at least three elements and some peak index p with 0 < p < arr.length - 1 such that the values rise strictly up to p and fall strictly after it:

  • arr[0] < arr[1] < ... < arr[p]
  • arr[p] > arr[p + 1] > ... > arr[arr.length - 1]

Return true if arr is a mountain. Equal neighbours anywhere break the mountain, and so does a slope that only rises or only falls.

Example 1

Input
arr = [2,1]
Output
false
Explanation
Fewer than three elements.

Example 2

Input
arr = [1,4,4,2]
Output
false
Explanation
The two 4s form a flat top, so the climb is not strict.

Example 3

Input
arr = [0,3,9,4,1]
Output
true

Constraints

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {boolean}
 */
var validMountainArray = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Valid Mountain Array — Solution in Python, Java & C++

Valid Mountain Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Valid Mountain Array is an easy coding problem on arrays and two pointers, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Two Pointers
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An array is a mountain when it has at least three elements and some peak index p with 0 < p < arr.length - 1 such that the values rise strictly up to p and fall strictly after it:

  • arr[0] < arr[1] < ... < arr[p]
  • arr[p] > arr[p + 1] > ... > arr[arr.length - 1]

Return true if arr is a mountain. Equal neighbours anywhere break the mountain, and so does a slope that only rises or only falls.

Example 1

Input: arr = [2,1]
Output: false
Explanation: Fewer than three elements.

Example 2

Input: arr = [1,4,4,2]
Output: false
Explanation: The two 4s form a flat top, so the climb is not strict.

Example 3

Input: arr = [0,3,9,4,1]
Output: true

Constraints

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^4

Hints for Valid Mountain Array

  1. Hint 1

    Walk up from the left while each next value is strictly larger.

  2. Hint 2

    Where the climb stops is the only candidate peak — it must not be the first or the last index.

  3. Hint 3

    From there, walk down while each next value is strictly smaller; the array is a mountain exactly when this walk reaches the end.

How to solve Valid Mountain Array

A mountain has exactly one place where the strict climb ends, so a single walker that climbs as far as it can and then descends as far as it can decides the question.

Approach

  1. Set i = 0 and advance while arr[i] < arr[i + 1].
  2. If i is still 0 (no climb) or is the last index (no descent), return false.
  3. Advance while arr[i] > arr[i + 1].
  4. Return whether i reached the last index.

Why it works

The first walk stops at the first index where the array does not strictly increase, which is the only possible peak: a later peak would need this non-increase to be part of a strict climb. The second walk then accepts the array only if everything after the peak strictly decreases. A plateau stops both walks early, so it is rejected automatically.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Arrays shorter than three elements are never mountains.
  • A purely increasing or purely decreasing array has its 'peak' at an end, which is not allowed.
  • Use strict comparisons: equal neighbours are a plateau, not a slope.

Reference solution

Python

from typing import List

def validMountainArray(arr: List[int]) -> bool:
    n = len(arr)
    i = 0
    while i + 1 < n and arr[i] < arr[i + 1]:
        i += 1
    if i == 0 or i == n - 1:
        return False
    while i + 1 < n and arr[i] > arr[i + 1]:
        i += 1
    return i == n - 1

Java

public static boolean validMountainArray(int[] arr) {
    int n = arr.length, i = 0;
    while (i + 1 < n && arr[i] < arr[i + 1]) i++;
    if (i == 0 || i == n - 1) return false;
    while (i + 1 < n && arr[i] > arr[i + 1]) i++;
    return i == n - 1;
}

C++

bool validMountainArray(vector<int>& arr) {
    int n = arr.size(), i = 0;
    while (i + 1 < n && arr[i] < arr[i + 1]) i++;
    if (i == 0 || i == n - 1) return false;
    while (i + 1 < n && arr[i] > arr[i + 1]) i++;
    return i == n - 1;
}

JavaScript

var validMountainArray = function(arr) {
    var n = arr.length, i = 0;
    while (i + 1 < n && arr[i] < arr[i + 1]) i++;
    if (i === 0 || i === n - 1) return false;
    while (i + 1 < n && arr[i] > arr[i + 1]) i++;
    return i === n - 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique