{x}
blog image

Find Peak Element

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.

Solution Explanation: Find Peak Element

This problem asks to find a peak element in a given array. A peak element is an element that is strictly greater than its neighbors. The solution leverages binary search for an efficient O(log n) time complexity.

Approach:

The core idea is that a peak element must exist. We can use binary search to efficiently locate one. In each iteration of the binary search:

  1. Find the middle element: Calculate the middle index mid = (left + right) // 2.
  2. Compare with the right neighbor: Compare nums[mid] with nums[mid + 1].
    • If nums[mid] > nums[mid + 1]: This means there's a potential peak to the left of mid, so we update the search space by setting right = mid.
    • If nums[mid] < nums[mid + 1]: This suggests a potential peak to the right of mid, so we update left = mid + 1.
  3. Repeat: Continue this process until left and right converge to a single index, which will be the index of a peak element.

Time and Space Complexity:

  • Time Complexity: O(log n) due to the binary search. The search space is halved in each iteration.
  • Space Complexity: O(1). The algorithm uses only a few variables to track the indices, requiring constant extra space.

Code Implementation (Python):

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[mid + 1]:
                right = mid  # Potential peak on the left
            else:
                left = mid + 1 # Potential peak on the right
        return left # left and right converge to the peak index

Code Implementation (Java):

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

Code Implementation (C++):

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2; // Avoid potential overflow
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

Code Implementation (Go):

func findPeakElement(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := (left + right) / 2
		if nums[mid] > nums[mid+1] {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

Code Implementation (TypeScript):

function findPeakElement(nums: number[]): number {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

All these implementations follow the same binary search algorithm, ensuring an efficient solution to the problem. The choice of language affects only syntactic details, not the core logic or complexity.