941. Valid Mountain Array
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 33.0%
Problem Breakdown
The problem asks us to determine if an array of integers represents a valid mountain array. A mountain array must satisfy the following conditions:
- The array length must be at least 3.
- There exists a peak element such that all elements before it are strictly increasing, and all elements after it are strictly decreasing.
Inputs: An array of integers arr.
Outputs: A boolean value indicating whether the array is a valid mountain array or not.
Implicit constraints:
- The array can contain duplicate values, but they cannot be part of the increasing or decreasing sequence.
- Negative numbers are allowed in the array.
- Edge cases include arrays with fewer than 3 elements, arrays that are entirely non-decreasing or non-increasing, and arrays where the peak is at the start or end.
Intuition
A brute-force approach would involve checking all possible subarrays to see if they form a mountain. However, this would be inefficient with a time complexity of O(n^2). The key insight is that we can traverse the array in a single pass to determine if it forms a valid mountain. We need to find the peak and ensure that there are strictly increasing elements before the peak and strictly decreasing elements after the peak.
Approach
- Check if the array length is less than 3. If so, return
falsebecause a valid mountain must have at least three elements. - Traverse the array to find the peak element where the sequence stops increasing.
- Ensure that there are no flat segments (i.e., consecutive equal elements) in the array.
- After finding the peak, ensure that all remaining elements are strictly decreasing.
- If both conditions are met, return
true; otherwise, returnfalse.
Complexity Analysis
- Time complexity: O(n), where n is the length of the array. We traverse the array once to find the peak and then check the rest of the elements.
- Space complexity: O(1), as we only use a few extra variables for tracking indices and flags.
Solution
def validMountainArray(arr):
if len(arr) < 3:
return False
i = 0
# Walk up
while i + 1 < len(arr) and arr[i] < arr[i + 1]:
i += 1
# Peak can't be first or last
if i == 0 or i == len(arr) - 1:
return False
# Walk down
while i + 1 < len(arr) and arr[i] > arr[i + 1]:
i += 1
return i == len(arr) - 1
# Example usage:
print(validMountainArray([2, 1])) # Output: False
print(validMountainArray([3, 5, 5])) # Output: False
print(validMountainArray([0, 3, 2, 1])) # Output: True
Edge Cases Handled
- Arrays with fewer than 3 elements are immediately returned as
false. - Arrays with flat segments (consecutive equal elements) are handled by the while loops, which only proceed if the current element is strictly less or greater than the next.
- Arrays where the peak is at the start or end are caught by checking if
iremains at 0 or reaches the last index after the first traversal.