Space
Open
From Fieldwork
Scales
Archive
Why this works
Search Space: We start with the whole array.
The Comparison: We compare arr[mid] to its neighbor. This essentially calculates a "local derivative."
The Convergence: Because the array is guaranteed to be a mountain, the left pointer will climb the hill from the left, and the right pointer will descend the hill from the right until they meet exactly at the highest point.
We're simply looking at the derivative!
And derivatives are just... they go in both directions!
"Since this is a unimodal function, I'm going to perform a binary search on the discrete derivative to find the root where the slope flips"
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
# Check if we're on an uphill or a downhill
if arr[mid] < arr[mid + 1]:
# We're on the left side of the peak! Move right
left = mid + 1
else:
# We're either at the peak or on the right side! Move left
# We can't do mid - 1 because mid might be the peak itself
right = mid
return leftPractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode