Find Peak Element

A peak is an element that is strictly greater than its neighbours.

You are given a 0-indexed integer array nums. Return the index of any peak element — if the terrain has several summits, any one of them is a correct answer.

Treat the positions just outside the array as bottomless cliffs: imagine nums[-1] and nums[n] are both -∞. A boundary element therefore only needs to beat its one real neighbour. No two adjacent elements are equal.

Your algorithm must run in O(log n) time.

Hints

· Stuck? Reveal one nudge at a time.

You only need an element that beats its two neighbours — not the global maximum. What does the required O(log n) whisper about the technique, even though the array is not sorted?

Stand at any middle index and compare nums[mid] with nums[mid + 1]. If the ground rises to the right, can the right half really contain no peak? Remember the array ends in a virtual cliff of negative infinity.

Binary search on the slope: while lo < hi, take mid; if nums[mid] > nums[mid + 1] a peak lies at mid or left (hi = mid), otherwise strictly right (lo = mid + 1). When lo == hi, that index is a peak.

Common doubts

Binary search never truly required sorted data; it requires a way to look at the middle and discard half with certainty. Here the slope at mid provides that certainty: a rising slope proves a peak exists to the right, a falling slope proves one exists at mid or to the left. Sortedness is just the most familiar source of such a guarantee.

The global maximum of the array is strictly greater than every other element, so it beats its own neighbours — and the virtual -∞ walls mean even a maximum sitting on the boundary qualifies. Every array of distinct-neighbour values has at least one peak.

No. The loop runs only while lo < hi, so mid = (lo + hi) / 2 always satisfies mid < hi <= n - 1, which makes mid + 1 <= n - 1 a valid index.

Some valid peak, not necessarily the first or the tallest. That is fine: the problem accepts the index of any peak, and that freedom is exactly what makes the halving argument legal.

Interview follow-ups

· What an interviewer asks next.

The slope at mid can be flat, so neither half can be safely discarded — an adversary can hide the peak on either side. In the worst case (all values equal except one) any algorithm needs O(n) looks. Discussing this degradation is exactly what the interviewer wants to hear.

Binary search over columns: take the middle column, find its maximum in O(rows), and compare that cell with its left and right neighbours. Move toward the larger side — the same rising-slope certificate in two dimensions. That is the problem Find a Peak Element II, running in O(rows · log(cols)).

No. On arbitrary unsorted data an adversary argument shows every unexamined element could secretly be the maximum, forcing Ω(n) looks. The relaxation from the maximum to any peak is precisely what buys the logarithmic bound.

Fun facts

Peak finding is the famous opening example of MIT's introductory algorithms course — chosen precisely because it demolishes the myth that binary search needs a sorted array.
The walk-uphill certificate is a discrete cousin of hill climbing in optimization: gradient ascent also promises only a local maximum, not the global one — and for the same reason.
The same keep-the-certain-half reasoning powers Find Minimum in Rotated Sorted Array, Search in Rotated Sorted Array, and the 2-D grid variant Find a Peak Element II.

Asked at

GoogleAmazonMetaMicrosoftBloombergUber

Frequently Sometimes Occasionally

Example 1

Input: nums = [1,2,3,1]
Output: 2
nums[2] = 3 is greater than both neighbours (2 and 1), so index 2 is a peak.

Example 2

Input: nums = [1,2,1,3,5,6,4]
Output: 5
There are two peaks: index 1 (value 2) and index 5 (value 6). Returning either index is accepted.

Example 3

Input: nums = [5,4,3,2,1]
Output: 0
The virtual cliff before index 0 counts as -∞, so nums[0] = 5 only has to beat nums[1] = 4.

Constraints

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

Find Peak Element is the problem that breaks binary search out of its cage. Most learners believe binary search needs a sorted array — this tutorial shows it only needs a guarantee about which half to keep, and by the end you will locate a summit in a completely unsorted landscape in O(log n) leaps.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary search invariant. The habit of maintaining a window that provably contains an answer and shrinking it by half every step.

Strict neighbour inequality. The guarantee nums[i] != nums[i + 1] means every step of the terrain is decisively uphill or downhill — never flat. Flat ground would make the midpoint slope indecisive.

Proof by certificate. Discarding half the array is only legal when you can argue that the half you keep must still contain an answer.

Understand the problem

In plain English: find any index whose value beats both of its neighbours, where the imaginary values just outside the array count as -∞.

Formally: given nums with nums[i] != nums[i + 1] for all valid i, return any index i such that nums[i - 1] < nums[i] > nums[i + 1] (with nums[-1] = nums[n] = -∞), in O(log n) time.

Worked example 1 — nums = [1,2,3,1]

index:   0   1   2   3
value:   1   2   3   1
-∞ ↗ 1 ↗ 2 ↗ 3 ↘ 1 ↘ -∞
             ▲
       peak at index 2

Worked example 2 — nums = [1,2,1,3,5,6,4]

index:   0   1   2   3   4   5   6
value:   1   2   1   3   5   6   4
             ▲                ▲
     summit at 1      summit at 5
     returning either index is correct

Clarifying questions

Asking two or three sharp questions before touching the keyboard is how senior engineers show they solve the right problem, not just a problem.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Can two adjacent elements ever be equal?”

No — the statement guarantees nums[i] != nums[i + 1]. This matters enormously: a flat plateau would make the slope at the midpoint indecisive and break the halving argument.

“Is a single-element array valid, and what is its answer?”

Yes — with both virtual walls at negative infinity, index 0 is automatically a peak.

Edge cases

“What should I return for a strictly increasing or strictly decreasing array?”

Increasing: the last index is the only peak (it beats the right cliff). Decreasing: index 0. Both follow directly from the virtual cliffs at the ends.

“If several peaks exist, is any one of them accepted?”

Yes — the problem asks for the index of any peak, and that freedom is exactly what lets a half-discarding search work.

Constraints and scale

“Is the O(log n) requirement strict even though n is at most 1000?”

Treat it as strict. The input is small, but the requirement is the whole point of the exercise — a linear scan answers the question while failing the interview.

The ideal opening — say it like this

Before I code, let me confirm the guarantees.

Adjacent elements are never equal, so every slope is strictly up or down — correct?

If multiple peaks exist, returning any single one is accepted?

Since you are asking for O(log n), I will binary search on the slope direction instead of scanning.

Key observations

1Aha

A peak always exists — the cliffs guarantee it

The global maximum of the array beats every element, so in particular it beats its own neighbours — and the virtual -∞ walls mean even a boundary maximum qualifies. An answer is never in doubt; the only question is finding one fast.

-∞ | ....terrain.... | -∞
     the highest point of any terrain
     is strictly above both its neighbours

2Aha

The slope at mid certifies which half must contain a peak

Suppose nums[mid] < nums[mid + 1] — the ground rises to the right. Follow that rise: either it keeps climbing all the way to the last index (a peak against the right cliff), or it turns downhill somewhere — and the turning point is a peak. Either way, a peak certainly lives strictly to the right of mid. The mirror argument holds when the ground falls: a peak lives at mid or to its left.

nums[mid] < nums[mid+1]:   mid ↗ ... the rise must crest
                           somewhere before the -∞ cliff
→ keep (mid, hi], discard the rest — with certainty

3Aha

Sorted was never the requirement — a discard certificate is

Maintain the invariant: the window [lo, hi] contains at least one peak. It starts true (Observation 1). Both updates — hi = mid on a falling slope, lo = mid + 1 on a rising slope — preserve it (Observation 2). When lo == hi, the window is a single index that still must hold a peak. That is classic binary search, running on a completely unsorted array.

Brute force vs optimal

	Linear scan	Binary search on the slope
Time	O(n)	O(log n)
Space	O(1)	O(1)
Meets the stated bound

Full, runnable code for both approaches lives in the Approaches selector below.

Summary

Key takeaway

Binary search runs on certainty, not sortedness: whenever one comparison at the middle proves which half must contain an answer, you may halve. The walk-uphill certificate you learned here reappears in rotated-array searches and the 2-D peak variant.

lo ← 0, hi ← n − 1
while lo < hi:
    mid ← (lo + hi) / 2          # mid < hi, so mid+1 is safe
    if nums[mid] > nums[mid+1]:  hi ← mid       # falling → peak at mid or left
    else:                        lo ← mid + 1   # rising → peak strictly right
return lo