Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Return the index of *any* peak — an element strictly greater than both neighbors — where out-of-bounds neighbors count as −∞. The surprise is that you can do this in O(log n) on an UNSORTED array: compare nums[mid] with nums[mid+1] and always walk uphill. If nums[mid] < nums[mid+1] a peak must exist to the right, so go right; otherwise a peak exists at mid or to the left. Use `while (lo < hi)` with `hi = mid` (not mid − 1) and return `lo`.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you realise binary search applies to an UNSORTED array because the *slope* is what's exploited, and whether you can argue the correctness invariant ('a peak always lives inside [lo, hi]') rather than just pattern-matching to a template.
Where candidates slip
Assuming binary search needs sorted input and defaulting to an O(n) scan, or writing `hi = mid - 1` (which can throw away the only peak) and `while (lo <= hi)` (which over-runs and reads out of bounds).
How to stand out
Prove the invariant: if `nums[mid] < nums[mid+1]`, the right side starts by rising and ends at −∞, so it MUST turn around at some peak — therefore a peak is guaranteed on the right. Then explain why `hi = mid` keeps that peak in the window.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewFind any local peakNeed ALL peaks or just one?AllAny oneExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Linear Scan (Baseline)
1Hint 1Explore hintHide hint
Forget cleverness: walk left to right. When does an element stop being smaller than the next one?
2Hint 2Explore hintHide hint
Return the first index `i` where `nums[i] > nums[i + 1]` — that's a peak, because everything before kept rising to it.
3Hint 3Explore hintHide hint
If you never find such a descent, the array is strictly increasing, so the last index is the peak.
A · Core idea
Scan from the front comparing each element to its right neighbor. Return the first index i with nums[i] > nums[i + 1]. If no such index exists, the array rose all the way to the end, so return n - 1.
Why the first descent is a peak. Reading left to right, the moment the sequence stops increasing (nums[i] > nums[i + 1]) we know nums[i] is greater than its right neighbor. It's also greater than its left neighbor: either i == 0 (left neighbor is −∞) or we only reached i because nums[i - 1] < nums[i] (otherwise the descent would have triggered earlier). Both neighbors are smaller, so nums[i] is a peak.
Why mention it. It's a correct, easy-to-justify baseline that establishes the O(n) cost we're about to beat. Saying 'the naive scan is O(n)' frames the improvement and shows you can reason about why an element qualifies as a peak — the same reasoning the binary search will lean on.
Why it's not the intended answer. The prompt demands O(log n). The scan inspects potentially every element, ignoring that a single comparison at the midpoint already tells us which half must contain a peak. That directional information is exactly what lets us discard half the array at a time.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 2, 3, 1]i=0
nums[0]=1 > nums[1]=2? no
still climbing2C · Code with teaching comments
Reference implementation previewpublic int findPeakElement(int[] nums) { for (int i = 0; i < nums.length - 1; i++) { if (nums[i] > nums[i + 1]) { return i; }Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The scan only learns 'is this the first descent?' one element at a time. Binary search reuses the same descent reasoning — but applied at the midpoint, where one comparison rules out an entire half because the −∞ boundary guarantees the kept half still turns around somewhere.
ComplexityO(n) time, O(1) space — One pass over up to n − 1 adjacent comparisons, no extra memory.
E · Edge cases and pitfalls3Looping `i` to `nums.length` instead of `nums.length - 1` — reads `nums[i + 1]` out of bounds.Explore edge casesHide edge cases
Pitfalls
- Looping `i` to `nums.length` instead of `nums.length - 1` — reads `nums[i + 1]` out of bounds.
- Forgetting the trailing `return n - 1` for a strictly increasing array.
- Shipping this when the prompt asks for O(log n).
Approach 2 of 2 · Optimal
Binary Search Uphill (Optimal)
1Hint 1Explore hintHide hint
You can't sort, but you can ask a directional question at the middle: is the slope at `mid` going up or down?
2Hint 2Explore hintHide hint
Compare `nums[mid]` with `nums[mid + 1]`. If it's rising, a peak must lie to the right (the right end is −∞, so it has to turn around). If it's falling, a peak lies at `mid` or to the left.
3Hint 3Explore hintHide hint
Keep the window with `while (lo < hi)` and set `lo = mid + 1` when rising, `hi = mid` when falling. The window always holds a peak; return `lo`.
A · Core idea
Maintain a window [lo, hi] that always contains at least one peak. Initialise lo = 0, hi = n - 1. While lo < hi, compute mid = lo + (hi - lo) / 2 and compare nums[mid] with nums[mid + 1]. If nums[mid] < nums[mid + 1] we're on an upward slope, so move lo = mid + 1. Otherwise we're on a downward (or flat-impossible) slope, so move hi = mid. When lo == hi the window is a single index — that element is a peak — return lo.
Why a peak is guaranteed in the kept half. Suppose nums[mid] < nums[mid + 1] (rising). Look at the subarray from mid + 1 to n - 1. It starts by going up (since nums[mid+1] > nums[mid]) and it ends at the −∞ sentinel beyond index n - 1. A sequence that rises and then must fall to −∞ has to turn around somewhere — that turning point is a peak. So discarding indices 0..mid is safe: a peak still exists in [mid + 1, hi]. The mirror argument holds when nums[mid] > nums[mid + 1]: the left part [lo, mid] ends high at mid and is bounded by −∞ on the far left, so it contains a peak — and mid itself might be it, which is why we keep mid.
Why `hi = mid` and never `mid - 1`. When the slope falls at mid, mid is a candidate peak — it beats its right neighbor and might beat its left one too. Writing hi = mid - 1 would evict mid from the window and could throw away the only peak (e.g. nums = [3, 2, 1], where index 0 is the answer). Keeping hi = mid preserves the invariant 'the window contains a peak'. This is the structural difference from value-search binary search, where you have tested mid and can safely exclude it.
Why `while (lo < hi)` and not `<=`. This template converges the window down to a single surviving index rather than searching for a known value. With hi = mid, the condition must be strict <: if it were <=, then when lo == hi == mid we'd evaluate nums[mid + 1] — potentially out of bounds at the right edge — and the window would never shrink, looping forever. The strict < stops exactly when one element remains.
Why `mid + 1` is always safe to read. mid = lo + (hi - lo) / 2 uses floor division, so whenever lo < hi we have mid < hi <= n - 1, hence mid + 1 <= n - 1 is a valid index. The loop guard and the floor together guarantee we never read past the end.
Why termination is guaranteed. Every branch strictly shrinks the window: lo = mid + 1 raises the lower bound past mid, and hi = mid lowers the upper bound below its old value (because mid < hi). A strictly shrinking non-empty integer window must reach lo == hi.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 2, 1, 3, 5, 6, 4]Array state
lo=0, hi=6
mid=3, nums[3]=3 < nums[4]=5 → go right
5C · Code with teaching comments
D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Binary search doesn't require sorted values — it requires a monotone decision that lets one probe eliminate half the candidates. Here the decision is 'which way is uphill?', and the −∞ boundaries guarantee the uphill direction always leads to a peak. Reframing 'sorted' as 'has a halving decision' is the unlock for rotated-array search, 'binary search on the answer', and every gradient-style problem.
ComplexityO(log n) time, O(1) space — Each iteration discards half the window, so it runs in ⌈log₂ n⌉ = O(log n) steps. Only scalar variables are used → O(1) space.
E · Edge cases and pitfalls8nums = [1] — lo == hi == 0 from the start, loop body never runs, return 0.Explore edge casesHide edge cases
Edge cases handled
nums = [1]lo == hi == 0 from the start, loop body never runs, return 0.nums = [1, 2]mid=0, nums[0]=1 < nums[1]=2 → lo=1; loop ends, return 1.nums = [2, 1]mid=0, nums[0]=2 > nums[1]=1 → hi=0; loop ends, return 0 (keeping mid mattered here).nums = [1, 2, 3, 4, 5]Always rising, lo marches to the last index → return 4.
Pitfalls
- Writing `hi = mid - 1` — can discard the only peak (e.g. [3,2,1] would miss index 0).
- Using `while (lo <= hi)` with `hi = mid` — reads nums[mid + 1] out of bounds and never terminates.
- Comparing `nums[mid]` with `nums[mid - 1]` instead of `nums[mid + 1]` — the template no longer matches the bound updates.
- Assuming binary search is illegal because the array isn't sorted — the slope provides the needed monotone decision.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int findPeakElement(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < nums[mid + 1]) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Excluding mid when going left
On a downward slope, `mid` is itself a peak candidate. `hi = mid - 1` removes it; for [3, 2, 1] the only peak is index 0 and this throws it away, returning a wrong index or running out of bounds.
Explore the code comparisonHide the code comparison
Excluding mid when going left
On a downward slope, `mid` is itself a peak candidate. `hi = mid - 1` removes it; for [3, 2, 1] the only peak is index 0 and this throws it away, returning a wrong index or running out of bounds.
Don't write this
if (nums[mid] < nums[mid + 1]) lo = mid + 1;
else hi = mid - 1;Write this instead
if (nums[mid] < nums[mid + 1]) lo = mid + 1;
else hi = mid;2Wrong loop condition for the hi = mid template
With `hi = mid`, the window can stall at `lo == hi`. Using `<=` keeps the loop alive there, evaluates `nums[mid + 1]` at the right edge (out of bounds), and never terminates. Strict `<` stops with one element.
Explore the code comparisonHide the code comparison
Wrong loop condition for the hi = mid template
With `hi = mid`, the window can stall at `lo == hi`. Using `<=` keeps the loop alive there, evaluates `nums[mid + 1]` at the right edge (out of bounds), and never terminates. Strict `<` stops with one element.
Don't write this
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1
else:
hi = midWrite this instead
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1
else:
hi = mid3Overflow in the midpoint
In Java `lo + hi` is a 32-bit int and can overflow for large indices, wrapping negative. Use the difference form even when the array is small — it's a free habit.
Explore the code comparisonHide the code comparison
Overflow in the midpoint
In Java `lo + hi` is a 32-bit int and can overflow for large indices, wrapping negative. Use the difference form even when the array is small — it's a free habit.
Don't write this
int mid = (lo + hi) / 2;Write this instead
int mid = lo + (hi - lo) / 2;Revise
Carry the pattern into the interview
Pattern to remember
Binary search on a slope — always climb toward the higher neighbor
Code pattern to memorize
lo, hi = 0, n - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # uphill to the right → peak is right
else:
hi = mid # downhill (or equal) → peak is at mid or left
return loRules to remember
- 1Binary search works even though the array is unsorted — the monotonicity is in the slope, not the values.
- 2Compare
nums[mid]withnums[mid + 1];midis computed by floor division somid + 1is always in bounds whilelo < hi. - 3Use
while (lo < hi)withhi = mid— notmid - 1— becausemiditself could be the peak and must stay in the window. - 4Treat
nums[-1] = nums[n] = -∞. The boundaries are the lowest, so a peak is guaranteed to exist and the search never falls off the ends. - 5The window always contains a peak (the invariant); when it shrinks to one element, that element is a peak — return
lo.
Use this pattern when
- Find a local maximum / any peak where neighbors are defined and ends are −∞
- The array isn't sorted but adjacent comparisons give a *direction* to move
- You only need *one* valid answer, not all peaks
- 'Walk uphill' / 'gradient' style reasoning over an index range
Choose another pattern when
- You need *all* peaks → a single linear scan is required, O(n)
- Neighbors aren't comparable or there's no notion of 'uphill' → binary search has no direction to follow
- The 'peak' is a global max with ties that matter → this finds *a* local peak, not a specific one
Interview takeaway
Find Peak Element shatters the myth that binary search needs a sorted array. What it really needs is a *monotone decision* — here, 'is the slope going up?' — that lets one comparison discard half the indices. Master this and you'll spot binary search in rotated arrays, Koko Eating Bananas, and any 'follow the gradient' problem.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternBinary search driven by a *slope* rather than sorted values. Recognise it whenever an adjacent comparison gives a guaranteed direction toward the answer and any single valid result is acceptable. The defining moves are `hi = mid` (keep the candidate) with `while (lo < hi)`; the same skeleton solves Peak Index in a Mountain Array and the 2D peak problem.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Peak Index in a Mountain ArrayComing soonSame uphill binary search, but the array is guaranteed strictly up then strictly down (exactly one peak).
- Find Minimum in Rotated Sorted ArrayBinary search comparing mid to an endpoint to decide which half holds the pivot/minimum.
- Search in Rotated Sorted ArrayDecide which half is sorted, then binary search that half for the target.
- Find a Peak Element IIComing soon2D version — binary search on columns, scan each column's max row. O(m log n).