# LeetCode 941: Valid Mountain Array

## Problem Restatement

We are given an integer array `arr`.

Return `True` if and only if `arr` is a valid mountain array.

A valid mountain array must satisfy three rules:

1. It has at least `3` elements.
2. It strictly increases up to one peak.
3. It strictly decreases after that peak.

The peak cannot be the first element or the last element.

The official statement defines a mountain array as one where there exists an index `i` with `0 < i < arr.length - 1`, such that values strictly increase before `i` and strictly decrease after `i`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `arr` |
| Output | `True` if `arr` is a valid mountain array, otherwise `False` |
| Minimum length | `3` |
| Peak position | Must be inside the array, not at either end |
| Order rule | Strictly increasing, then strictly decreasing |

Function shape:

```python
class Solution:
    def validMountainArray(self, arr: list[int]) -> bool:
        ...
```

## Examples

Example 1:

```python
arr = [2, 1]
```

The length is less than `3`.

So the answer is:

```python
False
```

Example 2:

```python
arr = [3, 5, 5]
```

The array increases from `3` to `5`, but then has another `5`.

A mountain must be strictly increasing and strictly decreasing. Equal adjacent values are not allowed.

So the answer is:

```python
False
```

Example 3:

```python
arr = [0, 3, 2, 1]
```

The array increases:

```text
0 -> 3
```

Then decreases:

```text
3 -> 2 -> 1
```

The peak is `3`, which is neither first nor last.

So the answer is:

```python
True
```

## First Thought: Find the Peak

A valid mountain has one peak.

So we can first walk upward while the next value is larger.

When that stops, we should be at the peak.

Then we walk downward while the next value is smaller.

At the end, the array is valid only if:

1. We climbed at least once.
2. We descended at least once.
3. We reached the end of the array.

## Key Insight

The strict comparisons matter.

The increasing phase uses:

```python
arr[i] < arr[i + 1]
```

The decreasing phase uses:

```python
arr[i] > arr[i + 1]
```

If two adjacent values are equal, neither condition is true, so the scan stops.

That correctly rejects arrays like:

```python
[3, 5, 5]
```

or:

```python
[0, 2, 2, 1]
```

## Algorithm

Let:

```python
n = len(arr)
```

If `n < 3`, return `False`.

Start at index `0`.

Climb while the next value is larger:

```python
while i + 1 < n and arr[i] < arr[i + 1]:
    i += 1
```

After this loop, `i` is the peak candidate.

If `i == 0`, there was no increasing part.

If `i == n - 1`, there was no decreasing part.

In either case, return `False`.

Then descend while the next value is smaller:

```python
while i + 1 < n and arr[i] > arr[i + 1]:
    i += 1
```

At the end, return whether `i` reached the last index.

## Walkthrough

Use:

```python
arr = [0, 3, 2, 1]
```

Start:

```python
i = 0
```

Climb:

| Compare | Result | New `i` |
|---|---|---:|
| `0 < 3` | climb | 1 |
| `3 < 2` | stop | 1 |

Peak candidate is index `1`, value `3`.

It is not the first or last index, so continue.

Descend:

| Compare | Result | New `i` |
|---|---|---:|
| `3 > 2` | descend | 2 |
| `2 > 1` | descend | 3 |

Now `i == n - 1`.

Return:

```python
True
```

## Correctness

The first loop advances exactly through the longest strictly increasing prefix of the array.

When it stops, either the array ended or the next value is not larger. Therefore, the current index is the only possible peak position for a mountain shape.

If that peak candidate is index `0`, then the array never increased. A valid mountain requires an increasing part, so the array is invalid.

If that peak candidate is index `n - 1`, then the array never decreased. A valid mountain requires a decreasing part, so the array is invalid.

The second loop advances exactly through the longest strictly decreasing suffix starting at the peak candidate.

If the second loop reaches the final index, then every element after the peak strictly decreases, so the array has the required mountain form.

If it stops before the final index, then some adjacent pair after the peak fails the strict decreasing rule. Therefore, the array cannot be a valid mountain.

So the algorithm returns `True` exactly for valid mountain arrays.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each index is visited at most once |
| Space | `O(1)` | Only one pointer is stored |

## Implementation

```python
class Solution:
    def validMountainArray(self, arr: list[int]) -> bool:
        n = len(arr)

        if n < 3:
            return False

        i = 0

        while i + 1 < n and arr[i] < arr[i + 1]:
            i += 1

        if i == 0 or i == n - 1:
            return False

        while i + 1 < n and arr[i] > arr[i + 1]:
            i += 1

        return i == n - 1
```

## Code Explanation

We first reject arrays that are too short:

```python
if n < 3:
    return False
```

Then we climb the increasing part:

```python
while i + 1 < n and arr[i] < arr[i + 1]:
    i += 1
```

After climbing, the peak must be inside the array:

```python
if i == 0 or i == n - 1:
    return False
```

Then we walk down the decreasing part:

```python
while i + 1 < n and arr[i] > arr[i + 1]:
    i += 1
```

The array is valid only if this walk reaches the end:

```python
return i == n - 1
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.validMountainArray([2, 1]) is False
    assert s.validMountainArray([3, 5, 5]) is False
    assert s.validMountainArray([0, 3, 2, 1]) is True

    assert s.validMountainArray([0, 1, 2, 3]) is False
    assert s.validMountainArray([3, 2, 1]) is False
    assert s.validMountainArray([0, 2, 3, 2, 1]) is True
    assert s.validMountainArray([0, 2, 2, 1]) is False
    assert s.validMountainArray([1, 3, 2]) is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[2,1]` | Too short |
| `[3,5,5]` | Equal values are invalid |
| `[0,3,2,1]` | Standard valid mountain |
| Increasing only | No descent |
| Decreasing only | No climb |
| Longer valid mountain | Normal case |
| Plateau near peak | Strictness check |
| Length `3` valid case | Smallest valid mountain |