Find Peak Element

Master this topic with zero to advance depth.

Find Peak Element

A peak element is an element that is strictly greater than its neighbors. Given an 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] = -\\infty. You must write an algorithm that runs in $O(\\log N)$ time.

Medium

Examples

Input: nums = [1,2,3,1]
Output: 2
3 is a peak element and its index is 2.

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Your function can return either index 1 where the peak element is 2, or index 5 where the peak element is 6.

Approach 1

Level I: Brute Force (Linear Scan)

Intuition

Since any element that is greater than its next neighbor is a potential peak (because we know the previous element was smaller, or it's the first element), we can just scan linearly.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [1,2,3,1]

0: 1 < 2
1: 2 < 3
2: 3 > 1. Return 2.

java

class Solution {
    public int findPeakElement(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) return i;
        }
        return nums.length - 1;
    }
}

Approach 2

Level II: Recursive Binary Search

Intuition

Divide the array and check the middle element's slope. If we are going up, a peak must exist on the right. If we are going down, a peak must exist on the left.

⏱ $O(\log N)$💾 $O(\log N)$ due to recursion stack.

Detailed Dry Run

nums = [1,2,3,1]. L=0, R=3.

mid=1. nums[1]=2 < nums[2]=3. Search [2, 3].
mid=2. nums[2]=3 > nums[3]=1. Search [2, 2].
L=R=2. Return 2.

java

class Solution {
    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }
    private int search(int[] nums, int l, int r) {
        if (l == r) return l;
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[mid + 1]) return search(nums, l, mid);
        return search(nums, mid + 1, r);
    }
}

Approach 3

Level III: Optimal (Binary Search on Slope)

Intuition

We can use binary search by looking at the slope. If nums[mid] < nums[mid+1], it means we are on a rising slope, and a peak must exist to the right. If nums[mid] > nums[mid+1], we are on a falling slope, and a peak must exist to the left (including mid).

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	nums[Mid+1]	Decision
1	0	6	3	3	5	3 < 5 → L = 4
2	4	6	5	6	4	6 > 4 → R = 5
3	4	5	4	5	6	5 < 6 → L = 5
Exit	5	5	-	-	-	Return L = 5

java

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < nums[mid + 1]) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

← Previous QuestionFind First and Last Position of Element in Sorted Array

Next Question →Find Minimum in Rotated Sorted Array

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.