LeetCode 162: Find Peak Element

Problem Restatement

We are given a 0-indexed integer array nums.

A peak element is an element strictly greater than its neighbors.

We need to return the index of any peak element.

The array boundary is treated as negative infinity:

nums[-1] = nums[n] = -infinity

So the first element can be a peak if it is greater than the second element. The last element can be a peak if it is greater than the second-to-last element.

The problem requires an O(log n) algorithm. Adjacent elements are never equal.

Input and Output

Example function shape:

def findPeakElement(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [1, 2, 3, 1]

The value 3 is greater than both neighbors:

3 > 2
3 > 1

So the answer is:

2

Example 2:

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

There are two valid peaks.

Index 1 is valid because:

2 > 1
2 > 1

Index 5 is also valid because:

6 > 5
6 > 4

So either answer is valid:

1

or:

5

Example 3:

nums = [1]

The only element is greater than both outside boundaries.

So the answer is:

0

First Thought: Linear Scan

A direct solution is to check every index.

For each index, compare it with its left and right neighbors.

class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        n = len(nums)

        for i in range(n):
            left = nums[i - 1] if i > 0 else float("-inf")
            right = nums[i + 1] if i + 1 < n else float("-inf")

            if nums[i] > left and nums[i] > right:
                return i

        return -1

This works, but it takes O(n) time.

The problem asks for O(log n), so we need binary search.

Key Insight

Even though the array is not sorted, we can still use binary search by looking at the slope.

At index mid, compare:

nums[mid]
nums[mid + 1]

If:

nums[mid] > nums[mid + 1]

then the array is going downward at mid.

A peak must exist on the left side, including mid.

If:

nums[mid] < nums[mid + 1]

then the array is going upward at mid.

A peak must exist on the right side.

This works because the outside boundary is negative infinity, and adjacent elements are not equal.

Why the Slope Tells Us Where a Peak Exists

Suppose:

nums[mid] < nums[mid + 1]

We are climbing upward from mid to mid + 1.

If the array keeps increasing all the way to the end, the last element is a peak because the right boundary is negative infinity.

If the array stops increasing somewhere, then at the first place where it goes down, that turning point is a peak.

So a peak must exist to the right.

Now suppose:

nums[mid] > nums[mid + 1]

We are going downward from mid to mid + 1.

If the array keeps decreasing all the way to the start, the first element is a peak because the left boundary is negative infinity.

If the array stopped decreasing earlier, the turning point is a peak.

So a peak must exist at mid or to the left.

Algorithm

Use binary search.

Initialize:

left = 0
right = len(nums) - 1

While left < right:

1. Compute mid.
2. Compare nums[mid] and nums[mid + 1].
3. If nums[mid] > nums[mid + 1], move right = mid.
4. Otherwise, move left = mid + 1.

When the loop ends, return left.

Walkthrough

Use:

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

Start:

left = 0
right = 6

Middle:

mid = 3
nums[mid] = 3
nums[mid + 1] = 5

Since 3 < 5, we are climbing.

A peak exists on the right.

Move:

left = mid + 1 = 4

Now:

left = 4
right = 6

Middle:

mid = 5
nums[mid] = 6
nums[mid + 1] = 4

Since 6 > 4, we are descending.

A peak exists at mid or to the left.

Move:

right = mid = 5

Now:

left = 4
right = 5

Middle:

mid = 4
nums[mid] = 5
nums[mid + 1] = 6

Since 5 < 6, move:

left = mid + 1 = 5

Now:

left = 5
right = 5

Return:

5

The value is:

nums[5] = 6

which is a peak.

Correctness

At every step, the search interval [left, right] contains at least one peak.

Initially, the whole array contains at least one peak because the boundaries are negative infinity and adjacent values are distinct.

During the search, we compare nums[mid] with nums[mid + 1].

If nums[mid] > nums[mid + 1], then moving left from mid either keeps descending until index 0, making index 0 a peak, or eventually finds a place where the direction changes from rising to falling, which is also a peak. Therefore, a peak exists in [left, mid], so setting right = mid preserves the invariant.

If nums[mid] < nums[mid + 1], then moving right from mid + 1 either keeps rising until the last index, making the last index a peak, or eventually finds a place where the direction changes from rising to falling, which is a peak. Therefore, a peak exists in [mid + 1, right], so setting left = mid + 1 preserves the invariant.

The loop stops when left == right. The interval still contains a peak, and it contains only one index. Therefore, that index is a peak.

Complexity

Implementation

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

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

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

        return left

Code Explanation

We search the full array:

left = 0
right = len(nums) - 1

The loop continues while more than one candidate remains:

while left < right:

Compute the middle:

mid = (left + right) // 2

Because left < right, mid + 1 is always a valid index.

If the slope goes down:

if nums[mid] > nums[mid + 1]:
    right = mid

we keep the left side, including mid.

Otherwise, the slope goes up:

else:
    left = mid + 1

we keep the right side.

Finally:

return left

returns an index of a peak element.

Testing

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

def run_tests():
    sol = Solution()

    nums = [1, 2, 3, 1]
    ans = sol.findPeakElement(nums)
    assert is_peak(nums, ans)

    nums = [1, 2, 1, 3, 5, 6, 4]
    ans = sol.findPeakElement(nums)
    assert is_peak(nums, ans)

    nums = [1]
    ans = sol.findPeakElement(nums)
    assert ans == 0

    nums = [1, 2]
    ans = sol.findPeakElement(nums)
    assert ans == 1

    nums = [2, 1]
    ans = sol.findPeakElement(nums)
    assert ans == 0

    nums = [1, 2, 3, 4, 5]
    ans = sol.findPeakElement(nums)
    assert ans == 4

    nums = [5, 4, 3, 2, 1]
    ans = sol.findPeakElement(nums)
    assert ans == 0

    print("all tests passed")

run_tests()