#114

Find Peak Element

medium

arraybinary-search

A peak element is one 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 of any of them.

You may imagine that nums[-1] = nums[n] = -∞ — that is, an out-of-bounds neighbor is treated as smaller than everything, so the first or last element only needs to beat its single real neighbor. Adjacent elements are always different. Your algorithm must run in O(log n) time.

Example

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

Output: 2

nums[2] = 3 is greater than both neighbors.

Constraints

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

Intuition

The direct approach scans for any element strictly greater than both of its neighbors, treating the out-of-bounds neighbors as -∞, and returns its index.

function findPeakElement(nums) {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    // Out-of-bounds neighbors count as -Infinity, so the ends only beat their one real neighbor.
    const left = i === 0 ? -Infinity : nums[i - 1];
    const right = i === n - 1 ? -Infinity : nums[i + 1];
    if (nums[i] > left && nums[i] > right) return i; // a peak
  }
  return -1; // unreachable: a peak always exists
}

Brute force — scan for an element bigger than both neighbors: O(n).

This is O(n), but the prompt demands O(log n) — and the array isn't sorted, so what is there to halve? Can we do better?

The key observation: follow the rising slope and you can't miss a peak. Look at mid and its right neighbor. If nums[mid] < nums[mid + 1], the values are climbing rightward — since the far-right edge drops off to -∞, some peak must lie to the right, so move lo = mid + 1. Otherwise the slope falls (or mid is itself a peak), and a peak lies at mid or to its left, so hi = mid. This is the half-open boundary search shape, applied to a monotonic predicate ("is the slope still rising?") rather than to sorted values.

When lo === hi the range is a single index, and the inward-sloping boundaries guarantee it's a peak.

Walking it through:

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

lo↓

mid↓

hi↓

nums[3]=3 < nums[4]=5 → slope rising → lo = 4

mid = 3. The value to the right is larger, so we're on a rising slope — a peak lies to the right.

lo↓

mid↓

hi↓

nums[5]=6 > nums[6]=4 → slope falling → hi = 5

Now [4, 6], mid = 5. The value to the right is smaller — the slope falls, so a peak is at 5 or left of it.

lo↓mid↓

hi↓

nums[4]=5 < nums[5]=6 → slope rising → lo = 5

mid = 4 (value 5) is below its right neighbor — still rising, so move past it.

lo↓hi↓

lo === hi → return 5

The range collapses to index 5 (value 6), which beats both neighbors — a peak. (Index 1 is also a peak; either is accepted.)

Optimization

Binary search toward the rising side

Compare nums[mid] to its right neighbor nums[mid + 1]. If nums[mid] < nums[mid + 1] the slope rises to the right, so a peak must exist somewhere on the right — move lo past mid. Otherwise the slope falls (or mid is itself a peak), so a peak exists at mid or to its left — pull hi down to mid. Because out-of-bounds neighbors count as -∞, the boundary always slopes inward, guaranteeing the search converges on a real peak.

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

function findPeakElement(nums) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < nums[mid + 1]) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Complexity analysis

Time complexity: O(log n). Here's why:

Each step compares nums[mid] to its right neighbor and discards the half that can't slope up to a peak.
The comparison is O(1), so the range halves every iteration.

So the search runs about log₂ n times — overall O(log n), versus O(n) for a linear peak scan.

Space complexity: O(1). Here's why:

Only the lo/hi bounds are kept; nothing scales with the input.

The returned index is a single number — overall O(1).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = [42]	0	Single element — trivially a peak (no real neighbors).
nums = [10,9,8,7]	0	Strictly decreasing — the first element is the only peak.
nums = [1,2,3,4]	3	Strictly increasing — the last element is the peak the search lands on.
nums = [2,4,1]	1	Single interior peak at index 1.
nums = [2,1,3]	2	Two peaks (indices 0 and 2); the search returns 2. Any valid peak is accepted by the checker.
nums = [4,5,2,1]	1	Peak at index 1, then a downhill run.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor