See all coding puzzles and patterns here.

Problem Definition

A peak element in an array is one that is strictly greater than its neighbors. I.e., an element nums[i] is a peak element if nums[i] > nums[i - 1] and nums[i] > nums[i + 1].

Given an array, find a peak element and return its index. If there are multiple peak elements, return the index of any one of them. Elements at the edges of the array, nums[0] and nums[-1], only need to be greater than their single neighbor, nums[1] and nums[-2], respectively.

Assume that $\forall i$, nums[i] $\neq$ nums[i + 1].

Solution

We implement a binary search solution, which can be used for this problem as explained below. For every mid index, if it's a peak, we just return the mid index. If it's not a peak, we move the mid index toward the side that is higher than mid. The presence of a greater element on that side means that either:

  • there's a monotonically increasing sequence in that direction, which terminates in a peak element, or
  • the sequence is interrupted by a decrease, which makes the prior element a peak.
def find_peak_element(nums):
    l, r = 0, len(nums) - 1
    while l < r:
        mid = (l + r) // 2
        if nums[mid] > nums[mid + 1]:
            if mid == 0 or nums[mid] > nums[mid - 1]:
                return mid
            r = mid
        else:
            l = mid + 1
    return l

Complexity

Let $n = $ len(nums).

Runtime complexity should be $O(log(n))$.

Auxiliary space complexity should be $O(1)$ since we're just storing 3 integer values.