Find Peak Element medium

Problem Statement

A peak element is an element that is strictly greater than its neighbors.

Given an 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] = -∞.

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: Both 3 and 6 are peak elements, but your function should return the index number 5.

Steps

1. Binary Search Approach: We can efficiently solve this problem using binary search. The core idea is that if nums[mid] < nums[mid + 1], then a peak must exist in the right half (because the array slopes upward at mid). Conversely, if nums[mid] < nums[mid - 1], a peak must exist in the left half.

2. Base Cases: If nums[mid] is greater than both its neighbors (or it's at the edge of the array), it's a peak.

3. Iterative Refinement: We repeatedly narrow down the search space until we find a peak.

Explanation

The algorithm leverages the property that at least one peak must exist in the array. The binary search efficiently finds one such peak by iteratively comparing the middle element with its neighbors. The condition nums[mid] < nums[mid + 1] implies that the peak lies to the right, and nums[mid] < nums[mid - 1] indicates the peak is to the left. Otherwise, nums[mid] itself is a peak. This approach guarantees logarithmic time complexity.

Code

function findPeakElement(nums: number[]): number {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] < nums[mid + 1]) {
            // Peak is in the right half
            left = mid + 1;
        } else {
            // Peak is in the left half (including mid)
            right = mid;
        }
    }

    return left; // left and right converge at the peak index
};

Complexity

• Time Complexity: O(log n) due to the binary search.
• Space Complexity: O(1) as we use only a constant amount of extra space.