Valid Mountain Array - Solution & Explanation
Problem Statement
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.
The function starts by checking if the array size is less than 3, returning false if it is. It then proceeds by using a variable i to iterate upwards while the current element is less than the next. When the peak is detected, further checks ensure the peak isn't at either end of the array. The loop continues by iterating downwards until the end of the array. If both conditions hold, the array is a valid mountain array.
Complexity
Time complexity: O(n), where n is the length of the array because each element is examined at most twice.
Space complexity: O(1), as no additional data structures are used.
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.
Instead of separate passes, the transition from ascent to descent is marked by a continuity check within the same pass. The condition validates an increase followed by a decrease.
Complexity
Time complexity: O(n), as the array is scanned linearly.
Space complexity: O(1), without additional space allocations.
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time complexity: O(n), where n is the length of the array because each element is examined at most twice. |
| Single Pass Linear Scan | Time complexity: O(n), as the array is scanned linearly. |
| Two Pointers | — |
Detailed 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. |
Video Solution
Valid Mountain Array | Live Coding with Explanation | Leetcode - 941 • Algorithms Made Easy • 11,711 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Valid Mountain Array easy or hard?
Valid Mountain Array Python/Java solution
How to solve Valid Mountain Array in O(n)?
What is the best approach for Valid Mountain Array?
Is Valid Mountain Array asked at Google/Amazon/Meta?
What data structure is used in Valid Mountain Array?
What is the time complexity of Valid Mountain Array?
Ready to solve this problem?
Practice Valid Mountain Array with our built-in code editor and test cases.
Practice on FleetCode