Valid Mountain Array | Live Coding with Explanation | Leetcode - 941
Valid Mountain Array - Video Solution
Watch 10 video solutions for Valid Mountain Array, a easy level problem involving Array. This walkthrough by Algorithms Made Easy has 11,711 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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. |