Generated by Codex with GPT-5

Quick facts

What the problem is really asking

This problem does not ask for the maximum value in the whole array.

It only asks for any index whose value is greater than its neighbors. That is a much weaker requirement, and that weaker requirement is exactly what makes the binary-search solution possible.

Two details matter:

  • a peak can appear at the edge of the array
  • the problem says values outside the array can be treated like negative infinity

So in [1, 2, 3, 1], index 2 is a peak because 3 is greater than both neighbors. In [1, 2, 3, 4], the last index is a peak because the array keeps going up and the right side is treated as -inf.

The practical interpretation is simple: the array always has somewhere it stops climbing, and that stopping point is a peak.

Two useful ways to think about it

The easiest correct idea is a linear scan.

Walk left to right and look for the first position where the slope turns from up to down. If nums[i] > nums[i + 1], then index i is already a peak. If that never happens, the array is strictly increasing, so the last index is the peak.

That solution is O(n) time and O(1) space. It is a perfectly good baseline.

The optimal solution is binary search.

Instead of checking every slope change, it checks the slope at the middle. If the middle is higher than the element to its right, then a peak must exist on the left half, including the middle. If the middle is lower than the element to its right, then a peak must exist on the right half. That lets the algorithm discard half of the search space each step and reach O(log n) time.

The key question is: when looking at mid, how can one know which half still contains a peak?

Compare nums[mid] and nums[mid + 1].

If nums[mid] > nums[mid + 1], the array is sloping downward at that boundary. That means there is definitely a peak somewhere in [left, mid].

Why? There are only two possibilities:

  1. mid is already a peak.
  2. mid is not a peak because something on its left is even larger, and if one keeps moving left through larger values, that climb must eventually stop at a peak.

If nums[mid] < nums[mid + 1], the array is sloping upward, so there must be a peak somewhere in [mid + 1, right] by the same logic.

That is the whole trick. The algorithm is not searching for a sorted target. It is searching for a guaranteed direction toward some local maximum.

Python solution

from __future__ import annotations

from typing import List, Sequence


class PeakElementFinder:
    """Find any peak index in an array."""

    def find_peak_index(self, values: Sequence[int]) -> int:
        """
        Return the index of any peak element.

        The LeetCode problem guarantees adjacent values are unequal, which makes
        the slope-based binary search valid.

        Time: O(log n)
        Space: O(1)
        """
        self._validate_input(values)

        left = 0
        right = len(values) - 1

        while left < right:
            middle = (left + right) // 2

            # A downward slope means a peak exists on the left side, including
            # middle. An upward slope means a peak exists on the right side.
            if values[middle] > values[middle + 1]:
                right = middle
            else:
                left = middle + 1

        return left

    def _validate_input(self, values: Sequence[int]) -> None:
        if not values:
            raise ValueError("values must contain at least one number.")


class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        """LeetCode entry point."""
        finder = PeakElementFinder()
        return finder.find_peak_index(nums)

Why this works

Each loop keeps the invariant that at least one peak exists inside the current search range.

When the code sees values[middle] > values[middle + 1], it keeps the left half because a descending step guarantees a peak on that side. When the code sees values[middle] < values[middle + 1], it keeps the right half because an ascending step guarantees a peak there.

The search range shrinks every iteration, so eventually left == right. At that point the range contains exactly one index, and the invariant says that index must be a peak.

This is why the algorithm is O(log n): each comparison throws away half of the remaining range. It also uses O(1) extra space because it only stores the current boundaries.

Interview follow-ups

What changes if adjacent duplicates are allowed?

The original problem guarantees nums[i] != nums[i + 1], which is what makes every comparison clearly slope left or slope right. If duplicates are allowed, that directional signal gets weaker because nums[mid] == nums[mid + 1] does not prove which half safely contains a strict peak.

The first thing to clarify is the definition. If a strict peak is still required, an array like [2, 2, 2] has no valid answer at all. If plateau tops are allowed, then the problem changes and the algorithm can be adapted, but the clean LeetCode proof no longer applies as-is.

In an interview, the safest answer is to call out that assumption explicitly. If duplicates are allowed and the interviewer still wants a robust solution without extra problem constraints, a linear scan is the simplest fully reliable approach. It runs in O(n) time with O(1) space and avoids the ambiguity that equal neighbors introduce.

What if the interviewer asks for all peak indices instead of any one peak?

Binary search is no longer the right tool because binary search works by discarding huge regions once it knows one peak still exists somewhere else. That is perfect when the task is to return any one peak, but it is exactly the wrong behavior when the task is to list every peak.

For all peak indices, the natural approach is a full scan. Check every position against its left and right neighbors, treating missing neighbors as -inf just like the original problem statement. Every qualifying index gets added to the result.

That solution runs in O(n) time and needs O(k) output space for k peaks. It is optimal in practice because every element may need to be reported, so the array cannot be meaningfully skipped the way it can in the original problem.

How does this idea extend to a 2D grid?

A common extension is 2D peak finding. The spirit stays the same: do not search for the single global maximum unless the problem requires it. Search for a direction that guarantees movement toward a peak.

One standard approach is to choose the middle column, find the row containing the maximum value in that column, and compare that cell to its left and right neighbors. If it is larger than both, that cell is a 2D peak. If the left neighbor is larger, recurse into the left half of the columns. If the right neighbor is larger, recurse into the right half.

This works because the maximum in the middle column is already the strongest candidate in that column, so a larger horizontal neighbor tells the search which side can still contain a better local summit. The complexity becomes O(rows * log cols) if the algorithm binary-searches over columns. That is much better than scanning the full grid, but the proof and implementation are more involved than the 1D version.