šŸ”— LeetCodešŸ”— Neetcode

Find Peak Element

Mediumbinary searchGoogleMetaMicrosoft

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 to any of the peaks.


You may imagine that nums[-1] = nums[n] = -āˆž. 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.

Examples

Input:nums = [1,2,3,1]
Output:2
Explanation:3 is a peak element and your function should return the index number 2.
Input:nums = [1,2,1,3,5,6,4]
Output:5
Explanation:Your function can return either index 1 (peak 2) or index 5 (peak 6).

Constraints

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

šŸ’” Hints

Hint 1

If nums[mid] < nums[mid + 1], there must be a peak to the right.

Hint 2

If nums[mid] > nums[mid + 1], there's a peak to the left (including mid).

Hint 3

This is because the edges are -āˆž, so a peak is guaranteed to exist on the ascending side.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Logarithmic
Algorithmic Approach

Binary search: if nums[mid] < nums[mid+1], a peak must exist on the right (ascending). Otherwise, a peak must exist on the left (including mid). Converge to the peak.

Time ComplexityO(log n)
Why:

Binary search follows the upward slope by comparing nums[mid] to nums[mid + 1], halving the interval each step.

Space ComplexityO(1)
Why:

Iterative binary search runs in-place using O(1) index pointers.

Big-O Growth CurveExcellent (O(log N))
Execution time grows slowly by repeatedly halving the search space.

šŸŒ Real-World Use Cases

Signal ProcessingPeak detection

Finding local maxima in signal data (audio waveforms, stock prices) efficiently using binary search on gradient direction.

šŸ” Dry Run

Solutionā± O(log n) | šŸ’¾ O(1)
Line2
left=0number
right=3number

Find peak in [1,2,3,1]. Initialize left=0, right=3.