LeetCode 0162. Find Peak Element Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

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

Solution 1: Binary Search

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).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)