Find Peak Element
Medium · Binary Search · Array · Binary Search
Problem
A peak is an element strictly greater than both of its neighbors. Treat the positions just outside the array as negative infinity, so nums[-1] = nums[n] = -∞; this means the first or last element can be a peak.
Given an integer array nums in which no two adjacent elements are equal, return the index of any peak. If there are several peaks, any of them is accepted.
Your algorithm must run in O(log n) time.
Examples
Input: nums = [2,6,4,1] Output: 1
6 at index 1 is larger than 2 and 4, and it is the only peak.
Input: nums = [9,5,3] Output: 0
The first element beats its only neighbor and the -∞ before it.
Input: nums = [1,2,3,1] Output: 2
3 at index 2 is larger than 2 and 1.
Constraints
- 1 <= len(nums) <= 1000
- -2^31 <= nums[i] <= 2^31 - 1
- nums[i] != nums[i + 1] for every valid i
Approaches
- Baseline: scan for the first descent — time O(n), space O(1)
Follow-up
The same idea works on a grid: binary search the columns, taking each column's largest cell and moving toward a larger horizontal neighbor, for O(m log n). Without the "no two neighbors equal" rule it fails: on a flat stretch you cannot tell which side rises.
Related problems
Start free on Cariara · Coding problems · System design studio
