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 has a time complexity of O(log n).

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: 6 is a peak element and your function should return the index number 5.

Steps

The problem can be solved efficiently using binary search. The core idea is:

1. Base Cases: If the array has only one element, that element is the peak.
2. Binary Search: Start with the middle element.
   • If the middle element is greater than its right neighbor, the peak must lie in the left half (including the middle element).
   • If the middle element is less than its right neighbor, the peak must lie in the right half.
3. Recursively search: Repeat the process on the chosen half until a peak is found.

Explanation

The algorithm leverages the fact that a peak must exist. If an element is not a peak, it's guaranteed that a peak will exist on either its left or right side. By comparing the middle element with its neighbor, we can confidently eliminate half of the search space in each step, thus achieving logarithmic time complexity. The -∞ assumption simplifies the edge cases, as the first and last elements are automatically considered potentially peak elements if they are greater than their single neighbour.

Code

public class Solution {
    public int FindPeakElement(int[] nums) {
        int left = 0;
        int right = nums.Length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2; // Avoid potential overflow

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

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

Complexity

• Time Complexity: O(log n) - Due to the binary search approach.
• Space Complexity: O(1) - Constant extra space is used. The algorithm operates in-place.