# LeetCode 162: Find Peak Element

## Problem Restatement

We are given a 0-indexed integer array `nums`.

A peak element is an element strictly greater than its neighbors.

We need to return the index of any peak element.

The array boundary is treated as negative infinity:

```python
nums[-1] = nums[n] = -infinity
```

So the first element can be a peak if it is greater than the second element. The last element can be a peak if it is greater than the second-to-last element.

The problem requires an `O(log n)` algorithm. Adjacent elements are never equal.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Index of any peak element |
| Peak rule | `nums[i]` is greater than its neighbors |
| Boundary rule | Outside the array counts as negative infinity |
| Required time | `O(log n)` |
| Adjacent values | `nums[i] != nums[i + 1]` |

Example function shape:

```python
def findPeakElement(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3, 1]
```

The value `3` is greater than both neighbors:

```python
3 > 2
3 > 1
```

So the answer is:

```python
2
```

Example 2:

```python
nums = [1, 2, 1, 3, 5, 6, 4]
```

There are two valid peaks.

Index `1` is valid because:

```python
2 > 1
2 > 1
```

Index `5` is also valid because:

```python
6 > 5
6 > 4
```

So either answer is valid:

```python
1
```

or:

```python
5
```

Example 3:

```python
nums = [1]
```

The only element is greater than both outside boundaries.

So the answer is:

```python
0
```

## First Thought: Linear Scan

A direct solution is to check every index.

For each index, compare it with its left and right neighbors.

```python
class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        n = len(nums)

        for i in range(n):
            left = nums[i - 1] if i > 0 else float("-inf")
            right = nums[i + 1] if i + 1 < n else float("-inf")

            if nums[i] > left and nums[i] > right:
                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

Even though the array is not sorted, we can still use binary search by looking at the slope.

At index `mid`, compare:

```python
nums[mid]
nums[mid + 1]
```

If:

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

then the array is going downward at `mid`.

A peak must exist on the left side, including `mid`.

If:

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

then the array is going upward at `mid`.

A peak must exist on the right side.

This works because the outside boundary is negative infinity, and adjacent elements are not equal.

## Why the Slope Tells Us Where a Peak Exists

Suppose:

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

We are climbing upward from `mid` to `mid + 1`.

If the array keeps increasing all the way to the end, the last element is a peak because the right boundary is negative infinity.

If the array stops increasing somewhere, then at the first place where it goes down, that turning point is a peak.

So a peak must exist to the right.

Now suppose:

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

We are going downward from `mid` to `mid + 1`.

If the array keeps decreasing all the way to the start, the first element is a peak because the left boundary is negative infinity.

If the array stopped decreasing earlier, the turning point is a peak.

So a peak must exist at `mid` or to the left.

## Algorithm

Use binary search.

Initialize:

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

While `left < right`:

1. Compute `mid`.
2. Compare `nums[mid]` and `nums[mid + 1]`.
3. If `nums[mid] > nums[mid + 1]`, move `right = mid`.
4. Otherwise, move `left = mid + 1`.

When the loop ends, return `left`.

## Walkthrough

Use:

```python
nums = [1, 2, 1, 3, 5, 6, 4]
```

Start:

```python
left = 0
right = 6
```

Middle:

```python
mid = 3
nums[mid] = 3
nums[mid + 1] = 5
```

Since `3 < 5`, we are climbing.

A peak exists on the right.

Move:

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

Now:

```python
left = 4
right = 6
```

Middle:

```python
mid = 5
nums[mid] = 6
nums[mid + 1] = 4
```

Since `6 > 4`, we are descending.

A peak exists at `mid` or to the left.

Move:

```python
right = mid = 5
```

Now:

```python
left = 4
right = 5
```

Middle:

```python
mid = 4
nums[mid] = 5
nums[mid + 1] = 6
```

Since `5 < 6`, move:

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

Now:

```python
left = 5
right = 5
```

Return:

```python
5
```

The value is:

```python
nums[5] = 6
```

which is a peak.

## Correctness

At every step, the search interval `[left, right]` contains at least one peak.

Initially, the whole array contains at least one peak because the boundaries are negative infinity and adjacent values are distinct.

During the search, we compare `nums[mid]` with `nums[mid + 1]`.

If `nums[mid] > nums[mid + 1]`, then moving left from `mid` either keeps descending until index `0`, making index `0` a peak, or eventually finds a place where the direction changes from rising to falling, which is also a peak. Therefore, a peak exists in `[left, mid]`, so setting `right = mid` preserves the invariant.

If `nums[mid] < nums[mid + 1]`, then moving right from `mid + 1` either keeps rising until the last index, making the last index a peak, or eventually finds a place where the direction changes from rising to falling, which is a peak. Therefore, a peak exists in `[mid + 1, right]`, so setting `left = mid + 1` preserves the invariant.

The loop stops when `left == right`. The interval still contains a peak, and it contains only one index. Therefore, that index is a peak.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | Each step removes about half of the search interval |
| Space | `O(1)` | Only index variables are used |

## Implementation

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

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

            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1

        return left
```

## Code Explanation

We search the full array:

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

The loop continues while more than one candidate remains:

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

Compute the middle:

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

Because `left < right`, `mid + 1` is always a valid index.

If the slope goes down:

```python
if nums[mid] > nums[mid + 1]:
    right = mid
```

we keep the left side, including `mid`.

Otherwise, the slope goes up:

```python
else:
    left = mid + 1
```

we keep the right side.

Finally:

```python
return left
```

returns an index of a peak element.

## Testing

```python
def is_peak(nums, i):
    left = nums[i - 1] if i > 0 else float("-inf")
    right = nums[i + 1] if i + 1 < len(nums) else float("-inf")
    return nums[i] > left and nums[i] > right

def run_tests():
    sol = Solution()

    nums = [1, 2, 3, 1]
    ans = sol.findPeakElement(nums)
    assert is_peak(nums, ans)

    nums = [1, 2, 1, 3, 5, 6, 4]
    ans = sol.findPeakElement(nums)
    assert is_peak(nums, ans)

    nums = [1]
    ans = sol.findPeakElement(nums)
    assert ans == 0

    nums = [1, 2]
    ans = sol.findPeakElement(nums)
    assert ans == 1

    nums = [2, 1]
    ans = sol.findPeakElement(nums)
    assert ans == 0

    nums = [1, 2, 3, 4, 5]
    ans = sol.findPeakElement(nums)
    assert ans == 4

    nums = [5, 4, 3, 2, 1]
    ans = sol.findPeakElement(nums)
    assert ans == 0

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1, 2, 3, 1]` | Peak in the middle |
| `[1, 2, 1, 3, 5, 6, 4]` | Multiple valid peaks |
| `[1]` | Single element |
| `[1, 2]` | Peak at the end |
| `[2, 1]` | Peak at the start |
| Increasing array | Last element is peak |
| Decreasing array | First element is peak |