💡 Problem Formulation: A mountain array is an array of integers where numbers first ascend to a peak value and then descend. It’s not a mountain array if it doesn’t start with an ascent and immediately descend after a single peak or if the climb or descent is missing altogether. For instance, the array [1, 3, 2] represents a mountain array, but [1, 2, 2, 3] does not because it plateaus before ascending. The goal is to determine whether a given array is a valid mountain array.
Method 1: Iterative Check
This method involves iterating through the array from the start, checking for an initial ascending sequence followed by a descending sequence. The function should return False if there is any plateau (consecutive equal values) or if the peak is at the start or end of the array.
Here’s an example:
def is_mountain_array(arr):
if len(arr) < 3:
return False
i = 1
# Ascend to the peak
while i < len(arr) and arr[i] > arr[i - 1]:
i += 1
# Check for peak at start or end and for any flat areas
if i == 1 or i == len(arr) or arr[i] == arr[i - 1]:
return False
# Descend from the peak
while i < len(arr) and arr[i] < arr[i - 1]:
i += 1
return i == len(arr)
Output:
print(is_mountain_array([1, 3, 2])) # True print(is_mountain_array([1, 2, 2, 3])) # False
This function first ensures that the array is long enough to be a mountain array. It then iterates to find the peak, ensuring that the peak is not at the start or end. The function finally descends from the peak, making sure that the sequence continues to the end of the array without any plateaus or additional ascents.
Method 2: Two Pointer Approach
The two-pointer approach uses one pointer starting from the beginning of the array and another from the end. Each pointer moves toward the center of the array until they meet at the peak. Both ascending and descending sequences are checked simultaneously to validate the mountain array.
Here’s an example:
def valid_mountain_array(arr):
if len(arr) < 3:
return False
left, right = 0, len(arr) - 1
# Move left pointer up
while left + 1 < len(arr) and arr[left] < arr[left + 1]:
left += 1
# Move right pointer down
while right > 0 and arr[right - 1] > arr[right]:
right -= 1
# Check if pointers meet at the same peak
return 0 < left == right < len(arr) - 1
Output:
print(valid_mountain_array([1, 3, 2])) # True print(valid_mountain_array([1, 2, 2, 3])) # False
This method initiates two pointers from opposite ends of the array and moves them towards the center. They stop moving when the ascending or descending order stops. A valid mountain array is confirmed if the pointers meet at the same index and that index is not the start or end of the array.
Method 3: Use the Python Max Function
This method finds the maximum value’s index and checks if it forms a peak in the mountain array. If the peak is at the edges or if any side of the peak does not strictly increase or decrease, it returns False.
Here’s an example:
def check_mountain_array(arr):
if len(arr) < 3 or arr[0] >= arr[1] or arr[-1] >= arr[-2]:
return False
peak = arr.index(max(arr))
return arr[:peak] == sorted(set(arr[:peak])) and arr[peak:] == sorted(set(arr[peak:]), reverse=True)
Output:
print(check_mountain_array([1, 3, 2])) # True print(check_mountain_array([1, 2, 2, 3])) # False
This method eliminates any input array that is too short to form a mountain or starts/ends with a descending/ascending pattern. It uses Python’s max() function to find the peak and confirms the mountain array shape by comparing both sides of the peak with a sorted set of themselves, one in ascending order and the other in descending order.
Method 4: Using a Flag
By initializing a flag that marks the transition from ascending to descending, this method processes the array in a single pass, changing the flag when the peak is reached, indicating the start of the descending sequence. If the flag is set erroneously or not set at all, the array is not a mountain array.
Here’s an example:
def is_valid_mountain_array(arr):
if len(arr) < 3:
return False
up = arr[0] < arr[1]
for i in range(1, len(arr) - 1):
if arr[i] == arr[i+1]:
return False
elif arr[i] > arr[i+1] and up:
up = False
elif arr[i] < arr[i+1] and not up:
return False
return not up
Output:
print(is_valid_mountain_array([1, 3, 2])) # True print(is_valid_mountain_array([1, 2, 2, 3])) # False
This method uses a flag to track when the ascending part of the array has ended. If the flag is set incorrectly (indicating a decrease where there should be an increase or vice versa) or if it is never set (meaning the peak was not reached), the array fails the mountain array check.
Bonus One-Liner Method 5: Functional Approach
Python’s combination of max, all and list comprehensions enables a concise one-liner to validate if an array is a mountain array by first checking the list for a peak and then ensuring that the elements up to and after the peak are strictly increasing and decreasing, respectively.
Here’s an example:
valid_mountain = lambda a: (lambda peak: 0 < peak < len(a)-1 and all(a[i] < a[i+1] for i in range(peak)) and all(a[i] > a[i+1] for i in range(peak, len(a)-1)))(a.index(max(a)))
Output:
print(valid_mountain([1, 3, 2])) # True print(valid_mountain([1, 2, 2, 3])) # False
Utilizing Python’s lambda functions and all function, this approach aims for brevity. However, it retains the complete logic required for validating a mountain array within a single line of code, confirming if it includes a peak and if the sequences strictly ascend and then descend.
Summary/Discussion
- Method 1: Iterative Check. Straightforward with explicit checks for plateaus. Potentially less efficient due to iterating twice.
- Method 2: Two Pointer Approach. Simultaneously checks ascent and descent. Efficient but may require an understanding of two-pointer techniques.
- Method 3: Use the Python Max Function. Leverages built-in functions for concise implementation. Could be inefficient for large arrays due to multiple sorting operations.
- Method 4: Using a Flag. Clear logic using a single pass. Efficient, but a miss-set flag can complicate debugging.
- Method 5: Functional Approach. Extremely concise. Suitable for one-liners, but readability may suffer, making it less maintainable.