Workspace

Problem workspace

3 day streakD

Find a Peak Element

MediumBinary SearchRotations & structure

The challenge

Return any index whose value is strictly larger than both neighbors. Outside the array, imagine values of −∞.

Adjacent values differ. Empty input returns −1. The array does not need to be sorted.

Example

[1, 2, 3, 1] → 2; [1, 3, 2, 4, 1] has peaks at 1 and 3.

Use the walkthrough below to inspect the input and each state change.

See Peak search, step by step

Inspect the comparison, the invariant, and the next boundary.

Inclusive candidate indices
L = 0 · mid = — · R = 310213213
Current comparisonResolved positionNumbers below = indices
Left
0
Middle
—
Right
3
Step 01 / 4

Start with the candidate indices

The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.

left = 0; right = 3

Recorded result so far

Not resolved
View exact input

Input: [1,2,3,1]

Put it into code

Follow the slope between mid and mid + 1. An uphill direction guarantees that the retained half contains a peak.

Indices are zero-based. C++ uses C++17 or later.

def find_peak(nums):
    if not nums:
        return -1
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            right = mid
    return left

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap