Find Peak Element

Q: What is the time complexity of Find Peak Element?

The binary search runs in O(log n) time and O(1) space, at most 13 steps for 5000 values. The walk from the left is O(n) , since it may read every pair before it finds the drop.

Q: Does the binary search still work when there are several peaks?

Yes, as long as neighbours differ and the spots past both ends count as lower than every value. It returns one peak, not always the highest. After a step up, the values must turn down by the end of the range at the latest, and the first turn is a peak, so the side the search keeps always holds one.

Q: Is the peak always the largest value?

In this problem, yes: the array rises to one peak and falls after it, so nothing else can be larger. In the version with several peaks it is not, since any value larger than both neighbours counts. That is why the search compares neighbours instead of looking for the maximum.

MediumBinary search

+10

The array nums climbs and then falls: each value is larger than the one before it up to some index, and each value after that index is smaller than the one before it. Either part may be empty, so the array may only climb or only fall. The value at the turning index is the peak, the only value larger than every neighbour it has.

Return the index of the peak, in O(log n) time.

Function

findPeakElement(nums: integer-array) → integer

numsinteger-array: the values, rising to one peak and then falling
Returnsinteger: the index of the peak

Constraints

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] for every valid i.
nums strictly increases up to one index and strictly decreases after it, so there is exactly one peak.

Examples

Input: nums = [2, 5, 9, 4, 1]
Output: 2
Explanation: The values rise through 2, 5 and 9, then fall through 4 and 1. The turn is at 9, index 2.

Follow-up

In a grid where no two neighbouring cells are equal, a peak is a cell larger than its up to four neighbours. Can you find one without reading every cell?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

With a single peak, the peak is the largest value, so one pass finds it in O(n). For O(log n), compare nums[mid] with nums[mid+1]: the slope at mid tells you which side of the peak it stands on, so every step can drop half of the range.

Walk until the values start to fall

Intuition

Before the peak every value is smaller than the next one, and from the peak on every value is larger. So the peak is the first index i where nums[i] > nums[i+1], or the last index if the array only climbs.

When the peak sits at the end of 5000 values, the walk makes 4999 comparisons, where binary search needs 13.

Algorithm

For i from 0 to n-2, compare nums[i] with nums[i+1].
At the first i where nums[i] is larger, return i.
If the loop ends without a drop, return n-1.

def findPeakElement(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i  # the first step down starts at the peak
    return len(nums) - 1  # never went down: the last value is the peak

Binary search on the slope

Intuition

Read one pair, nums[mid] and nums[mid+1]. A step up means the array is still climbing, which on this array happens only before the peak: the peak is at mid+1 or to its right. A step down means you are at the peak or past it: the peak is at mid or to its left.

Keep a range [lo, hi] that always holds the peak. A step up moves lo to mid+1. A step down moves hi to mid, keeping mid because it may be the peak. When lo meets hi, the one index left is the peak. Rounding mid down keeps it below hi, so mid+1 always exists.

In the first example, mid = 2 sees 9 > 4, so hi = 2; then mid = 1 sees 5 < 9, so lo = 2, the peak. 5000 values take at most 13 steps.

Algorithm

Set lo = 0 and hi = n-1.
While lo < hi, take mid = lo + (hi - lo) / 2, rounded down.
If nums[mid] < nums[mid+1], set lo = mid + 1.
Otherwise set hi = mid.
Return lo.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1  # the peak is always inside [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2  # mid < hi, so mid + 1 is a valid index
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # still climbing: the peak is to the right of mid
        else:
            hi = mid  # going down: the peak is mid or to its left
    return lo

Pitfalls and edge cases

Setting hi = mid - 1 on a step down. In [2, 5, 9, 4, 1] the first mid is the peak itself, and hi = 1 throws it away; the search returns 1.
Comparing with nums[mid-1] while rounding mid down. mid can be 0, where there is no left neighbour.
Using a half-open range with hi = n. Then mid can be n-1, and nums[mid+1] reads past the end, at once for a single value.
Forgetting the shift in Lua and R. The answer is still the 0-based index, so a position i is returned as i-1.

Frequently asked questions3

What is the time complexity of Find Peak Element?

The binary search runs in O(log n) time and O(1) space, at most 13 steps for 5000 values. The walk from the left is O(n), since it may read every pair before it finds the drop.

Does the binary search still work when there are several peaks?

Yes, as long as neighbours differ and the spots past both ends count as lower than every value. It returns one peak, not always the highest. After a step up, the values must turn down by the end of the range at the latest, and the first turn is a peak, so the side the search keeps always holds one.

Is the peak always the largest value?

In this problem, yes: the array rises to one peak and falls after it, so nothing else can be larger. In the version with several peaks it is not, since any value larger than both neighbours counts. That is why the search compares neighbours instead of looking for the maximum.

def findPeakElement(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [2, 5, 9, 4, 1]

Expected Output