Valid Mountain Array solution and explanation
IBM
Google
9 more videos on this problem
Valid Mountain Array | Live Coding with Explanation | Leetcode - 941Algorithms Made Easy · 4:17 · 11K views
Valid Mountain Array - LeetCode 941 - Coding Interview QuestionsOne Code Man · 3:04 · 1K views
Leetcode | 941. Valid Mountain Array | Easy | Java SolutionDeveloper Docs · 6:47 · 1K views
Daily LeetCode Challenge [09]: 941. Valid Mountain Array. (#array)The Brown Box · 10:12 · 1K views
941.1 Valid Mountain Array (Theory) | #9 | Arrays Playlist | LeetcodeCTO Bhaiya · 8:33 · 1K views
LeetCode - 941 Valid Mountain Array | Arrays CardAditya Mahajan · 7:58 · 769 views
Valid Mountain Array - LeetCode 941 - PythonGordon Zhu · 15:58 · 720 views
Valid Mountain Array - 941. LeetCode - JavaTeddy Smith · 9:01 · 619 views
Leetcode - 941. Valid Mountain Array - Javascript solutionNiso Zakuto · 7:44 · 432 views
941. Valid Mountain Array | LeetCode | Python SolutionDepressed Programmer · 4:49 · 336 views
The problem
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
iwith0 < i < arr.length - 1such 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 <= 1040 <= arr[i] <= 104
Approach overview
Problem Overview: You are given an integer array and must determine whether it forms a valid mountain. A mountain array strictly increases to a single peak and then strictly decreases. The peak cannot be the first or last element, and equal adjacent values are not allowed.
Approach 1: Single Pass Linear Scan (Time: O(n), Space: O(1))
This approach walks through the array once while tracking two phases: the increasing slope and the decreasing slope. Start from index 1 and move forward while arr[i] > arr[i-1]. When the increasing phase stops, that index represents the potential peak. The peak must not be the first or last index. Continue scanning while arr[i] < arr[i-1] to validate the decreasing slope. If you reach the end of the array exactly after the descent, the array forms a valid mountain.
The key insight is that a mountain has exactly one transition from increasing to decreasing. Tracking this transition in a single traversal avoids extra memory and keeps the algorithm simple. This method works well for problems involving ordered patterns in an array.
Approach 2: Two Pointers Approach (Time: O(n), Space: O(1))
This method uses two directional scans to verify both slopes of the mountain. Start a pointer from the left and keep moving while values strictly increase. Separately, start another pointer from the right and move backward while values strictly decrease. If both pointers stop at the same index and that index is not at the boundaries, that position represents a valid peak.
The technique relies on comparing adjacent elements and advancing pointers until the slope condition breaks. Because both pointers converge toward the peak, the array must contain one strictly increasing section and one strictly decreasing section. This pattern is a classic use of the two pointers technique applied to a monotonic pattern in an array.
Recommended for interviews: The single pass linear scan is usually the expected solution because it demonstrates clean reasoning about array traversal and state transitions. Interviewers like this approach since it validates the increasing and decreasing phases in one pass with O(n) time and O(1) space. The two pointers method is also efficient and shows familiarity with pointer-based scanning patterns.
Approach 1: Two Pointers Approach
This approach involves using two pointers, one starting at the beginning and the other at the end of the array. These pointers will move inward to detect the peak of the mountain array. If they meet at the same peak, the array is valid as a mountain.
def validMountainArray(arr):
n = len(arr)
if n < 3:
return False
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 - 1class Solution {
public boolean validMountainArray(int[] arr) {
int n = arr.length;
if (n < 3) return false;
int 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;
}
}#include <vector>
using namespace std;
bool validMountainArray(vector<int>& arr) {
int n = arr.size();
if (n < 3) return false;
int 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;
}function validMountainArray(arr) {
const n = arr.length;
if (n < 3) return false;
let 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;
}#include <stdbool.h>
bool validMountainArray(int* arr, int arrSize) {
if (arrSize < 3) return false;
int i = 0;
while (i + 1 < arrSize && arr[i] < arr[i + 1]) i++;
if (i == 0 || i == arrSize - 1) return false;
while (i + 1 < arrSize && arr[i] > arr[i + 1]) i++;
return i == arrSize - 1;
}public class Solution {
public bool ValidMountainArray(int[] arr) {
int n = arr.Length;
if (n < 3) return false;
int 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;
}
}The Python solution checks for the minimum length condition, then iterates to find an increasing sequence, checks that a peak is a valid peak, then confirms a valid decreasing order from that peak.
Time complexity: O(n), iterating over the array elements once.
Space complexity: O(1), no extra data storage is needed.
Approach 2: Single Pass Linear Scan
This approach involves a single linear scan of the array to first ascend, marking an increase until a peak, and then descend. The validations confirm conditions for a mountain array throughout the process.
def validMountainArray(arr):
n = len(arr)
if n < 3:
return False
i = 0
while i < n - 1 and arr[i] < arr[i + 1]:
i += 1
if i == 0 or i == n - 1:
return False
while i < n - 1 and arr[i] > arr[i + 1]:
i += 1
return i == n - 1class Solution {
public boolean validMountainArray(int[] arr) {
int n = arr.length;
if (n < 3) return false;
int i = 0;
while (i < n - 1 && arr[i] < arr[i + 1]) i++;
if (i == 0 || i == n - 1) return false;
while (i < n - 1 && arr[i] > arr[i + 1]) i++;
return i == n - 1;
}
}#include <vector>
using namespace std;
bool validMountainArray(vector<int>& arr) {
int n = arr.size();
if (n < 3) return false;
int i = 0;
while (i < n - 1 && arr[i] < arr[i + 1]) i++;
if (i == 0 || i == n - 1) return false;
while (i < n - 1 && arr[i] > arr[i + 1]) i++;
return i == n - 1;
}function validMountainArray(arr) {
const n = arr.length;
if (n < 3) return false;
let i = 0;
while (i < n - 1 && arr[i] < arr[i + 1]) i++;
if (i === 0 || i === n - 1) return false;
while (i < n - 1 && arr[i] > arr[i + 1]) i++;
return i === n - 1;
}#include <stdbool.h>
bool validMountainArray(int* arr, int arrSize) {
if (arrSize < 3) return false;
int i = 0;
while (i < arrSize - 1 && arr[i] < arr[i + 1]) i++;
if (i == 0 || i == arrSize - 1) return false;
while (i < arrSize - 1 && arr[i] > arr[i + 1]) i++;
return i == arrSize - 1;
}public class Solution {
public bool ValidMountainArray(int[] arr) {
int n = arr.Length;
if (n < 3) return false;
int i = 0;
while (i < n - 1 && arr[i] < arr[i + 1]) i++;
if (i == 0 || i == n - 1) return false;
while (i < n - 1 && arr[i] > arr[i + 1]) i++;
return i == n - 1;
}
}The Python approach compresses the steps into a unified process, using indexed counters to assess validity based on the conditions defining a mountain structure.
Time complexity: O(n), directly dependent on element count.
Space complexity: O(1) because no auxiliary structures are involved.
Approach 3: 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.
Then, we use a pointer i to move from the left end of the array to the right, until we find a position i such that arr[i] > arr[i + 1]. After that, we use a pointer j to move from the right end of the array to the left, until we find a position j such that arr[j] > arr[j - 1]. If the condition i = j is satisfied, then it means that the array arr is a mountain array.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function validMountainArray(arr: number[]): boolean {
const n = arr.length;
if (n < 3) {
return false;
}
let [i, j] = [0, n - 1];
while (i + 1 < n - 1 && arr[i] < arr[i + 1]) {
i++;
}
while (j - 1 > 0 && arr[j] < arr[j - 1]) {
j--;
}
return i === j;
}func validMountainArray(arr []int) bool {
n := len(arr)
if n < 3 {
return false
}
i, j := 0, n-1
for i+1 < n-1 && arr[i] < arr[i+1] {
i++
}
for j-1 > 0 && arr[j-1] > arr[j] {
j--
}
return i == j
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time complexity: O(n), iterating over the array elements once. |
| Single Pass Linear Scan | Time complexity: O(n), directly dependent on element count. |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Pass Linear Scan | O(n) | O(1) | Best general solution. Cleanly detects the increasing phase, peak, and decreasing phase in one traversal. |
| Two Pointers Approach | O(n) | O(1) | Useful when validating slopes from both ends and identifying whether both sides meet at the same peak index. |
Frequently asked questions
Is Valid Mountain Array easy or hard?
Valid Mountain Array is classified as an Easy problem on LeetCode. The challenge lies in correctly handling edge cases such as peaks at the boundaries, equal adjacent elements, or arrays that never transition from increasing to decreasing.
Valid Mountain Array Python/Java solution
Both Python and Java implementations follow the same logic: scan upward while arr[i] > arr[i-1], mark the peak, then scan downward while arr[i] < arr[i-1]. If the peak is not at either boundary and the scan finishes at the end, the array is valid. The implementation runs in O(n) time with O(1) space.
How to solve Valid Mountain Array in O(n)?
Traverse the array while values strictly increase to find the peak. Ensure the peak is not the first or last element. Then continue traversing while values strictly decrease. If the traversal ends exactly at the last element after the descent, the array forms a valid mountain. This linear scan guarantees O(n) time and constant space.
What is the best approach for Valid Mountain Array?
The single pass linear scan is the most common solution. It walks through the array once, first consuming the strictly increasing part and then the strictly decreasing part. The peak must appear between the two phases and cannot be at the boundaries. This approach runs in O(n) time and O(1) space.
Is Valid Mountain Array asked at Google/Amazon/Meta?
Valid Mountain Array represents a typical array pattern recognition problem often used in technical interviews. Variations of mountain or peak array validation appear in interviews at large tech companies because they test array traversal, edge-case handling, and pointer logic.
What data structure is used in Valid Mountain Array?
The problem primarily uses a basic array and sequential traversal. Solutions rely on index comparisons, pointer movement, and adjacent element checks rather than advanced data structures.
What is the time complexity of Valid Mountain Array?
The optimal solutions run in O(n) time because the array is scanned at most once or twice with simple comparisons between adjacent elements. Space complexity is O(1) since no additional data structures are required beyond a few variables or pointers.