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.
1#include <vector>
2using namespace std;
3bool validMountainArray(vector<int>& arr) {
4 int n = arr.size();
5 if (n < 3) return false;
6 int i = 0;
7 while (i + 1 < n && arr[i] < arr[i + 1]) i++;
8 if (i == 0 || i == n - 1) return false;
9 while (i + 1 < n && arr[i] > arr[i + 1]) i++;
10 return i == n - 1;
11}This solution follows the two-pointer strategy. It starts from the beginning to climb upwards and checks if the peak is not at the beginning or the end. Once a peak is identified, the algorithm proceeds downwards to ensure that the array has decreased properly. If both conditions are met, it confirms a valid mountain array.
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.
1functionThe JavaScript solution narrows down a single concise pass along the mountain conditions with strict criteria checks for peak positioning and directional changes.