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.
1class Solution {
2 public boolean validMountainArray(int[] arr) {
3 int n = arr.length;
4 if (n < 3) return false;
5 int i = 0;
6 while (i + 1 < n && arr[i] < arr[i + 1]) i++;
7 if (i == 0 || i == n - 1) return false;
8 while (i + 1 < n && arr[i] > arr[i + 1]) i++;
9 return i == n - 1;
10 }
11}This implementation uses a variable i to climb up and identify the peak. If the peak is at either the start or end, it returns false. Otherwise, it continues checking the descending order. If the end of the array is reached after descending, 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.
1#include <vector>
using namespace std;
bool validMountainArray(vector<int>& arr) {
int n = arr.size();
if (n < 3) return false;
int i = 0;
while (i < n - 1 && arr[i] < arr[i + 1]) i++;
if (i == 0 || i == n - 1) return false;
while (i < n - 1 && arr[i] > arr[i + 1]) i++;
return i == n - 1;
}C++ uses a streamlined methodology, enforcing a single linear scan while capturing and validating transitions from ascents to descents as required for a mountain array.