LC 162 — Find Peak Element

Problem

What are we solving?

Problem Statement

A peak element is an element strictly greater than its neighbors. Given an integer array nums where nums[i] != nums[i+1], return the index of any peak element. The array is virtually bounded by -∞ on both sides. Must run in O(log n).

Example 1

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

Output:2

Example 2 — multiple peaks

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

Output:1 or 5 (either valid)

Intuition

Follow the slope — a peak always exists ahead

The array doesn't need to be sorted. The key invariant: if nums[mid] < nums[mid+1], we are on an upward slope — a peak must exist to the right. If nums[mid] > nums[mid+1], we are descending — a peak is at mid or to the left. In either case, we safely discard half the array.

Think of it as hiking. If the trail goes uphill ahead, keep walking right. If it goes downhill, the top is behind you. You always converge on a summit.

nums = [1, 2, 1, 3, 5, 6, 4] — slope directions

↑1

↓2

↑1

↑3

↑5

↓ peak6

end4

At mid=3 (value 3): nums[3] < nums[4] → uphill → go right. Eventually lands on index 5 (value 6).

Step-by-step walkthrough

1

left=0, right=6 → mid=3, nums[3]=3, nums[4]=5

3 < 5 → uphill → peak is to the right. left = 4.

2

left=4, right=6 → mid=5, nums[5]=6, nums[6]=4

6 > 4 → downhill → peak is mid or to the left. right = 5.

3

left=4, right=5 → mid=4, nums[4]=5, nums[5]=6

5 < 6 → uphill → peak to the right. left = 5.

4

left=5, right=5 → mid=5

left == right → return 5. nums[5]=6 is indeed a peak.

Solution

Clean implementation

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {         // strict: converges to single element
            int mid = left + (right - left) / 2;

            if (nums[mid] < nums[mid + 1])
                left = mid + 1;        // uphill — peak is to the right
            else
                right = mid;            // downhill — peak is mid or left
        }

        return left;                  // left == right == peak index
    }
}

class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:          # strict: converges to single element
            mid = left + (right - left) // 2

            if nums[mid] < nums[mid + 1]:
                left = mid + 1       # uphill — peak is to the right
            else:
                right = mid           # downhill — peak is mid or left

        return left                   # left == right == peak index

→

Note while left < right: This variant converges left and right to the same index without needing a saved boundary variable. When they meet, that index is the peak. It works because we never set right = mid - 1 — we always keep mid as a candidate.

Complexity

Time

O(log n)

Halves the range each step using the slope invariant.

Space

O(1)

Constant space — no auxiliary structures.