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

Function shape:

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

Examples

Example 1:

arr = [0, 1, 0]

The peak value is 1, at index 1.

So the answer is:

1

Example 2:

arr = [0, 2, 1, 0]

The peak value is 2, at index 1.

So the answer is:

1

Example 3:

arr = [0, 10, 5, 2]

The peak value is 10, at index 1.

So the answer is:

1

First Thought: Linear Scan

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

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:

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:

arr[mid]
arr[mid + 1]

There are two cases.

If:

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:

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:

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:

left = mid + 1

4. Otherwise, keep mid as a possible answer:

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

Implementation

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:

left = 0
right = len(arr) - 1

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

while left < right:

We choose the middle index:

mid = (left + right) // 2

Then we compare the middle value with the next value.

If the next value is larger:

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

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

Otherwise:

else:
    right = mid

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

At the end:

return left

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

Testing

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: