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] <= 104This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time complexity: O(n), as the array is scanned linearly.
Space complexity: O(1), without additional space allocations.
| 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. |
Valid Mountain Array • Kevin Naughton Jr. • 26,226 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