Find Peak Element

Medium Problem 43 of 151 Java and Python

Problem

A peak element is strictly greater than its neighbours. Given an integer array nums where nums[i] != nums[i + 1], return the index of any peak.

Imagine nums[-1] and nums[n] are -∞, so the ends can be peaks. The algorithm must run in O(log n) time.

Example 1

Input: nums = [1, 2, 3, 1]
Output: 2
Why: 3 is a peak.

Example 2

Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 1 or 5
Why: Both 2 (index 1) and 6 (index 5) are peaks.

Constraints

1 ≤ nums.length ≤ 1000
nums[i] != nums[i + 1]

Explanation

If nums[mid] < nums[mid + 1], you are on an upward slope. Keep walking right and the values must eventually drop (the edge is -∞), so a peak exists on the right.

Otherwise the slope goes down from mid, so a peak is at mid or to its left. Either way you keep a half that surely contains a peak, even though the array is not sorted.

Approach 1 · Naive

Linear scan for a drop

Time O(n)
Space O(1)

The first index where the next value is smaller is a peak (or the last index if it never drops).

For i from 0 to n – 2, return i if nums[i] > nums[i + 1].
Return n - 1.

Java

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

Python

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return i
        return len(nums) - 1

Approach 2 · Optimal

Binary search on the slope

Time O(log n)
Space O(1)

Compare nums[mid] with nums[mid + 1] and move towards the larger one.

Set lo = 0, hi = n - 1.
While lo < hi: if nums[mid] < nums[mid + 1], lo = mid + 1; else hi = mid.
Return lo.

Java

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

Python

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < nums[mid + 1]:
                lo = mid + 1
            else:
                hi = mid
        return lo

Complexity compared

Approach	Time	Space
Naive Linear scan for a drop	O(n)	O(1)
Optimal Binary search on the slope	O(log n)	O(1)

Key takeaways

Binary search needs a rule that tells you which half to keep, not a sorted array.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem