162. Find Peak Element

Description

The problem is to find a peak element in an array. A peak element is an element that is greater than its neighbors. For an array nums, an element nums[i] is a peak if:

• nums[i] > nums[i - 1] (for i > 0) and
• nums[i] > nums[i + 1] (for i < nums.length - 1)

The goal is to return the index of any peak element.

Intuition

To efficiently find a peak element, we can use a modified binary search. This approach exploits the fact that if the middle element of a subarray is not a peak, then at least one of its neighbors must be greater. Therefore, we can move our search to the half of the array where the neighbor is greater.

Approach

1. Initialize Pointers: - Set two pointers: l (left) to 0 and r (right) to nums.length - 1.
2. Binary Search: - While l is less than r, calculate the middle index mid of the current subarray. - Compare nums[mid] with its right neighbor nums[mid + 1]. - If nums[mid + 1] > nums[mid], then the peak must be in the right half of the array, so update l to mid + 1. - Otherwise, the peak is in the left half or at mid, so update r to mid.
3. Return Peak: - When l equals r, return l (or r), which will be the index of the peak element.

Complexity

Time Complexity:

O(log n), where n is the number of elements in the array. This is due to the binary search approach, which halves the search space with each iteration.

Space Complexity:

O(1), as the algorithm uses a constant amount of extra space for pointers and variables.

Code

C++

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

Python

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

Java

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

JavaScript

var findPeakElement = function (nums) 
{
 let l = 0;
    let r = nums.length - 1;
    while (l < r) {
        const mid = Math.floor((l + r) / 2);
        if (nums[mid + 1] > nums[mid]) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
};