LeetCode 941: Valid Mountain Array

Explanation

To determine if the given array is a valid mountain array, we need to find the peak element of the mountain. The peak element should be such that it is not the first or last element of the array. If the peak element is found, we can check if all elements to the left of the peak are in increasing order and all elements to the right of the peak are in decreasing order.

• If any element to the right of the peak is greater than or equal to the peak element, or if we do not find a peak element, the array is not a valid mountain array.
• If the conditions are satisfied, the array is a valid mountain array.

Time complexity: O(n) where n is the length of the input array. Space complexity: O(1)

class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        int i = 0;

        // Walk up
        while (i + 1 < n && arr[i] < arr[i + 1]) {
            i++;
        }

        // Peak can't be the first or last element
        if (i == 0 || i == n - 1) {
            return false;
        }

        // Walk down
        while (i + 1 < n && arr[i] > arr[i + 1]) {
            i++;
        }

        return i == n - 1;
    }
}