Find Peak Element
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Find any index whose value is greater than both neighbours (the ends see an imaginary negative infinity), in O(log n).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If the middle value is smaller than the one to its right, which side must contain a peak?
- Hint 2Walking uphill must end at a peak or at the edge of the list.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
You are on a foggy hillside and want to reach a hilltop. You can only feel your own height and the height of the step next to you. If the next step to the right is higher, keep climbing that way, because a hill must top out before the valley ends. If the step to the right is lower, you are already climbing down: a top is here or behind you.
- The obvious way
Scan for the first value bigger than its neighbours: O(n).
- The key insight
If the middle is lower than its right neighbour the ground rises to the right, and it cannot rise for ever (the edge counts as a drop), so a peak exists on the right: move there. Otherwise a peak exists at the middle or to the left. Halve each time.
- The algorithm
- Markers at both ends.
- Compare the middle with the value just right of it.
- Right value bigger? Go uphill: left marker = middle + 1.
- Otherwise a peak is here or behind: right marker = middle. When the markers meet, that is a peak.
Watch it run
Exampleheights = [1, 2, 1, 3, 5, 6, 4]
Middle is 3, its right neighbour is 5: uphill to the right. A peak must be there.
range: positions 4 to 6
Where people slip
- middle + 1 is always inside the list because low < high means middle < high.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def find_peak_element(nums):
low, high = 0, len(nums) - 1
while low < high:
middle = (low + high) // 2
if nums[middle] < nums[middle + 1]:
low = middle + 1 # uphill to the right: a peak is there
else:
high = middle # falling: a peak is here or behind
return lowNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.