162. Find Peak Element

Problem¶

Find any index i such that nums[i] is greater than its neighbors, with out-of-bounds neighbors treated as \(-\infty\), and adjacent numbers are distinct. 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 it interesting?¶

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

Python solution¶

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.
        l, r = 0, len(nums) - 1

        while l < r:
            mid = (l + r) // 2

            if nums[mid] < nums[mid + 1]:
                l = mid + 1
            else:
                r = mid

        return l

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

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