Find Peak Element — Binary Search on Slope O(log n) [LC 162]

Problem Statement#

Find a peak element where nums[i] > nums[i-1] and nums[i] > nums[i+1]. Assume nums[-1] = nums[n] = -infinity. No two adjacent elements are equal. Return any peak index. Must run in O(log n) time.

Constraints:

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• nums[i] != nums[i+1] for all valid i

Input:  nums = [1,2,3,1]
Output: 2

Input:  nums = [1,2,1,3,5,6,4]
Output: 5

Why This Problem Matters#

LeetCode 162 is a classic Google and Meta binary search question. The O(log n) requirement rules out linear scan and forces you to think about what invariant can be maintained across halves. This is tricky because the array is not sorted — traditional binary search intuition doesn't apply directly.

The insight — "if the slope is going up at mid, a peak must exist to the right" — is a non-obvious application of binary search that appears in Search in Mountain Array (LC 1095) and Peak Index in a Mountain Array (LC 852). Learning the slope-direction binary search here unlocks those harder problems.

The Core Insight#

The slope argument: The problem guarantees virtual -infinity at both ends. This means every finite array must have at least one peak — it cannot be monotonically increasing or decreasing throughout.

At any mid:

• If nums[mid] < nums[mid+1]: slope is ascending right. A peak exists in [mid+1, right] — ascending slope must eventually turn descending, creating a peak.
• If nums[mid] > nums[mid+1]: slope is descending right. A peak exists in [left, mid] — either mid itself is a peak, or there's one to its left.

This invariant allows standard binary search: always narrow to the half that is guaranteed to contain a peak.

Visual Dry Run#

nums = [1, 2, 1, 3, 5, 6, 4]

nums[5] = 6 > nums[4] = 5 and nums[5] = 6 > nums[6] = 4 — valid peak.

Solution (Optimal)#

class Solution:
    def findPeakElement(self, nums):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1   # peak is in right half
            else:
                right = mid      # peak is at mid or in left half
        return left

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

Time: O(log n) — binary search halves the search space each iteration Space: O(1) — two pointer variables only

Common Mistakes#

• Linear scan O(n) — the problem explicitly requires O(log n)
• Checking nums[mid] > nums[mid-1] as the split condition — causes index-out-of-bounds when mid=0
• Setting right = mid - 1 when nums[mid] > nums[mid+1] — incorrectly eliminates mid which could be the peak
• Not understanding why the invariant holds — virtual -infinity at boundaries is what guarantees a peak exists in whichever half you select
• Assuming the array must be unimodal (single peak) — the problem allows multiple peaks; binary search finds any valid one

Interview Tips#

• Explain the virtual -infinity boundary: "by the boundary conditions, the array must have at least one peak"
• State the slope argument clearly before coding: "ascending slope at mid means peak is to the right"
• Use right = mid (not mid - 1) when going left — mid could be the answer
• Contrast with standard binary search on sorted arrays: "we don't need sorted order; we need slope direction"
• Mention related problems: Peak Index in Mountain Array (LC 852), Search in Mountain Array (LC 1095)

Follow-up Questions#

• What if you need to find all peaks, not just one? (Linear scan O(n) — binary search only guarantees one)
• What if adjacent elements can be equal? (The slope argument breaks down — cannot determine which half contains a peak)
• How does this generalize to 2D peak finding? (LC 1901 — binary search on columns, linear scan on rows)
• What if the array is guaranteed to have exactly one peak (unimodal)? (Same binary search applies; the result is unique)
• How would you prove the invariant formally? (If slope goes up at mid but no peak exists to the right, the entire right side must monotonically increase to +infinity — contradicting the virtual -infinity boundary)

Key Takeaways#

• LeetCode 162 is asked at Google, Meta, and Amazon — binary search applied to an unsorted array via slope direction
• Virtual -infinity at both ends guarantees at least one peak exists in any finite array
• If nums[mid] < nums[mid+1], a peak must exist in [mid+1, right]; otherwise in [left, mid]
• Use right = mid (not mid - 1) when going left — mid itself could be the peak
• Time O(log n), Space O(1) — the standard binary search template applied to slope direction instead of value comparison
• No two adjacent elements are equal (given by constraints) — this is what makes slope direction unambiguous
• The slope-direction binary search pattern directly transfers to LC 852 and LC 1095