LeetCode 162 - Find Peak Element

The problem gives us an integer array nums and asks us to find the index of any peak element. A peak element is defined as an element that is strictly greater than its immediate neighbors.

leetcodemediumarraybinary-search

LeetCode Problem 162

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem gives us an integer array nums and asks us to find the index of any peak element.

A peak element is defined as an element that is strictly greater than its immediate neighbors. For an element at index i, this means:

  • nums[i] > nums[i - 1]
  • nums[i] > nums[i + 1]

The problem also defines imaginary values outside the array boundaries:

  • nums[-1] = -∞
  • nums[n] = -∞

This definition is important because it means the first or last element can also be a peak. For example:

  • In [3,2,1], the first element 3 is a peak because it is greater than 2 and also greater than -∞.
  • In [1,2,3], the last element 3 is a peak because it is greater than 2 and also greater than -∞.

The input array is guaranteed to satisfy:

nums[i] != nums[i + 1]

This guarantee is extremely important because adjacent elements are never equal. That means every comparison between neighboring elements is strictly increasing or strictly decreasing. This property allows binary search to work cleanly.

The problem requires an algorithm with O(log n) time complexity, which strongly suggests that a binary search based solution is expected. A linear scan would work logically, but it would not satisfy the required complexity.

Some important edge cases include:

  • Arrays with only one element
  • Strictly increasing arrays
  • Strictly decreasing arrays
  • Peaks at the boundaries
  • Multiple valid peaks

The problem allows returning the index of any valid peak, so we do not need to find all peaks or the maximum element.

Approaches

Brute Force Approach

The most straightforward solution is to scan the array from left to right and check whether each element is a peak.

For each index i, we compare the current element with its left and right neighbors. If the current element is greater than both, we return its index.

This works because the definition of a peak is local. We only need to compare neighboring elements.

However, this approach requires examining every element in the worst case, which leads to O(n) time complexity. Since the problem explicitly requires O(log n) time, this approach is not acceptable as the final solution.

Key Insight for the Optimal Solution

The important observation is that we can use the slope between adjacent elements to eliminate half of the search space.

Suppose we are at index mid.

  • If nums[mid] > nums[mid + 1], then the sequence is descending at mid. This means there must be a peak somewhere on the left side, including mid itself.
  • If nums[mid] < nums[mid + 1], then the sequence is ascending at mid. This means there must be a peak somewhere on the right side.

Why is this true?

If the array is ascending, eventually one of two things happens:

  • The ascent stops and creates a peak
  • The ascent continues to the end, making the last element a peak

Similarly, if the array is descending, a peak must exist on the left side.

This property allows us to perform binary search and reduce the search space by half at every step.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Scan every element and check neighbors
Optimal O(log n) O(1) Binary search using slope direction

Algorithm Walkthrough

Optimal Binary Search Algorithm

  1. Initialize two pointers, left = 0 and right = len(nums) - 1.

These pointers define the current search range where a peak is guaranteed to exist. 2. Continue searching while left < right.

The loop stops when both pointers converge to a single index, which will be a peak. 3. Compute the middle index:

mid = (left + right) // 2
  1. Compare nums[mid] with nums[mid + 1].

This comparison tells us whether we are on an ascending slope or a descending slope. 5. If nums[mid] > nums[mid + 1], move the search space left:

right = mid

Since the sequence is descending, a peak must exist at mid or somewhere to the left. 6. Otherwise, move the search space right:

left = mid + 1

Since the sequence is ascending, a peak must exist on the right side. 7. When the loop ends, return left.

At this point, left == right, and that index is guaranteed to be a peak.

Why it works

The algorithm maintains the invariant that at least one peak exists inside the current search interval.

At every step, the comparison between nums[mid] and nums[mid + 1] tells us which side must contain a peak. Because adjacent elements are never equal, we always have a strictly increasing or strictly decreasing slope.

By discarding half of the search space each time, the algorithm eventually converges to a valid peak index in logarithmic time.

Python Solution

from typing import List

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

The implementation starts by initializing the binary search boundaries with left and right.

Inside the loop, we compute the midpoint and compare the current value with the next value. This comparison determines whether the slope is increasing or decreasing.

If the slope is descending, we keep the left half by setting right = mid. We include mid because it could itself be the peak.

If the slope is ascending, we discard the left half and continue searching on the right side with left = mid + 1.

The loop terminates when the search interval shrinks to a single element. Since the invariant guarantees a peak exists in the interval, that remaining index must be a peak.

Go Solution

func findPeakElement(nums []int) int {
    left := 0
    right := len(nums) - 1

    for left < right {
        mid := (left + right) / 2

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

    return left
}

The Go implementation follows the same logic as the Python version.

Go slices already provide efficient indexed access, so no additional data structures are needed. Integer overflow is not a concern here because the array size is at most 1000, though in larger systems many developers still prefer:

mid := left + (right-left)/2

Both versions use constant extra space and perform binary search iteratively.

Worked Examples

Example 1

Input:

nums = [1,2,3,1]
Iteration left right mid nums[mid] nums[mid+1] Decision
1 0 3 1 2 3 Ascending, search right
2 2 3 2 3 1 Descending, search left

After iteration 2:

left = 2
right = 2

The loop ends, and we return 2.

The peak element is 3.

Example 2

Input:

nums = [1,2,1,3,5,6,4]
Iteration left right mid nums[mid] nums[mid+1] Decision
1 0 6 3 3 5 Ascending, search right
2 4 6 5 6 4 Descending, search left
3 4 5 4 5 6 Ascending, search right

After iteration 3:

left = 5
right = 5

The algorithm returns 5.

The peak element is 6.

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Binary search cuts the search space in half each iteration
Space O(1) Only a few variables are used

The time complexity is logarithmic because each iteration removes half of the remaining search range. Starting from n elements, the search interval shrinks exponentially until only one index remains.

The space complexity is constant because the algorithm uses only a fixed number of variables regardless of input size.

Test Cases

from typing import List

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

solution = Solution()

# Provided example 1
assert solution.findPeakElement([1, 2, 3, 1]) == 2

# Provided example 2, result can be 1 or 5
assert solution.findPeakElement([1, 2, 1, 3, 5, 6, 4]) in [1, 5]

# Single element array
assert solution.findPeakElement([10]) == 0

# Strictly increasing array, last element is peak
assert solution.findPeakElement([1, 2, 3, 4, 5]) == 4

# Strictly decreasing array, first element is peak
assert solution.findPeakElement([5, 4, 3, 2, 1]) == 0

# Peak in the middle
assert solution.findPeakElement([1, 3, 2]) == 1

# Multiple peaks
assert solution.findPeakElement([1, 3, 2, 4, 1]) in [1, 3]

# Two elements increasing
assert solution.findPeakElement([1, 2]) == 1

# Two elements decreasing
assert solution.findPeakElement([2, 1]) == 0

# Large peak near end
assert solution.findPeakElement([1, 2, 3, 4, 10, 2]) == 4
Test Why
[1,2,3,1] Standard example with peak in middle
[1,2,1,3,5,6,4] Multiple valid peaks
[10] Single element boundary case
[1,2,3,4,5] Strictly increasing sequence
[5,4,3,2,1] Strictly decreasing sequence
[1,3,2] Small array with center peak
[1,3,2,4,1] Confirms any valid peak is acceptable
[1,2] Small increasing array
[2,1] Small decreasing array
[1,2,3,4,10,2] Peak near the end

Edge Cases

A single element array is the smallest possible input. Since the imaginary neighbors outside the array are -∞, the lone element is automatically a peak. Many incorrect implementations accidentally access out of bounds indices here. This solution handles it naturally because the binary search loop never executes when left == right.

Strictly increasing arrays are another important edge case. In an array like [1,2,3,4,5], every comparison moves the search interval to the right. Eventually, the algorithm converges on the last element, which is a valid peak because the right boundary behaves like -∞.

Strictly decreasing arrays can also expose bugs in binary search logic. In [5,4,3,2,1], every comparison moves the search interval leftward. The algorithm correctly converges on index 0, which is a peak because the left boundary behaves like -∞.

Arrays with multiple peaks are important because the problem does not require finding a specific peak. A naive implementation might incorrectly try to locate the global maximum. This solution works because the binary search invariant guarantees that at least one peak remains in the active search range, regardless of how many peaks exist overall.