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^40 <= arr[i] <= 10^4
Hints for Valid Mountain Array
Hint 1
Walk up from the left while each next value is strictly larger.
Hint 2
Where the climb stops is the only candidate peak — it must not be the first or the last index.
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
- Set
i = 0and advance whilearr[i] < arr[i + 1]. - If
iis still 0 (no climb) or is the last index (no descent), returnfalse. - Advance while
arr[i] > arr[i + 1]. - Return whether
ireached 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 - 1Java
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