Skip to content

162. Find Peak Element

Description

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.

 

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

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

 

Constraints:

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

Solutions

We define the left boundary of binary search as \(left=0\) and the right boundary as \(right=n-1\), where \(n\) is the length of the array. In each step of binary search, we find the middle element \(mid\) of the current interval, and compare the values of \(mid\) and its right neighbor \(mid+1\):

  • If the value of \(mid\) is greater than the value of \(mid+1\), there exists a peak element on the left side, and we update the right boundary \(right\) to \(mid\).
  • Otherwise, there exists a peak element on the right side, and we update the left boundary \(left\) to \(mid+1\).
  • Finally, when the left boundary \(left\) is equal to the right boundary \(right\), we have found the peak element of the array.

The time complexity is \(O(\log n)\), where \(n\) is the length of the array \(nums\). Each step of binary search can reduce the search interval by half, so the time complexity is \(O(\log n)\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return left

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func findPeakElement(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := (left + right) >> 1
        if nums[mid] > nums[mid+1] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function findPeakElement(nums: number[]): number {
    let [left, right] = [0, nums.length - 1];
    while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Comments