Peak Index in a Mountain Array

Intuition

Because the array strictly ascends and then strictly descends, the first index where the value drops below its predecessor marks the point just past the summit. Scanning left to right and catching that first decrease directly locates the peak, even though it inspects up to every element.

Algorithm walkthrough

1. 1Start comparing from the second element onward.
2. 2At each step, check whether the current value is smaller than the one before it.
3. 3The first time that happens, the previous index was the peak, so return it.
4. 4If no drop is ever seen, the array kept rising, so the last index is the peak.

Implementation

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        for i in range(1, len(arr)):
            if arr[i] < arr[i - 1]:
                return i - 1
        return len(arr) - 1

Intuition

At any midpoint, comparing it with its right neighbor tells us whether we are still climbing or already falling. If the next element is larger we are on the ascending face and the peak lies to the right; otherwise we are on the descending face and the peak is at mid or to its left. Repeatedly applying this halves the range until only the summit remains.

Algorithm walkthrough

1. 1Initialize lo at the first index and hi at the last index.
2. 2While lo is less than hi, take the midpoint.
3. 3If arr[mid] is smaller than arr[mid + 1], we are still ascending, so move lo to mid + 1.
4. 4Otherwise the peak is at mid or earlier, so set hi to mid.
5. 5When lo meets hi, that index is the summit.

Implementation

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