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.
1public class Solution {
2 public bool 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}The C# solution applies the two-pointer method, iterating initially upward and downward after finding the peak. If a valid peak indicating the turn from increasing to decreasing, it ensures the array is a mountain.
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.
1classThe Java solution uses a single loop iteration to cover both ascent and descent transitions, confirming a valid mountain by monitoring the peak location and continuity checks.