Find Peak Element

LeetCode #162 [Medium]

Problem Statement

A peak element in an array is an element that is strictly greater than its neighbors. Given an integer array nums, find any peak element and return its index. You may assume nums[-1] = nums[n] = -∞.

Example: nums = [1,2,3,1] → Output: 2 (nums[2] = 3 is a peak)

Approach 1: Linear Scan

Explanation: Traverse array and return first element greater than neighbors.

Time Complexity: O(n)

Space Complexity: O(1)

for i in 0..n-1:
    if (i==0 or nums[i] > nums[i-1]) and (i==n-1 or nums[i] > nums[i+1]):
        return i

💡 Think: Check neighbors and return an index that is larger than both sides.

Approach 2: Binary Search

Explanation: Compare middle element with neighbors; move to side with higher neighbor.

Time Complexity: O(log n)

Space Complexity: O(1)

low = 0
high = n-1
while low < high:
    mid = (low+high)//2
    if nums[mid] < nums[mid+1]:
        low = mid + 1
    else:
        high = mid
return low

💡 Think: Move toward the uphill side; a peak must exist in that direction.

Approach 3: Recursive Binary Search

Explanation: Recursively check mid and its neighbor to find peak.

Time Complexity: O(log n)

Space Complexity: O(log n) recursion stack

function findPeak(nums, low, high):
    if low == high:
        return low
    mid = (low+high)//2
    if nums[mid] < nums[mid+1]:
        return findPeak(nums, mid+1, high)
    else:
        return findPeak(nums, low, mid)

💡 Think: Recurse into the half with a rising slope until left equals right.

Solve on LeetCode