Skip to content

162. Find Peak Element

On LeetCode ->

Reformulated question

Find any index i such that nums[i] is greater than its neighbors, with out-of-bounds neighbors treated as \(-\infty\), and do it in \(O(\log n)\).

  • Example: nums = [1,2,1,3,5,6,4] -> 1 or 5 because 2 and 6 are both peaks.

Key trick

Use binary search on the slope:

  • If nums[mid] < nums[mid + 1], a peak must exist on the right.
  • Otherwise, a peak must exist on the left, including mid.

This works because moving uphill guarantees some peak ahead, possibly at the boundary.

Trap

Common mistakes:

  • Returning the maximum element with a linear scan, which breaks the \(O(\log n)\) requirement.
  • Overcomplicating boundary checks instead of using the slope rule with mid + 1.
  • Forgetting that any peak is valid.
  • Mishandling arrays of length 1 or strictly increasing/decreasing arrays.

Why is this question interesting?

It looks like a local-condition problem, but the clean solution is binary search on structure rather than exact value.

Solution with idiomatic Python

class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        # Binary search on the slope.
        # If mid < mid + 1, we are going uphill, so a peak exists to the right.
        # Otherwise, a peak exists at mid or to the left.
        left, right = 0, len(nums) - 1

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

            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid

        return left
  • Time: \(O(\log n)\)
  • Space: \(O(1)\)

Pytest test

import pytest


def is_peak(nums: list[int], i: int) -> bool:
    left = nums[i - 1] if i > 0 else float("-inf")
    right = nums[i + 1] if i < len(nums) - 1 else float("-inf")
    return nums[i] > left and nums[i] > right


@pytest.mark.parametrize(
    ("nums", "valid_indices"),
    [
        ([1], {0}),
        ([1, 2], {1}),
        ([2, 1], {0}),
        ([1, 2, 3, 1], {2}),
        ([1, 2, 1, 3, 5, 6, 4], {1, 5}),
        ([1, 2, 3, 4], {3}),
        ([4, 3, 2, 1], {0}),
        ([1, 3, 2], {1}),
        ([5, 4, 5], {0, 2}),
        ([1, 5, 1, 5, 1], {1, 3}),
    ],
)
def test_findPeakElement(nums, valid_indices):
    result = Solution().findPeakElement(nums)
    assert result in valid_indices
    assert is_peak(nums, result)

Comment on my solution

Your notes are heading in the right direction:

  • You correctly identified edge cases:
    • single element
    • strictly increasing
    • strictly decreasing
    • interior peak
  • The missing step is the binary-search invariant:
    • compare nums[mid] and nums[mid + 1]
    • keep the half that must contain a peak

A good interview version is to avoid classifying many patterns and instead rely on that one rule.

## Solution

class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        # 1 2 3 1 -> 2
        # 1 3 2 1 -> 1
        # 1 2 1 3 5 6 4 -> 1 or 5
        # 1 2 3 4 5 6 4 -> 5
        # 7 6 5 4 5 6 4 -> 5
        # 4 5 6 4 3 2 1 -> 2
        # 1 -> 0
        # 1 2 -> 1
        # 1 3 4 -> 2
        # 1 3 2 -> 1
        #
        # nums[i] != nums[i + 1] and len(nums) >=3
        #   - if nums not monotone
        #     - peak will be found inside nums
        #   - if nums only increase
        #     - peak is the last element
        #   - if nums only decrease
        #     - peak is the first element