Valid Mountain Array

Problem Statement

The problem is to determine whether a given array of integers called arr can be classified as a "mountain array." A mountain array possesses certain characteristics which create a visual representation resembling a mountain. Specifically:

• The array must have at least three elements to form a peak and slopes.
• It should increase to a highest point (peak) and then strictly decrease. This implies an element i such that before this i, elements are in ascending order, and after i, elements are in descending order.
• The peak, which is neither the first nor the last element in the array, signifies a shift from climbing up to climbing down.

Examples

Example 1

Input:

arr = [2,1]

Output:

false

Example 2

Input:

arr = [3,5,5]

Output:

false

Example 3

Input:

arr = [0,3,2,1]

Output:

true

Constraints

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 104

Approach and Intuition

When looking to validate whether an array is a mountain array, we are essentially checking for a single peak with increasing values leading up to the peak and decreasing values thereafter. Here’s the method to approach this:

1. Initial Checks:

   • Verify if the array length is less than 3. If it is, return false immediately since we can't form a mountain.

2. Find Ascending Order:

   • Traverse through the array from the beginning, and continue moving forward until you find the first element which is not larger than the next one. This point (if exists) should potentially be the peak.
   • If during this traversal, either the peak ends up being the first element or no peak can be found, return false.

3. Find Descending Order:

   • Continue from the peak found in the previous step. The elements should now start to decrease.
   • If any element is found that does not adhere to this descending order, return false.

4. Check for True Peak:

   • If the array was strictly increasing or strictly decreasing without a true peak, verify the position of the stopping point from the first traversal. If you stopped at the last element, then you don't have a decline phase — return false.
   • Conversely, if the first traversal stopped at the first element, indicating there was no increase, return false.

5. Final Validation:

   • If all the conditions meet (an increase phase, a peak, followed by a decrease phase), the array is a mountain array. Return true.

Examples:

• For arr = [2,1], it fails the initial check of having at least 3 elements. Hence, it returns false.
• In the case of arr = [3,5,5], even though it starts off correctly by increasing, it doesn't form a peak because of the repetition of 5. There is no strict increase followed by a strict decrease.
• For arr = [0,3,2,1], we observe a classic mountain array. It strictly increases from 0 to 3 and then strictly decreases from 3 to 1.

By reasoning through these steps using the outlined approach, you can determine if an array represents a mountain structure, fulfilling the conditions necessary for valid mountain-like progression.

Solutions

class Solution {
    public boolean checkMountain(int[] arr) {
        int len = arr.length;
        int idx = 0;
    
        // Ascend to peak
        while (idx + 1 < len && arr[idx] < arr[idx + 1])
            idx++;
    
        // A valid peak cannot be at the extremes
        if (idx == 0 || idx == len - 1)
            return false;
    
        // Descend from peak
        while (idx + 1 < len && arr[idx] > arr[idx + 1])
            idx++;
    
        return idx == len - 1;
    }
}