MediumArrayBinary Search

Find Peak Element

2 approaches, code in every language

You are given an integer array. A position is called a peak when its value is strictly greater than the value immediately to its left and the value immediately to its right. For the purposes of this definition, imagine that the slots just outside the array on either end hold negative infinity, so the very first or very last element can also qualify as a peak.

Return the index of any single peak. The array can contain more than one peak, and returning the index of any one of them is accepted. Your solution should run in logarithmic time with respect to the length of the array.

Example 1

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

Output: 2

The value 3 sitting at index 2 is larger than both of its neighbours (2 on the left and 1 on the right), so index 2 is a peak.

Example 2

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

Output: 5

Index 5 holds 6, which is greater than 5 on its left and 4 on its right. Index 1 (value 2) is also a valid peak, but returning any one of them is fine.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums[i] != nums[i + 1] for every valid index i

Linear Scan for the First Descent

Walk left to right and stop the moment a value is larger than its right neighbour.

Loading animation…

Intuition

Because neighbouring elements are never equal, the array is a sequence of rising and falling runs. Starting from the left, as long as each value is smaller than the next one we are still climbing. The first time an element is greater than the element after it, we have just crossed the top of a climb, so the current index is a peak. If we never see such a drop, the array climbed all the way to the end, which makes the last index the peak.

Algorithm walkthrough

1Iterate with index i from 0 up to but not including the last index.
2At each step compare nums[i] with nums[i + 1].
3If nums[i] is greater than nums[i + 1], the ascent has ended, so return i.
4If the loop finishes without finding a drop, the array was strictly increasing, so return the last index.

Implementation

from typing import List

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return i
        return len(nums) - 1

Time

O(n)

Space

O(1)

Every element may be inspected once in the worst case.

Binary Search on the Slope

Halve the search range each step by moving toward the uphill direction.

Loading animation…

Intuition

At the midpoint we only need to know whether we are on a rising or a falling part of the array. If the middle element is smaller than its right neighbour we are on an upward slope, and a peak must exist somewhere to the right, so we can safely discard the left half including the midpoint. Otherwise the midpoint is either a peak or on a downward slope, and a peak is guaranteed at the midpoint or to its left. Repeatedly shrinking toward the uphill side converges to a peak.

Algorithm walkthrough

1Set lo to 0 and hi to the last index.
2While lo is less than hi, compute mid as the lower middle of the range.
3If nums[mid] is less than nums[mid + 1], the peak lies to the right, so set lo to mid + 1.
4Otherwise the peak is at mid or to the left, so set hi to mid.
5When lo equals hi the range has collapsed onto a peak; return lo.

Implementation

from typing import List

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < nums[mid + 1]:
                lo = mid + 1
            else:
                hi = mid
        return lo

Time

O(log n)

Space

O(1)

Each iteration discards half of the remaining range.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Survey Line Crest is our own problem on the technique behind Find Peak Element: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free