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 >= 3i 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 <= 1040 <= arr[i] <= 104Problem 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.
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.
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.
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.
Time complexity: O(n), as the array is scanned linearly.
Space complexity: O(1), without additional space allocations.
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).
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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. |
Valid Mountain Array | Live Coding with Explanation | Leetcode - 941 • Algorithms Made Easy • 11,438 views views
Watch 9 more video solutions →Practice Valid Mountain Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor