# Valid Mountain Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/valid-mountain-array)
Canonical: https://scaleengineer.com/dsa/problems/valid-mountain-array
**Data structures:** Array
---
## Problem
Given an array of integers `arr`, return _`true` if and only if it is a valid mountain array_.

Recall that arr is a mountain array if and only if:

* `arr.length >= 3`
* There exists some `i` with `0 < i < arr.length - 1` such that:  
  * `arr[0] < arr[1] < ... < arr[i - 1] < arr[i] `
  * `arr[i] > arr[i + 1] > ... > arr[arr.length - 1]`
![](https://assets.glich.co/dsa/valid-mountain-array/image0.png) 

**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`

# Approaches
## Two Passes: Find Peak then Verify
This approach breaks the problem into two distinct steps. First, we iterate through the array to find the peak (the maximum element). Then, we perform two more traversals: one from the start to the peak and another from the peak to the end, to verify the mountain properties.
**Time:** O(N). The first pass to find the peak takes O(N). The subsequent two passes to verify the slopes take O(peakIndex) and O(N - peakIndex) respectively, which sum up to O(N). The total time complexity is O(N) + O(N) = O(N). · **Space:** O(1). We only use a few variables to store the peak index and loop counters.
**Pros:** Conceptually straightforward and easy to understand.; Separates the logic of finding the peak and verifying the slopes, which can make debugging easier.
**Cons:** Requires multiple passes over the array (one to find the peak, and up to two more to verify the slopes), which can be slightly less performant in practice than a single-pass solution.; The logic is split into separate parts, which might make the code slightly longer.
### Explanation
The core idea is to first locate the highest point of the potential mountain. We traverse the array to find the index of the maximum element. Let's call this `peakIndex`.

According to the definition of a mountain array, the peak cannot be the first or the last element. So, if `peakIndex` is 0 or `arr.length - 1`, we can immediately return `false`. This also handles arrays that are purely increasing or decreasing.

Next, we need to verify the two slopes of the mountain.
- We check the 'uphill' part: from the beginning of the array up to `peakIndex`. We iterate from index 0 to `peakIndex - 1` and ensure that `arr[i] < arr[i+1]` for all `i` in this range. If we find any pair that violates this (i.e., `arr[i] >= arr[i+1]`), it's not a valid mountain, so we return `false`.
- Then, we check the 'downhill' part: from `peakIndex` to the end of the array. We iterate from `peakIndex` to `arr.length - 2` and ensure that `arr[i] > arr[i+1]` for all `i` in this range. If we find any pair that violates this (i.e., `arr[i] <= arr[i+1]`), it's not a valid mountain, so we return `false`.

If the array passes all these checks, it is a valid mountain array, and we return `true`. A preliminary check for `arr.length < 3` is also necessary at the beginning.

```java
class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return false;
        }

        // Find the peak index
        int maxVal = -1;
        int peakIndex = -1;
        for (int i = 0; i < n; i++) {
            if (arr[i] > maxVal) {
                maxVal = arr[i];
                peakIndex = i;
            }
        }

        // Peak cannot be the first or last element
        if (peakIndex == 0 || peakIndex == n - 1) {
            return false;
        }

        // Check the uphill part
        for (int i = 0; i < peakIndex; i++) {
            if (arr[i] >= arr[i + 1]) {
                return false;
            }
        }

        // Check the downhill part
        for (int i = peakIndex; i < n - 1; i++) {
            if (arr[i] <= arr[i + 1]) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- If the array length `n` is less than 3, it cannot be a mountain array, so return `false`.
- Find the index of the maximum element in the array. Let's call this `peakIndex`.
- If there are multiple maximum elements, the index of the first one is typically found.
- According to the definition, the peak cannot be the first or the last element. If `peakIndex` is 0 or `n - 1`, return `false`.
- Verify the strictly increasing part (the 'uphill' slope). Iterate from index 0 to `peakIndex - 1`. If `arr[i] >= arr[i+1]` for any `i`, it's not a valid mountain. Return `false`.
- Verify the strictly decreasing part (the 'downhill' slope). Iterate from `peakIndex` to `n - 2`. If `arr[i] <= arr[i+1]` for any `i`, it's not a valid mountain. Return `false`.
- If all the above checks pass, the array is a valid mountain. Return `true`.

## One Pass: Walk Up and Down the Mountain
This is the most efficient approach, solving the problem in a single pass through the array. The idea is to simulate walking up the mountain from the left and then walking down to the right, ensuring we reach the end.
**Time:** O(N). The pointer `i` traverses each element of the array at most once. · **Space:** O(1). We only use a constant amount of extra space for the pointer `i` and length `n`.
**Pros:** Highly efficient, as it solves the problem in a single pass.; Elegant and concise code.; Avoids the overhead of multiple loops over the same data.
**Cons:** The logic, while concise, might be slightly less intuitive at first glance compared to explicitly finding the peak and then verifying.
### Explanation
We use a single pointer, let's call it `i`, to traverse the array. The entire process can be thought of as a single journey over the mountain.

First, we handle the base case: if the array has fewer than 3 elements, it cannot be a mountain, so we return `false`.

We start `i` at index 0 and 'climb up' the mountain. We advance `i` as long as we are within the array bounds and the next element is strictly greater than the current one (`arr[i] < arr[i+1]`). This loop finds the start of the peak or the end of the increasing sequence.

After the 'climb up' loop, `i` points to the potential peak. We must perform a crucial check here. If `i` is still 0, it means the array never increased (e.g., `[5,4,3]`). If `i` has reached the last index (`arr.length - 1`), it means the array only increased (e.g., `[1,2,3]`). In both cases, it's not a valid mountain, so we return `false`. This ensures the peak is not at the ends of the array.

Next, we 'climb down' from the peak. We continue advancing `i` as long as we are within bounds and the next element is strictly smaller than the current one (`arr[i] > arr[i+1]`).

After the 'climb down' loop, if we have successfully traversed a valid mountain, our pointer `i` should have landed exactly on the last index of the array (`arr.length - 1`). The final step is to check if `i == arr.length - 1`. If it is, it means we climbed up to a peak and then climbed down to the very end, with no flat parts or upward slopes on the way down. This confirms a valid mountain, and we return `true`. Otherwise, we return `false`.

```java
class Solution {
    public boolean validMountainArray(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return false;
        }

        int i = 0;

        // Walk up the mountain
        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 the mountain
        while (i + 1 < n && arr[i] > arr[i + 1]) {
            i++;
        }

        // If we reached the end, it's a valid mountain
        return i == n - 1;
    }
}
```
### Algorithm
- Let `n` be the length of the array. If `n < 3`, return `false`.
- Initialize a pointer `i = 0`.
- **Climb up:** Use a `while` loop to increment `i` as long as `i+1 < n` and `arr[i] < arr[i+1]`. This loop continues as long as the array is strictly increasing.
- **Check peak validity:** After the first loop, `i` is at the peak. The peak cannot be the first or last element. So, if `i == 0` (never climbed up) or `i == n - 1` (only climbed up), return `false`.
- **Climb down:** Use another `while` loop to increment `i` as long as `i+1 < n` and `arr[i] > arr[i+1]`. This loop continues as long as the array is strictly decreasing.
- **Final check:** If the pointer `i` has reached the end of the array (`i == n - 1`), it means we successfully climbed up and then climbed down to the very end. This is a valid mountain, so return `true`. Otherwise, return `false`.

# Solutions
### Java

```java
class Solution { public boolean validMountainArray ( int [] arr ) { int n = arr . length ; if ( n < 3 ) { return false ; } int l = 0 , r = n - 1 ; while ( l + 1 < n - 1 && arr [ l ] < arr [ l + 1 ]) { ++ l ; } while ( r - 1 > 0 && arr [ r ] < arr [ r - 1 ]) { -- r ; } return l == r ; } }
```

### CPP

```cpp
class Solution { public: bool validMountainArray ( vector < int >& arr ) { int n = arr . size (); if ( n < 3 ) return 0 ; int l = 0 , r = n - 1 ; while ( l + 1 < n - 1 && arr [ l ] < arr [ l + 1 ]) ++ l ; while ( r - 1 > 0 && arr [ r ] < arr [ r - 1 ]) -- r ; return l == r ; } };
```

### Python

```python
class Solution : def validMountainArray ( self , arr : List [ int ]) -> bool : n = len ( arr ) if n < 3 : return False l , r = 0 , n - 1 while l + 1 < n - 1 and arr [ l ] < arr [ l + 1 ]: l += 1 while r - 1 > 0 and arr [ r ] < arr [ r - 1 ]: r -= 1 return l == r
```