Peak Index in a Mountain Array Solution

Problem

Given an array that first strictly increases then strictly decreases (a "mountain"), return the index of the peak element — the point where the array switches from going up to going down.

Input: arr = [0, 2, 1, 0]
Output: 1
Explanation: arr[1] = 2 is the peak — it's greater than both its neighbors.

A counter-example: [0, 1, 2, 3] is not a mountain array — it never decreases, so no peak exists (the problem guarantees input is always a valid mountain).

Intuition

The problem asks for the index where the array transitions from ascending to descending. At any midpoint, comparing the midpoint to its right neighbor tells you exactly which half the peak is in: if the array is still climbing, the peak is to the right; if it has already started falling, the peak is at or to the left. This lets you eliminate half the array at every step, turning a linear scan into a binary search.

Approach 1 — Linear Scan

Scan left to right. The first position where the array stops climbing — where the current element is greater than the next — is the peak.

Iterate from index 1 to the second-to-last element.
At each index, check if arr[current] > arr[current + 1].
If so, return current — this is the peak.

1def peakIndexInMountainArray(arr: list[int]) -> int:
2    for i in range(1, len(arr) - 1):
3        if arr[i] > arr[i + 1]:  # array has started descending, peak found
4            return i
5    return -1  # unreachable given valid mountain input

Time: O(n) — in the worst case the peak is at the last valid position.

Space: O(1) — only two variables used.

Approach 2 — Binary Search

At any midpoint mid, compare arr[mid] to arr[mid + 1]:

If arr[mid] < arr[mid + 1], the array is still ascending, so the peak is to the right — move left to mid + 1.
Otherwise, the array is descending or at the peak — move right to mid (the peak could be exactly at mid).

Initialize left = 0, right = len(arr) - 1.
While left < right:
- Compute mid = (left + right) // 2.
- If arr[mid] < arr[mid + 1], set left = mid + 1.
- Else set right = mid.
Return left — the search converges to the peak index.

1def peakIndexInMountainArray(arr: list[int]) -> int:
2    left, right = 0, len(arr) - 1
3    while left < right:
4        mid = (left + right) // 2
5        if arr[mid] < arr[mid + 1]:  # still ascending, peak is to the right
6            left = mid + 1
7        else:                         # descending or at peak, peak is here or left
8            right = mid
9    return left

Time: O(log n) — search space halves at every step.

Space: O(1) — only three pointer variables used.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n)	O(1)	Small arrays or when clarity matters more than performance
Binary Search	O(log n)	O(1)	Default choice; always preferred for this problem

Common Mistakes

Using while left <= right with arr[mid + 1] — when left == right == mid, mid + 1 is out of bounds. The condition while left < right guarantees mid < right, so arr[mid + 1] is always a valid index.
Setting right = mid - 1 in the descending branch — the peak could be exactly at mid (since arr[mid] >= arr[mid + 1] includes equality at the peak). Using mid - 1 skips the correct answer.
Returning the last mid instead of left — the loop exits when left == right, which is the peak. The last computed mid value is typically one step behind; always return left (or right).
Not realizing the mid + 1 comparison is safe in the binary search — because mid = (left + right) // 2 always produces mid < right when left < right, so mid + 1 <= right <= len(arr) - 1.

Peak Index in a Mountain Array — Solution