Find Peak Element Solutions & Complexity

1. Define the problem

Find Peak Element

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 of any of them. 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. Compare nums_mid to its right neighbor: an uphill slope always leads toward a peak, so you can throw away the downhill half.

Constraints

1 ≤ nums.length ≤ 1000
-2³¹ ≤ nums_i ≤ 2³¹ - 1
nums_i != nums[i + 1] for all valid i

Example

Inputnums = [1, 2, 3, 1]

Output2

Explanation 3 is a peak element because 3 > 2 and 3 > 1, and its index is 2.

2. Visualize the solution

Follow the uphill slope until it turns downhill

Statusinit

low=0, high=3, mid=1 (value 2). nums[1]=2 < nums[2]=3 — still climbing, search right.

What happens in this step

low=0, high=3
mid = 0 + floor((3-0)/2) = 1

nums[1]=2 vs nums[2]=3: 2 is not greater than 3, so the slope is still climbing — the peak lies to the right. low becomes 2.

Step 1 of 3

Steps to visualize

The row is the whole array; the box marks the part that still might hold a peak.
Start low at 0 and high at the last index.
Compare nums_mid to nums[mid + 1].
If nums_mid is bigger, a peak lies at mid or somewhere to its left, so high = mid.
If nums_mid is smaller, the slope is still climbing, so the peak lies to the right — low = mid + 1.
When low === high, that index is a peak.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Follow the uphill slope until it turns downhill

Statusinit

low=0, high=3, mid=1 (value 2). nums[1]=2 < nums[2]=3 — still climbing, search right.

What happens in this step

low=0, high=3
mid = 0 + floor((3-0)/2) = 1

nums[1]=2 vs nums[2]=3: 2 is not greater than 3, so the slope is still climbing — the peak lies to the right. low becomes 2.

Step 1 of 3

4. Solution

Solution

solution.tsTypeScript

function findPeakElement(nums) {
  let low = 0;
  let high = nums.length - 1;

  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);

    if (nums[mid] > nums[mid + 1]) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return low;
}

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

5. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 2, 3, 1]`	`2`	example from the docstring, single clear peak
`nums = [1, 2, 1, 3, 5, 6, 4]`	`5`	array with more than one valid peak
`nums = [1]`	`0`	smallest valid input, one element is trivially a peak
`nums = [1, 2]`	`1`	two elements, peak at the boundary on the right
`nums = [2, 1]`	`0`	two elements, peak at the boundary on the left
`nums = [1, 2, 3, 4, 5]`	`4`	strictly increasing array, peak is the last element
`nums = [5, 4, 3, 2, 1]`	`0`	strictly decreasing array, peak is the first element

Find Peak Element