Find Peak Element

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

1. 1Iterate with index i from 0 up to but not including the last index.
2. 2At each step compare nums[i] with nums[i + 1].
3. 3If nums[i] is greater than nums[i + 1], the ascent has ended, so return i.
4. 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

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

1. 1Set lo to 0 and hi to the last index.
2. 2While lo is less than hi, compute mid as the lower middle of the range.
3. 3If nums[mid] is less than nums[mid + 1], the peak lies to the right, so set lo to mid + 1.
4. 4Otherwise the peak is at mid or to the left, so set hi to mid.
5. 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