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 <stdbool.h>
2bool validMountainArray(int* arr, int arrSize) {
3 if (arrSize < 3) return false;
4 int i = 0;
5 while (i + 1 < arrSize && arr[i] < arr[i + 1]) i++;
6 if (i == 0 || i == arrSize - 1) return false;
7 while (i + 1 < arrSize && arr[i] > arr[i + 1]) i++;
8 return i == arrSize - 1;
9}The function starts by checking if the array size is less than 3, returning false if it is. It then proceeds by using a variable i to iterate upwards while the current element is less than the next. When the peak is detected, further checks ensure the peak isn't at either end of the array. The loop continues by iterating downwards until the end of the array. If both conditions hold, the array is 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.
1defThe Python approach compresses the steps into a unified process, using indexed counters to assess validity based on the conditions defining a mountain structure.