Peak Index in a Mountain Array
Medium · Binary Search · Array · Binary Search
Problem
You are given an integer array arr that is a *mountain*: its values strictly increase up to a single peak and then strictly decrease. The peak is never the first or last element.
Return the index of the peak element. Solve it in O(log n) time.
Examples
Input: arr = [1,4,8,6,2] Output: 2
8 at index 2 is larger than both neighbors.
Input: arr = [0,3,1] Output: 1
The peak 3 sits at index 1.
Input: arr = [2,5,7,9,10,4] Output: 4
Values rise until 10 at index 4, then fall.
Constraints
- 3 <= len(arr) <= 10^5
- 0 <= arr[i] <= 10^6
- arr is guaranteed to be a mountain array
Approaches
- Walk up from the left — time O(n), space O(1)
Follow-up
What if the array may have plateaus (equal neighbors) on its slopes? Then arr[mid] == arr[mid + 1] says nothing about the side, and no algorithm can beat O(n) in the worst case: a single bump hidden in a flat line can be anywhere.
Related problems
Start free on Cariara · Coding problems · System design studio
