How do you approach Find Peak Element?

Binary search can find a peak in O(log n) time.

What is the time complexity of Find Peak Element?

Time complexity: O(log n). Space complexity: O(1).

What are common mistakes on Find Peak Element?

Computing the midpoint as (low + high) / 2. In a fixed-width integer language that overflows on large ranges; low + (high - low) / 2 does not. An update that fails to shrink the range, which spins forever on a two-element window. Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

gitGood.dev

← Back to problems

Find Peak Element

MediumAlgorithms

Description

A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array `nums`, find a peak element, and return its index. If the array contains multiple peaks, return the index to **any** of the peaks. You may imagine that `nums[-1] = nums[n] = -Infinity`. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array. You must write an algorithm that runs in O(log n) time.

Example 1

Input: nums = [1,2,3,1]

Output: 2

Explanation: 3 is a peak element and your function should return the index number 2.

Example 2

Input: nums = [1,2,1,3,5,6,4]

Output: 5

Explanation: Your function can return either index 1 (peak value 2) or index 5 (peak value 6).

Constraints

- 1 <= nums.length <= 1000 - -2^31 <= nums[i] <= 2^31 - 1 - nums[i] != nums[i + 1] for all valid i.

Find Peak Element: approach, complexity and pitfalls

A medium binary search problem, graded against 7 test cases (4 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

Binary search can find a peak in O(log n) time.
If nums[mid] < nums[mid + 1], a peak must exist on the right side.
If nums[mid] > nums[mid + 1], a peak must exist on the left side (including mid).

The optimal approach

Show the approach: Binary Search

Use binary search. If the middle element is less than its right neighbor, a peak must exist to the right. Otherwise, a peak exists to the left (including mid). This works because we imagine -infinity at both ends.

Time: O(log n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.