How to Find a Peak Element in O(log n) Time – LeetCode 162 Solution

Problem Description

LeetCode problem 162 asks to find a peak element in an integer array where a peak is an element strictly greater than its neighbors. The array is considered to have -∞ at positions -1 and n, and adjacent elements are guaranteed to be unequal.

Linear Scan Solution

A straightforward O(n) approach scans the array and returns the index of any element that satisfies the peak condition.

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            boolean ok = true;
            if (i - 1 >= 0) {
                if (nums[i - 1] >= nums[i]) ok = false;
            }
            if (i + 1 < n) {
                if (nums[i + 1] >= nums[i]) ok = false;
            }
            if (ok) return i;
        }
        return -1;
    }
}

Time complexity: O(n). Space complexity: O(1).

Binary Search Solution

Because the problem hints at a logarithmic solution, we can apply binary search based on the monotonic property: if nums[mid] > nums[mid+1], the peak lies on the left side (including mid); otherwise it lies on the right side.

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

Time complexity: O(log n). Space complexity: O(1).

Proof of Existence

For any non‑empty array with the given boundary conditions, a peak always exists. If the array length is 1, that element is trivially a peak. For longer arrays, consider the leftmost element; if it is greater than its right neighbor, it is a peak. Otherwise, moving right, the sequence must eventually decrease, and the point where it switches from increasing to decreasing is a peak.

Proof that Binary Search Does Not Miss the Peak

The binary search maintains an interval that is guaranteed to contain at least one peak. At each step, comparing nums[mid] with its right neighbor determines which half must contain a peak, ensuring the algorithm converges to a valid peak index.

If you do not understand why the proof of existence leads to the correctness of the binary‑search approach, focus on the step where the interval is reduced based on the comparison.