# LeetCode 852: Peak Index in a Mountain Array

## Problem Restatement

We are given an integer array `arr`.

The array is guaranteed to be a mountain array. That means:

1. The values strictly increase.
2. Then they reach one peak.
3. After the peak, the values strictly decrease.

We need to return the index of the peak element.

The problem also requires an `O(log n)` solution, so we should use binary search.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A mountain array `arr` |
| Output | The index of the peak element |
| Constraint | `3 <= arr.length <= 10^5` |
| Guarantee | `arr` is a valid mountain array |

Function shape:

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

## Examples

Example 1:

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

The peak value is `1`, at index `1`.

So the answer is:

```python
1
```

Example 2:

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

The peak value is `2`, at index `1`.

So the answer is:

```python
1
```

Example 3:

```python
arr = [0, 10, 5, 2]
```

The peak value is `10`, at index `1`.

So the answer is:

```python
1
```

## First Thought: Linear Scan

The simplest solution is to scan the array and find the first index `i` where:

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

Because the array first increases and then decreases, the first position where the next value is smaller must be the peak.

Code:

```python
class Solution:
    def peakIndexInMountainArray(self, arr: list[int]) -> int:
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                return i

        return -1
```

This works, but it takes `O(n)` time.

The problem asks for `O(log n)`, so we need binary search.

## Key Insight

At any index `mid`, compare:

```python
arr[mid]
arr[mid + 1]
```

There are two cases.

If:

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

then we are still on the increasing side of the mountain.

The peak must be to the right of `mid`.

If:

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

then we are on the decreasing side, or exactly at the peak.

The peak is at `mid` or to the left of `mid`.

This gives us a binary search rule.

## Algorithm

Use two pointers:

```python
left = 0
right = len(arr) - 1
```

While `left < right`:

1. Compute the middle index.
2. Compare `arr[mid]` and `arr[mid + 1]`.
3. If `arr[mid] < arr[mid + 1]`, move right:

```python
left = mid + 1
```

4. Otherwise, keep `mid` as a possible answer:

```python
right = mid
```

When the loop ends, `left == right`.

That index is the peak.

## Correctness

The peak always remains inside the search range `[left, right]`.

If `arr[mid] < arr[mid + 1]`, the array is rising at `mid`. Since the mountain has exactly one peak, the peak must be somewhere after `mid`. Moving `left` to `mid + 1` keeps the peak in the search range.

If `arr[mid] > arr[mid + 1]`, the array is falling after `mid`. This means `mid` may be the peak, or the peak may be before `mid`. Moving `right` to `mid` keeps the peak in the search range.

Each step shrinks the search range while preserving the peak inside it.

When `left == right`, only one possible index remains. Since the peak has never been removed from the range, that index must be the peak.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Binary search halves the range each step |
| Space | `O(1)` | Only a few variables are used |

## Implementation

```python
class Solution:
    def peakIndexInMountainArray(self, arr: list[int]) -> int:
        left = 0
        right = len(arr) - 1

        while left < right:
            mid = (left + right) // 2

            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            else:
                right = mid

        return left
```

## Code Explanation

We start with the full array:

```python
left = 0
right = len(arr) - 1
```

The loop continues while there is more than one possible index:

```python
while left < right:
```

We choose the middle index:

```python
mid = (left + right) // 2
```

Then we compare the middle value with the next value.

If the next value is larger:

```python
if arr[mid] < arr[mid + 1]:
    left = mid + 1
```

we are still climbing, so the peak is on the right.

Otherwise:

```python
else:
    right = mid
```

we are falling, or standing at the peak, so we keep `mid` and discard the right side.

At the end:

```python
return left
```

`left` and `right` point to the same index, which is the peak.

## Testing

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

    assert s.peakIndexInMountainArray([0, 1, 0]) == 1
    assert s.peakIndexInMountainArray([0, 2, 1, 0]) == 1
    assert s.peakIndexInMountainArray([0, 10, 5, 2]) == 1
    assert s.peakIndexInMountainArray([1, 3, 5, 4, 2]) == 2
    assert s.peakIndexInMountainArray([1, 2, 3, 4, 5, 3, 1]) == 4

    print("all tests passed")

test_peak_index_in_mountain_array()
```

Test meaning:

| Test | Why |
|---|---|
| `[0, 1, 0]` | Minimum mountain shape |
| `[0, 2, 1, 0]` | Peak near the left |
| `[0, 10, 5, 2]` | Official-style descending tail |
| `[1, 3, 5, 4, 2]` | Peak in the middle |
| `[1, 2, 3, 4, 5, 3, 1]` | Longer increasing side |