Sponsored
Sponsored
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.
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.
1def validMountainArray(arr):
2 n = len(arr)
3 if n < 3:
4 return False
5 i = 0
6 while i + 1 < n and arr[i] < arr[i + 1]:
7 i += 1
8 if i == 0 or i == n - 1:
9 return False
10 while i + 1 < n and arr[i] > arr[i + 1]:
11 i += 1
12 return i == n - 1The Python solution checks for the minimum length condition, then iterates to find an increasing sequence, checks that a peak is a valid peak, then confirms a valid decreasing order from that peak.
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.
Time complexity: O(n), as the array is scanned linearly.
Space complexity: O(1), without additional space allocations.
1defThe Python approach compresses the steps into a unified process, using indexed counters to assess validity based on the conditions defining a mountain structure.