Find Peak Element — Binary Search on Slope [LC 162, Google, Amazon]

Problem Statement#

LeetCode 162 — Find Peak Element · Difficulty: Medium

A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element and return its index. If the array contains multiple peaks, return the index of any peak.

You may imagine that nums[-1] = nums[n] = -∞. You must write an algorithm that runs 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

Example 1:

Input:  nums = [1, 2, 3, 1]
Output: 2
Explanation: nums[2] = 3 is a peak: 3 > 2 and 3 > 1.

Example 2:

Input:  nums = [1, 2, 1, 3, 5, 6, 4]
Output: 5
Explanation: nums[5] = 6 is a peak (or index 1 is also valid).

Example 3:

Input:  nums = [1]
Output: 0
Explanation: Single element is trivially a peak (no neighbors).

Why This Problem Matters#

LC 162 is a favourite at Google and Amazon because it forces candidates to apply binary search to a problem that does not look like a sorted-array search. The array is not sorted. There is no specific target. Yet O(log n) is achievable — and required. That leap of intuition distinguishes engineers who merely memorise templates from those who understand the deeper principle.

The deeper principle is this: binary search works whenever you can make a definitive, binary decision at each midpoint that shrinks the search space by half. You do not need a globally sorted array. You need a local comparison that tells you which direction to move. For peak finding, that comparison is the slope between nums[mid] and nums[mid+1].

This pattern appears extensively in practice: finding the point where a function crosses a threshold, finding the local maximum of a unimodal function, and locating the boundary between two behavioural regimes in a system. Google's "Magical Candy Bags" problem is a disguised version. Meta's "Minimum Cost Climbing Stairs" planning variant is another.

In interviews, candidates who describe the invariant — "a peak must exist in the current window" — score significantly higher than those who just code the loop without justification.

The Core Insight#

The problem guarantees nums[-1] = nums[n] = -∞. This means:

• If you are at the leftmost element and it is greater than its right neighbor, it is a peak.
• If you are at the rightmost element and it is greater than its left neighbor, it is a peak.
• At any interior point, if neither neighbor is larger, you have a peak.

Now consider any midpoint mid:

• If nums[mid] < nums[mid + 1], the slope is uphill going right. Because the array must eventually come back down (since nums[n] = -∞), there is guaranteed to be a peak somewhere to the right of mid. We can safely discard mid and everything to its left.
• Otherwise (nums[mid] >= nums[mid + 1]), the slope is downhill or flat going right. Because nums[-1] = -∞, there must be a peak somewhere to the left of or at mid. We keep mid in the search space: set hi = mid.

The invariant is: at every iteration, a peak element exists within [lo, hi]. When lo == hi, the single remaining element is that peak.

Since adjacent elements are guaranteed distinct (nums[i] != nums[i+1]), there is no ambiguous flat region — every comparison is a clean uphill or downhill decision.

Visual Dry Run#

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

nums[5] = 6. Correct peak.

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

nums[2] = 3. Correct peak.

Common Mistakes#

1. Using while lo <= hi with hi = mid - 1. The exact-match template does not work here. Because we need to keep mid in the search space when the slope goes left (hi = mid), you must use while lo < hi. With lo <= hi and hi = mid - 1, you can miss the peak element itself.

2. Accessing nums[mid + 1] without checking bounds. When hi = len(nums) - 1 and mid = hi, accessing mid + 1 causes an index-out-of-bounds error. The while lo < hi loop prevents mid == hi (because mid = (lo + hi) // 2 < hi when lo < hi), so the access is always safe. Forgetting this guard and adding manual bounds checks is a sign of misunderstanding the template.

3. Comparing nums[mid] with both neighbors to check for a peak inside the loop. This is unnecessary. The single slope comparison nums[mid] < nums[mid+1] is sufficient. Adding extra comparisons with nums[mid-1] clutters the logic and risks off-by-one errors near the boundaries.

4. Returning mid immediately when the peak condition is met inside the loop. While this can work, the cleaner and safer approach is to let the loop converge to lo == hi and return lo. Early returns require additional boundary checks and are harder to verify correct under pressure.

5. Assuming the array must be unimodal (single peak). The problem allows multiple peaks. The algorithm works regardless — it finds one peak, which is all that is required. If you assume unimodality and hard-code logic for a single hill shape, you will fail on multi-peak inputs.

6. Confusing the direction of the move. When nums[mid] < nums[mid+1] (uphill right), move lo right. When nums[mid] >= nums[mid+1] (downhill right), move hi left (to mid, not mid-1). Getting this backwards causes the algorithm to chase valleys instead of peaks.

Solutions#

Python#

def findPeakElement(nums: list[int]) -> int:
    lo, hi = 0, len(nums) - 1       # search window [lo, hi]; a peak always exists here
 
    while lo < hi:                   # loop until exactly one candidate remains
        mid = lo + (hi - lo) // 2   # safe midpoint; always < hi so mid+1 is valid
 
        if nums[mid] < nums[mid + 1]:
            # slope is uphill going right: a peak must exist in [mid+1, hi]
            lo = mid + 1
        else:
            # slope is downhill (or equal) going right: a peak exists in [lo, mid]
            # keep mid in the window — it could be the peak
            hi = mid
 
    # lo == hi: the single remaining element is a peak
    return lo

JavaScript#

function findPeakElement(nums) {
    let lo = 0;
    let hi = nums.length - 1;        // inclusive search window; peak guaranteed here
 
    while (lo < hi) {                // converge until one element remains
        const mid = lo + Math.floor((hi - lo) / 2); // safe midpoint; mid < hi always
 
        if (nums[mid] < nums[mid + 1]) {
            // uphill to the right: peak must be in right half [mid+1, hi]
            lo = mid + 1;
        } else {
            // downhill or flat to the right: peak is in left half [lo, mid]
            // do NOT exclude mid — it may be the peak
            hi = mid;
        }
    }
 
    // lo === hi: converged to the peak index
    return lo;
}

Complexity Analysis#

The binary search halves the window at every step: the lo < hi loop runs at most ceil(log₂(n)) iterations. For n = 1000 that is at most 10 iterations. Space is O(1) — only lo, hi, and mid are used.

The linear scan is conceptually simpler but fails the problem's O(log n) requirement.

Follow-up Questions#

Q: Can there be a peak at index 0 or n-1? Yes. Index 0 is a peak if nums[0] > nums[1] (it has no left neighbor, and nums[-1] = -∞). The algorithm handles this correctly without special-casing.

Q: What if the entire array is strictly increasing? Then nums[mid] < nums[mid+1] is always true, and lo keeps moving right until lo == hi == n-1, which is correctly a peak (its only neighbor is to the left, which is smaller).

Q: What if the entire array is strictly decreasing? Then nums[mid] >= nums[mid+1] is always true, and hi keeps shrinking until lo == hi == 0, correctly identified as a peak.

Q: How do you find ALL peaks? Binary search finds one peak in O(log n). Finding all peaks requires a full linear scan O(n) — you cannot do better because any element could be a local peak.

Q: What is the recursive version? Replace the while loop with a recursive call on [mid+1, hi] or [lo, mid]. Space becomes O(log n) due to the call stack.

This Pattern Solves#

• LC 162 — Find Peak Element (this problem)
• LC 852 — Peak Index in a Mountain Array (unimodal version)
• LC 1095 — Find in Mountain Array (binary search on peak + two searches)
• LC 1901 — Find a Peak Element II (2D extension — same slope logic applied per row)
• Any problem asking for a local maximum in an unsorted array where adjacent elements are distinct

Key Takeaway#

Peak finding with binary search works because of the slope invariant: if you are on an uphill slope, a peak must lie ahead; if you are on a downhill slope, a peak lies behind or at your current position. The while lo < hi template with hi = mid (not mid - 1) is essential — it keeps the peak candidate in the window. The loop terminates when exactly one element remains, and that element is guaranteed to be a peak. This slope-chasing technique extends naturally to 2D peak finding and mountain array problems.

Key Takeaways#

• LC 162 (Find Peak Element) is asked by Google and Microsoft because it forces candidates to use binary search on an unsorted array by reasoning about local slope rather than global order.
• The slope invariant: if nums[mid] < nums[mid + 1], a peak must exist to the right; otherwise a peak exists at or to the left of mid.
• Use while lo < hi with hi = mid — never hi = mid - 1 — because mid itself might be the peak.
• Peaks at the boundaries (index 0 or n-1) are valid and handled correctly without special cases due to the virtual -infinity boundary assumption.
• A strictly increasing array's peak is at the last index; a strictly decreasing array's peak is at index 0 — both are handled without special code.
• This same slope-chasing technique solves LC 852 (Peak Index in Mountain Array) and LC 1901 (Find Peak Element II in 2D).
• The problem guarantees nums[i] != nums[i+1], making the slope comparison unambiguous — without this, binary search would not work here.