162. Find Peak Element

Intitution

A peak is an element that is greater than its immediate neighbors. Because we can assume nums[-1] and nums[n] are -∞, the array is guaranteed to have at least one peak.

To find a peak in O(log n) time, we can use binary search:

• If nums[mid] is greater than both neighbors → it's a peak.

• If the right neighbor is greater → the peak lies to the right.

• Else → the peak lies to the left.

This works because in a unimodal-like structure, there's always a path toward a peak.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{N})$

Code

public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = (left + right) >> 1;

        // Check if nums[mid] is greater than its left and right neighbors
        boolean isGreaterThanLeft = (mid - 1 < 0 || nums[mid] > nums[mid - 1]);
        boolean isGreaterThanRight = (mid + 1 >= nums.length || nums[mid] > nums[mid + 1]);

        // If both conditions hold, we found a peak
        if (isGreaterThanLeft && isGreaterThanRight) {
            return mid;
        }

        // If increasing toward the right, move right
        if (!isGreaterThanRight) {
            left = mid + 1;
        } else { // Else move left
            right = mid - 1;
        }
    }

    // Should never reach here if input is valid
    return -1;
}