Code Implementation

class Solution:
    def validMountainArray(self, arr):
        n = len(arr)
        if n < 3:
            return False
        i = 0
        # walk up
        while i + 1 < n and arr[i] < arr[i + 1]:
            i += 1
        # peak can't be first or last
        if i == 0 or i == n - 1:
            return False
        # walk down
        while i + 1 < n and arr[i] > arr[i + 1]:
            i += 1
        return i == n - 1
    

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        int n = arr.size();
        if (n < 3) return false;
        int i = 0;
        // walk up
        while (i + 1 < n && arr[i] < arr[i + 1]) i++;
        // peak can't be first or last
        if (i == 0 || i == n - 1) return false;
        // walk down
        while (i + 1 < n && arr[i] > arr[i + 1]) i++;
        return i == n - 1;
    }
};
    

class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        if (n < 3) return false;
        int i = 0;
        // walk up
        while (i + 1 < n && arr[i] < arr[i + 1]) i++;
        // peak can't be first or last
        if (i == 0 || i == n - 1) return false;
        // walk down
        while (i + 1 < n && arr[i] > arr[i + 1]) i++;
        return i == n - 1;
    }
}
    

var validMountainArray = function(arr) {
    const n = arr.length;
    if (n < 3) return false;
    let i = 0;
    // walk up
    while (i + 1 < n && arr[i] < arr[i + 1]) i++;
    // peak can't be first or last
    if (i === 0 || i === n - 1) return false;
    // walk down
    while (i + 1 < n && arr[i] > arr[i + 1]) i++;
    return i === n - 1;
};
    

Problem Description

Given an array of integers arr, determine if it is a valid mountain array. An array is considered a valid mountain if:

• It has at least 3 elements.
• There exists some index i (0 < i < arr.length - 1) such that:
  • arr[0] < arr[1] < ... < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

In other words, the array must strictly increase to a single peak (not at the ends), then strictly decrease. There must be no plateaus or flat sections, and the peak cannot be at the first or last index.

Thought Process

The core idea is to identify whether the array "climbs" up to a single peak and then "descends" down, with no plateaus or multiple peaks. A brute-force approach might scan for all possible peaks and check both sides for strict increase and decrease, but this is inefficient.

Instead, we can simulate a climb: walk up the array as long as values are increasing, then walk down as long as values are decreasing. If we reach the end exactly after descending, and the peak was not at the start or end, then it is a valid mountain.

This approach avoids unnecessary checks and leverages the fact that a valid mountain has only one peak and no plateaus.

Solution Approach

• Check Length: If arr has fewer than 3 elements, it cannot be a mountain. Return false immediately.
• Walk Up: Initialize an index i = 0. Move i forward as long as arr[i] < arr[i+1]. This simulates climbing up the mountain.
• Check Peak Position: If i is still at the start (0) or at the end (arr.length - 1), there is no valid peak. Return false.
• Walk Down: Continue moving i forward as long as arr[i] > arr[i+1]. This simulates descending the mountain.
• Final Check: If i reaches the last index, the array forms a valid mountain. Otherwise, return false.

This method uses only a single pass and constant extra space.

Example Walkthrough

Consider the input arr = [0, 3, 2, 1]:

1. Start at index 0. arr[0] = 0, arr[1] = 3. Since 0 < 3, move up to index 1.
2. arr[1] = 3, arr[2] = 2. Since 3 > 2, we've reached the peak at index 1.
3. Now walk down: arr[2] = 2, arr[3] = 1. 2 > 1, move to index 3.
4. Index 3 is the last index. Since we ascended and then descended, and the peak was not at the start or end, this is a valid mountain.

If the input was [2, 1] or [3, 5, 5], the function would return false due to insufficient length or a plateau at the peak.

Time and Space Complexity

• Brute-force Approach: For each possible peak, check both sides for strict increase and decrease. This would be O(n²).
• Optimized Approach (as above): Only one pass through the array, so time complexity is O(n).
• Space Complexity: Both approaches use O(1) extra space, as we only need a few variables.

The optimized solution is efficient and suitable for large arrays.

Summary

To determine if an array is a valid mountain, we simulate climbing up to a peak and then descending, ensuring the peak is not at the ends and there are no plateaus. This approach is efficient, requiring only a single traversal and minimal extra space. The key insight is to use two simple while loops to model the climb and descent, yielding an elegant and robust solution.