LeetCode 852 - Peak Index in a Mountain Array

LeetCode Problem 852

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

This problem gives us a special type of array called a mountain array. A mountain array strictly increases until it reaches a single peak element, then strictly decreases afterward.

In other words, there exists some index i such that:

• arr[0] < arr[1] < ... < arr[i]
• arr[i] > arr[i + 1] > ... > arr[n - 1]

Our task is to return the index of this peak element.

For example, in the array [0, 10, 5, 2], the values increase from 0 to 10, then decrease from 10 to 5 to 2. Therefore, the peak element is 10, and its index is 1.

The important requirement is that the solution must run in O(log n) time complexity. This immediately suggests that a linear scan is not sufficient for the intended optimal solution. Since the array has a structured property, increasing then decreasing, binary search becomes a natural candidate.

The constraints also reinforce this idea:

• The array length can be as large as 10^5
• A logarithmic solution is explicitly required
• The array is guaranteed to be a valid mountain array

That final guarantee is extremely important because it means:

• There is always exactly one peak
• The peak is never at the first or last index
• We never need to handle invalid input shapes

A naive implementation could still make mistakes near the boundaries of the array, especially when checking neighboring elements. Since binary search often compares arr[mid] with arr[mid + 1], careful boundary management is necessary to avoid out-of-range errors.

Another subtle issue is determining which direction to move during binary search. The key observation is that if we are on the increasing slope, the peak lies to the right. If we are on the decreasing slope, the peak lies to the left or at the current position.

Approaches

Brute Force Approach

The simplest solution is to scan through the array and locate the element that is greater than both of its neighbors.

We iterate from index 1 to n - 2 and check:

arr[i] > arr[i - 1] and arr[i] > arr[i + 1]

Because the problem guarantees a valid mountain array, the first index satisfying this condition is the peak.

This approach is correct because the mountain property guarantees exactly one local maximum.

However, the time complexity is O(n), which does not satisfy the required O(log n) complexity constraint.

Optimal Binary Search Approach

The mountain structure gives us a monotonic pattern:

• Before the peak, values are increasing
• After the peak, values are decreasing

This means we can use binary search to determine which side of the peak we are currently on.

At any midpoint:

• If arr[mid] < arr[mid + 1], we are on the increasing slope, so the peak must be to the right
• If arr[mid] > arr[mid + 1], we are on the decreasing slope, so the peak is at mid or to the left

This allows us to repeatedly eliminate half of the search space, producing an O(log n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scan the array and find the local maximum
Optimal	O(log n)	O(1)	Use binary search on the mountain structure

Algorithm Walkthrough

1. Initialize two pointers, left and right, representing the current search range.

We start with:

left = 0
right = len(arr) - 1

2. Continue searching while left < right.

The loop stops only when both pointers converge to the peak index. 3. Compute the midpoint:

mid = (left + right) // 2

4. Compare arr[mid] with arr[mid + 1].

This comparison tells us whether we are on the increasing or decreasing side of the mountain. 5. If arr[mid] < arr[mid + 1], we are on the increasing slope.

Since the values are still rising, the peak must lie somewhere to the right of mid.

Move the search range:

left = mid + 1

6. Otherwise, we are on the decreasing slope.

This means mid could already be the peak, or the peak lies further left.

Move the search range:

right = mid

7. Eventually, left and right converge to the same index.

That index is the peak index. 8. Return left or right, since they are equal.

Why it works

The algorithm maintains the invariant that the peak always lies within the current search interval [left, right].

When arr[mid] < arr[mid + 1], the slope is increasing, so the peak must exist to the right. We safely discard the left half.

When arr[mid] > arr[mid + 1], the slope is decreasing, meaning the peak is at mid or to the left. We safely discard the right half beyond mid.

Because each iteration removes half the remaining search space, the algorithm converges to the peak efficiently in logarithmic time.

Python Solution

from typing import List

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

The implementation begins by initializing the binary search boundaries, left and right.

Inside the loop, we compute the midpoint and compare arr[mid] with arr[mid + 1].

If the sequence is still increasing at mid, the peak must lie to the right, so we move left forward.

Otherwise, the sequence is decreasing, meaning the peak is at mid or earlier, so we move right backward to mid.

The loop continues shrinking the search interval until both pointers meet. At that moment, the converged index is guaranteed to be the peak.

The implementation uses constant extra memory and avoids unnecessary checks because the mountain array guarantee ensures valid neighboring comparisons.

Go Solution

func peakIndexInMountainArray(arr []int) int {
    left := 0
    right := len(arr) - 1

    for left < right {
        mid := (left + right) / 2

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

    return left
}

The Go implementation follows the exact same binary search logic as the Python version.

Go slices provide direct indexed access similar to Python lists, so the translation is straightforward.

There are no special nil checks because the problem guarantees the array length is at least 3.

Integer overflow is not a practical concern here because the maximum array size is only 10^5, but using (left + right) / 2 remains safe under these constraints.

Worked Examples

Example 1

Input:

arr = [0, 1, 0]

left	right	mid	arr[mid]	arr[mid + 1]	Action
0	2	1	1	0	decreasing, move right = mid
0	1	0	0	1	increasing, move left = mid + 1

Now:

left = 1
right = 1

Return:

1

Example 2

Input:

arr = [0, 2, 1, 0]

left	right	mid	arr[mid]	arr[mid + 1]	Action
0	3	1	2	1	decreasing, move right = mid
0	1	0	0	2	increasing, move left = mid + 1

Now:

left = 1
right = 1

Return:

1

Example 3

Input:

arr = [0, 10, 5, 2]

left	right	mid	arr[mid]	arr[mid + 1]	Action
0	3	1	10	5	decreasing, move right = mid
0	1	0	0	10	increasing, move left = mid + 1

Now:

left = 1
right = 1

Return:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary search halves the search space each iteration
Space	O(1)	Only a few pointer variables are used

The binary search repeatedly discards half of the remaining array, leading to logarithmic time complexity.

No additional data structures are allocated, so the extra memory usage remains constant.

Test Cases

sol = Solution()

assert sol.peakIndexInMountainArray([0, 1, 0]) == 1  # smallest valid mountain
assert sol.peakIndexInMountainArray([0, 2, 1, 0]) == 1  # peak near beginning
assert sol.peakIndexInMountainArray([0, 10, 5, 2]) == 1  # larger peak value
assert sol.peakIndexInMountainArray([1, 3, 5, 4, 2]) == 2  # peak in middle
assert sol.peakIndexInMountainArray([0, 5, 10, 7, 3, 1]) == 2  # longer mountain
assert sol.peakIndexInMountainArray([0, 1, 2, 3, 2, 1]) == 3  # peak closer to end
assert sol.peakIndexInMountainArray([0, 1000000, 999999]) == 1  # maximum value range
assert sol.peakIndexInMountainArray([3, 5, 3, 2, 0]) == 1  # short decreasing side
assert sol.peakIndexInMountainArray([0, 2, 4, 6, 8, 7, 5, 3, 1]) == 4  # larger mountain

Test	Why
[0, 1, 0]	Smallest valid mountain array
[0, 2, 1, 0]	Peak near the beginning
[0, 10, 5, 2]	Large peak value
[1, 3, 5, 4, 2]	Peak exactly in the middle
[0, 5, 10, 7, 3, 1]	Longer mountain shape
[0, 1, 2, 3, 2, 1]	Peak closer to the end
[0, 1000000, 999999]	Maximum allowed element values
[3, 5, 3, 2, 0]	Very short increasing section
[0, 2, 4, 6, 8, 7, 5, 3, 1]	Larger input with clear peak

Edge Cases

One important edge case is the smallest possible mountain array, such as [0, 1, 0]. Binary search implementations can easily make boundary mistakes when the array size is tiny. This implementation handles it correctly because the loop condition left < right safely terminates once both pointers converge.

Another important case is when the peak is very close to the beginning, such as [0, 5, 3, 2, 1]. Some incorrect implementations assume the peak is near the middle and fail to move the search boundaries properly. Here, comparing arr[mid] with arr[mid + 1] correctly identifies that the slope is descending and narrows the search leftward.

A third important case is when the peak is near the end, such as [0, 1, 2, 3, 4, 2]. In this situation, several iterations occur on the increasing slope before the search converges. The algorithm correctly keeps moving left forward until it reaches the peak.

Another subtle edge case involves very large values, such as [0, 1000000, 999999]. Since the algorithm only performs comparisons and does not compute arithmetic involving array values, large numbers do not create overflow or precision issues.

Finally, arrays with long increasing and decreasing sections can expose inefficient implementations. A linear scan would take O(n) time, but this binary search solution remains efficient because each iteration cuts the remaining search space in half.