162. Find Peak Element

A peak is any element strictly greater than its neighbours. Even though the array is not sorted, you can find one in O(log n) by following the uphill slope: compare nums[mid] with nums[mid+1] and walk toward the rise.

● MediumBinary SearchTypeScript

PROBLEM What we're solving

Return the index of any peak — an element strictly greater than both neighbours — in a possibly unsorted array nums. Treat the out-of-bounds neighbours as -∞, so a peak always exists. For example, nums=[1,2,1,3,5,6,4] → 5 (value 6); index 1 (value 2) is also a valid answer. The requirement is O(log n) time, which rules out a plain scan.

KEY IDEA Walk uphill — a rise must lead to a peak

Insight → look at nums[mid] versus its right neighbour nums[mid+1]. If nums[mid] < nums[mid+1] you are on an uphill slope, and because the far-right edge falls off to -∞, the rising values must eventually turn down — a peak is guaranteed to the right. Otherwise you are flat/downhill, so mid itself or something to its left is a peak. Either way you safely discard half the array.

RECIPE Binary search on the slope

0 · Half-open bounds. lo = 0, hi = nums.length - 1, loop while lo < hi (strict — we converge the window to a single cell rather than test for a hit).
1 · Overflow-safe mid. mid = lo + Math.floor((hi - lo) / 2). Because lo < hi, mid + 1 is always a valid index — no out-of-bounds read.
2 · Rising → go right. If nums[mid] < nums[mid+1], a peak lies to the right, so lo = mid + 1 (discard mid, it can't be the peak — its right neighbour is bigger).
3 · Falling → go left (keep mid). Otherwise mid could be the peak, so hi = mid — do not use mid - 1, or you might discard the only peak.
4 · Converge. When lo === hi the window is one cell — that index is a peak. Return lo.

Classic confusion → the asymmetry of the updates trips people up: lo = mid + 1 but hi = mid (not mid - 1). In the rising case mid is provably not a peak so you may skip it; in the falling case mid is still a candidate so you must keep it. Mixing these up either loops forever or skips the answer.

COST Complexity & alternatives

Linear scan

O(n)

Walk until a value stops rising. Correct, but violates the O(log n) ask.

Binary search on slope

O(log n)

O(log n) time; O(1) space.

Why binary search works without sorting

Binary search normally needs a sorted array, but it really only needs a monotone decision: at every mid the slope tells you a half that is guaranteed to contain a peak. With the -∞ sentinels at both ends, that guarantee always holds, so halving is always safe.

Pattern transfer → the "binary search on a slope / predicate" idea drives Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, and Peak Index in a Mountain Array. Whenever a comparison of neighbouring or boundary elements reveals which half holds the answer, reach for this template.

RUN IT Follow the rising slope until the window collapses

nums =

step 0 / 7

STARTSearch begins. lo=0, hi=6. Amber cells are the active window. Out-of-bounds neighbours count as -∞, so a peak always exists.

1function findPeakElement(nums: number[]): number {
2▶  let lo = 0;
3▶  let hi = nums.length - 1;
4 
5  while (lo < hi) {
6    const mid = lo + Math.floor((hi - lo) / 2);
7    if (nums[mid] < nums[mid + 1]) {
8      lo = mid + 1;   // uphill to the right -> a peak lies right
9    } else {
10      hi = mid;       // downhill (or equal) -> a peak is mid or left
11    }
12  }
13  return lo;   // lo === hi: the peak
14}

nums =10211233546546

State

—

mid

—

nums[mid]

—

nums[mid+1]

active windowmidmid + 1 (right neighbour)peak found

slowfast

TYPESCRIPT The solution, annotated

findPeakElement.ts
function findPeakElement(nums: number[]): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < nums[mid + 1]) {
      lo = mid + 1;   // uphill to the right -> a peak lies right
    } else {
      hi = mid;       // downhill (or equal) -> a peak is mid or left
    }
  }
  return lo;   // lo === hi: the peak
}

Reading it block by block

Lines 2–3 — bounds over the whole array. lo and himark the window that is guaranteed to contain a peak. Initially that's the entire array, because the -∞ sentinels at both ends force at least one peak inside.

Line 5 — loop while the window has 2+ cells. The condition is strict lo < hi: we shrink the window until a single cell remains rather than testing for an exact match. When lo === hi we are done.

Line 6 — overflow-safe midpoint. Since lo < hi, mid is strictly less than hi, so mid + 1 is always a valid index — the comparison on the next line can never read out of bounds.

Lines 7–8 — rising slope. If nums[mid] < nums[mid + 1] the values climb to the right; a peak must be in [mid + 1, hi]. We can drop mid because its right neighbour is larger, so set lo = mid + 1.

Lines 9–10 — falling (or flat) slope. Otherwise mid is greater than its right neighbour, so mid itself is a candidate peak. Set hi = mid — crucially not mid - 1, which could throw away the only peak.

Line 12 — the window collapsed. The loop exits with lo === hi, and by the invariant that cell is a peak. Return lo (equivalently hi).

Complexity → O(log n) time — each iteration discards half the window. O(1) extra space — only two integer pointers, no recursion or auxiliary structure.

INTERVIEWFollow-ups they'll ask

"Why does this work if the array isn't sorted?" Binary search only needs a rule that points at a half guaranteed to hold the answer. The slope comparison plus the -∞ sentinels provide exactly that.
"Why hi = mid and not mid - 1?" In the falling case mid may itself be the peak; excluding it can discard the only answer and break correctness.
"What if adjacent elements can be equal?" The classic statement forbids it. Allowing equals breaks the slope guarantee, and worst case you may need an O(n) scan (no monotone decision survives a plateau).
"Find all peaks?" That requires a full O(n) scan — binary search can only pinpoint one peak, since it discards halves that may also contain peaks.
"Related problem?" Peak Index in a Mountain Array (LC 852) is the same template on a guaranteed single-peak (mountain) array.

OPTIMAL Binary Search

findPeakElement.ts
function findPeakElement(nums: number[]): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < nums[mid + 1]) {
      lo = mid + 1;   // uphill to the right -> a peak lies right
    } else {
      hi = mid;       // downhill (or equal) -> a peak is mid or left
    }
  }
  return lo;   // lo === hi: the peak
}

Complexity → O(log n) time — each iteration discards half the window. O(1) extra space — only two integer pointers, no recursion or auxiliary structure.

ALT 1 Linear scan — walk until it stops rising

O(n) time · O(1) space

Scan left to right and return the first index whose next element is smaller (or that is the last index) — the simplest correct idea, ignoring the O(log n) requirement.

approach-2.ts
function findPeakElement(nums: number[]): number {
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] > nums[i + 1]) return i;
  }
  return nums.length - 1;
}

Note → Correct because the first place the sequence stops rising is a peak, but it touches every element in the worst case (a strictly increasing array) → O(n). The binary search on the slope reaches a peak in O(log n) by discarding half the array each step.

MNEMONIC The one-liner

"Walk uphill: mid<mid+1 → go right (lo=mid+1), else keep mid (hi=mid); lo==hi is the peak."

TRIGGERS When you see _ → reach for _

"find a peak / local maximum"	binary search comparing mid vs mid+1
O(log n) required on unsorted data	binary search on a slope/predicate
mountain array peak	same uphill-slope template
"return any valid answer"	converge window to one cell, return lo

SKELETON The reusable shape

skeleton.ts
function findPeakElement(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < nums[mid + 1]) lo = mid + 1;
    else                            hi = mid;
  }
  return lo;
}

FLASHCARDS Tap to flip

What defines a peak here?

An element strictly greater than both neighbours, with nums[-1] = nums[n] = -∞ so a peak always exists.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

With nums = [1,2,1,3,5,6,4], which index can the algorithm return?

QUESTION 02

What is the required time complexity?

QUESTION 03

When nums[mid] < nums[mid + 1], what do you do?

QUESTION 04

In the falling case you set hi = mid. Why not hi = mid - 1?

QUESTION 05

Why is the loop condition lo < hi (strict) rather than lo <= hi?

QUESTION 06

How can binary search apply to an array that is not sorted?

QUESTION 07

Reading nums[mid + 1] never goes out of bounds. Why?

QUESTION 08

#162 · Find Peak ElementLocate any peak (a value greater than both neighbors) in O(log n) by binary searching on the slope: when nums[mid] < nums[mid+1] climb right, otherwise keep mid or go left — a peak always exists with -∞ sentinels at the ends.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Walk uphill — a rise must lead to a peak

RECIPE Binary search on the slope

COST Complexity & alternatives

Why binary search works without sorting

RUN IT Follow the rising slope until the window collapses

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Binary Search

ALT 1 Linear scan — walk until it stops rising

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _