Find Peak Element

Medium

Problem

A peak is an element strictly greater than its neighbours. Imagine nums[−1] = nums[n] = −∞, and no two adjacent elements are equal. Return the index of any peak, in O(log n) time.

Example 1

Input:  [1, 2, 3, 1]
Output: 2

Example 2

Input:  [1, 2, 1, 3, 5, 6, 4]
Output: 1 or 5

Test cases

Case 1

Input:    [1,2,3,1]
Expected (any of): [2]

Case 2

Input:    [1,2,1,3,5,6,4]
Expected (any of): [1,5]

Case 3

Input:    [1]
Expected (any of): [0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Binary search on the slope

Time O(log n)Space O(1)

If nums[mid] < nums[mid + 1] a peak lies to the right (the sequence must come down eventually); otherwise one lies at mid or to the left.

function findPeakElement(nums) {
let lo = 0, 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;
}