64. Find Peak Element
🔗 LeetCode Problem: 162. Find Peak Element
📊 Difficulty: Medium
🏷️ Topics: Array, Binary Search
Problem Statement
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
Constraints:
- 1 <= nums.length <= 1000
- -2^31 <= nums[i] <= 2^31 - 1
- nums[i] != nums[i + 1] for all valid i
🎨 Visual Understanding
The Problem Visualized
Example 1: nums = [1, 2, 3, 1]
Visual:
3 ← peak (index 2)
↗ ↘
2 1
↗
1
Peaks: index 2 (value 3)
3 > 2 (left neighbor) ✓
3 > 1 (right neighbor) ✓
Example 2: nums = [1, 2, 1, 3, 5, 6, 4]
Visual:
6 ← peak (index 5)
↗ ↘
2 5 4
↗ ↘ ↗
1 1 3
↗
1
Peaks: index 1 (value 2) OR index 5 (value 6)
Both are valid answers!
Edge cases:
Single element: [5]
Index 0 is peak (no neighbors)
Increasing: [1, 2, 3, 4, 5]
Index 4 is peak (5 > 4, and 5 > -∞)
Decreasing: [5, 4, 3, 2, 1]
Index 0 is peak (5 > -∞, and 5 > 4)
All equal invalid (nums[i] != nums[i+1])
🚨 CRITICAL INSIGHT - Why Binary Search Works
The Key Pattern!
Amazing Observation:
A peak ALWAYS exists!
Even if no obvious peak, edges can be peaks!
Why?
nums[-1] = -∞ (conceptually)
nums[n] = -∞ (conceptually)
So first element > -∞ on left
And last element > -∞ on right
At least one peak guaranteed!
Binary Search Insight:
At any position mid:
If nums[mid] < nums[mid + 1]:
We're on "upward slope"
Peak MUST exist to the right! →
If nums[mid] > nums[mid + 1]:
We're on "downward slope"
Peak MUST exist to the left! ←
(mid itself could be peak)
We can eliminate half at each step!
The Upward vs Downward Slope Decision
Case 1: Upward Slope (nums[mid] < nums[mid + 1])
═══════════════════════════════════════════════════════════
[1, 2, 1, 3, 5, 6, 4]
↑ ↑
mid mid+1
1 < 3 (upward)
Since going up, and right boundary is -∞,
there MUST be a peak to the right!
Either:
- Continues up and hits right edge (peak!)
- Goes up then down (peak in between!)
Search right: left = mid + 1
Case 2: Downward Slope (nums[mid] > nums[mid + 1])
═══════════════════════════════════════════════════════════
[1, 2, 1, 3, 5, 6, 4]
↑ ↑
mid mid+1
6 > 4 (downward)
Since going down, and left boundary is -∞,
there MUST be a peak at mid or to the left!
Either:
- mid is the peak
- Peak exists to the left
Search left: right = mid
Visual Proof:
═══════════════════════════════════════════════════════════
Upward slope:
?
↗ or ↗ ↘ (peak guaranteed on right)
mid ↗ ↗
Downward slope:
↗ ↘ or ↘ (peak at mid or left)
mid mid
Why This Works - Proof
Claim: Peak always exists on the side we search
Proof for Upward (nums[mid] < nums[mid+1]):
We search right half: [mid+1, right]
Case A: Values keep increasing to right edge
→ Right edge is peak (greater than -∞)
Case B: Values eventually decrease
→ Before decrease, there's a peak
Either way, peak exists on right! ✓
Proof for Downward (nums[mid] > nums[mid+1]):
We search left half: [left, mid]
Case A: mid is peak (greater than both neighbors)
→ Found it!
Case B: Values increase from left
→ Before mid, there's a peak
Case C: mid is at left edge
→ mid is peak (greater than -∞)
Either way, peak exists on left or at mid! ✓
This guarantees we'll find a peak!
🎯 Approach 1: Linear Search (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Check each element:
If greater than both neighbors, it's a peak
Return that index
Implementation
public int findPeakElement(int[] nums) {
int n = nums.length;
// Single element
if (n == 1) return 0;
// Check first element
if (nums[0] > nums[1]) return 0;
// Check last element
if (nums[n - 1] > nums[n - 2]) return n - 1;
// Check middle elements
for (int i = 1; i < n - 1; i++) {
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
return i;
}
}
return -1; // Should never reach
}
⏰ Time: O(n) - Check every element
💾 Space: O(1) - Only variables
❌ Problem: Doesn't meet O(log n) requirement!
🎯 Approach 2: Binary Search (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Key Insight:
At any mid, we can determine which side has a peak
If ascending (mid < mid+1): peak on right
If descending (mid > mid+1): peak on left or at mid
Eliminate half each time!
The Strategy:
Binary Search for Peak:
1. while (left < right):
a. mid = left + (right - left) / 2
b. If nums[mid] < nums[mid + 1]:
Ascending, peak on right
left = mid + 1
c. Else:
Descending, peak on left or at mid
right = mid
2. return left
Implementation
public int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// Compare mid with its right neighbor
if (nums[mid] < nums[mid + 1]) {
// Ascending slope, peak must be on the right
left = mid + 1;
} else {
// Descending slope, peak is at mid or on the left
right = mid;
}
}
// When left == right, we've found a peak
return left;
}
⏰ Time: O(log n) - Binary search
💾 Space: O(1) - Only pointers
🔍 Dry Run
Example 1: nums = [1, 2, 3, 1]
Goal: Find any peak
Initial: left = 0, right = 3
[1, 2, 3, 1]
↑ ↑
left right
Iteration 1:
mid = 0 + (3 - 0) / 2 = 1
nums[1] = 2, nums[2] = 3
2 < 3 (ascending)
Peak on right
left = 2
[1, 2, 3, 1]
↑ ↑
left right
Iteration 2:
mid = 2 + (3 - 2) / 2 = 2
nums[2] = 3, nums[3] = 1
3 > 1 (descending)
Peak at mid or left
right = 2
[1, 2, 3, 1]
↑
left/right
Loop ends (left == right)
return 2 ✓
Verification: nums[2] = 3
3 > 2 (left) ✓
3 > 1 (right) ✓
Peak! ✓
Example 2: nums = [1, 2, 1, 3, 5, 6, 4]
Initial: left = 0, right = 6
[1, 2, 1, 3, 5, 6, 4]
↑ ↑
left right
Iteration 1:
mid = 3
nums[3] = 3, nums[4] = 5
3 < 5 (ascending)
Peak on right
left = 4
[1, 2, 1, 3, 5, 6, 4]
↑ ↑
left right
Iteration 2:
mid = 5
nums[5] = 6, nums[6] = 4
6 > 4 (descending)
Peak at mid or left
right = 5
[1, 2, 1, 3, 5, 6, 4]
↑ ↑
left right
Iteration 3:
mid = 4
nums[4] = 5, nums[5] = 6
5 < 6 (ascending)
Peak on right
left = 5
[1, 2, 1, 3, 5, 6, 4]
↑
left/right
Loop ends
return 5 ✓
Verification: nums[5] = 6
6 > 5 (left) ✓
6 > 4 (right) ✓
Peak! ✓
Example 3: nums = [1] (single element)
Initial: left = 0, right = 0
Loop condition: left < right
0 < 0? False
Loop doesn't run
return 0 ✓
Single element is always a peak!
Example 4: nums = [1, 2, 3, 4, 5] (increasing)
Initial: left = 0, right = 4
Iteration 1:
mid = 2
nums[2] = 3, nums[3] = 4
3 < 4, go right
left = 3
Iteration 2:
mid = 3
nums[3] = 4, nums[4] = 5
4 < 5, go right
left = 4
Loop ends (left == right == 4)
return 4 ✓
nums[4] = 5 > nums[3] = 4 ✓
nums[4] = 5 > -∞ (right boundary) ✓
Peak at right edge!
Example 5: nums = [5, 4, 3, 2, 1] (decreasing)
Initial: left = 0, right = 4
Iteration 1:
mid = 2
nums[2] = 3, nums[3] = 2
3 > 2, go left or mid
right = 2
Iteration 2:
mid = 1
nums[1] = 4, nums[2] = 3
4 > 3, go left or mid
right = 1
Iteration 3:
mid = 0
nums[0] = 5, nums[1] = 4
5 > 4, go left or mid
right = 0
Loop ends
return 0 ✓
nums[0] = 5 > -∞ (left boundary) ✓
nums[0] = 5 > nums[1] = 4 ✓
Peak at left edge!
🎯 Why This Works - Deep Dive
The Loop Condition: while (left < right)
═══════════════════════════════════════════════════════════
Similar to "Find Minimum" pattern:
Converge to single element
That element is guaranteed to be a peak
The Comparison: nums[mid] vs nums[mid + 1]
═══════════════════════════════════════════════════════════
We check the SLOPE at mid:
- Upward slope → peak ahead
- Downward slope → peak behind or here
Why compare with mid + 1 (not mid - 1)?
Consistent direction checking
Always safe (mid < right guarantees mid + 1 exists)
The Asymmetric Update:
═══════════════════════════════════════════════════════════
Ascending: left = mid + 1
mid is NOT a peak (smaller than mid+1)
Safe to exclude mid
Descending: right = mid
mid COULD be a peak
Must keep it in range
Same pattern as "Find Minimum"!
Why Peak Always Exists:
═══════════════════════════════════════════════════════════
Mathematical proof:
1. Array has at least 1 element
2. Boundaries are conceptually -∞
3. Any local maximum is a peak
Process:
Start at left edge (> -∞)
If always increasing → right edge is peak
If decreases → local max before decrease is peak
If oscillates → multiple peaks exist
At least one peak guaranteed! ✓
Time Complexity:
═══════════════════════════════════════════════════════════
Each iteration: O(1)
Search space halves: O(log n) iterations
Total: O(log n) ✓
Much better than O(n) linear search!
Why Not Compare with Both Neighbors?
// Alternative (more intuitive but same result):
if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
return mid; // Found peak
}
// Issues:
// 1. Need to handle mid == 0 edge case
// 2. Need to handle mid == n-1 edge case
// 3. More code, same complexity
// Our approach is cleaner:
// Just compare with mid + 1
// No edge case handling needed
// Converges to peak automatically
⚠️ Common Mistakes to Avoid
Mistake 1: Wrong loop condition
// ❌ WRONG
while (left <= right) {
if (nums[mid] > nums[mid + 1]) {
right = mid; // Infinite loop!
}
}
// ✓ CORRECT
while (left < right) {
if (nums[mid] > nums[mid + 1]) {
right = mid;
}
}
Mistake 2: Wrong pointer update
// ❌ WRONG - Might skip peak
if (nums[mid] > nums[mid + 1]) {
right = mid - 1; // Skip mid!
}
// ✓ CORRECT - Keep mid
if (nums[mid] > nums[mid + 1]) {
right = mid; // Mid might be peak
}
Mistake 3: Comparing with wrong neighbor
// ❌ WRONG - Need boundary checks
if (nums[mid] > nums[mid - 1]) {
// What if mid == 0? Crash!
}
// ✓ CORRECT - Always safe
if (nums[mid] < nums[mid + 1]) {
// mid + 1 always exists (mid < right)
}
Mistake 4: Returning wrong value
// ❌ WRONG
return nums[left]; // Returns value, not index
// ✓ CORRECT
return left; // Returns index
Mistake 5: Early return on found peak
// ❌ UNNECESSARY (but not wrong)
if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {
return mid; // Found peak
}
// More code, same result
// ✓ SIMPLER - Let convergence find it
// Just the ascending/descending checks
🎯 Pattern Recognition
Problem Type: Binary Search - Find Peak
Core Pattern: Slope-Based Half Elimination
When to Apply:
✓ Need to find peak element
✓ Array not fully sorted
✓ Need O(log n) time
✓ Any peak is acceptable
✓ Neighbors comparison property
Recognition Keywords:
- "Peak element"
- "Greater than neighbors"
- "Any peak"
- O(log n) complexity
- Can return any valid answer
Similar Problems:
- Find Minimum in Rotated Sorted Array (LC 153)
- Find Peak Element II (LC 1901) - 2D version
- Peak Index in Mountain Array (LC 852)
Key Difference from Other BS:
┌────────────────────────────────────────────┐
│ Classic Binary Search: │
│ - Array fully sorted │
│ - Exact target search │
│ │
│ Find Peak (This Problem): │
│ - Array not sorted │
│ - Find local maximum │
│ - Use slope to decide direction │
│ - Any valid answer works │
└────────────────────────────────────────────┘
Slope comparison is the KEY!
🧠 Interview Strategy
Step 1: "Find peak → Check slope → Binary search"
Step 2: "Compare mid with mid+1 to determine slope"
Step 3: "Ascending → peak on right; Descending → peak on left/mid"
Step 4: "Converge using while (left < right)"
Step 5: "Return left when converged"
Key Points to Mention:
- Peak always exists (boundary = -∞)
- Check slope: mid vs mid+1
- Ascending: left = mid + 1 (exclude mid)
- Descending: right = mid (keep mid)
- Loop: while (left < right)
- Return: left (index, not value)
- Time: O(log n), Space: O(1)
- Any peak is valid answer
Why This Approach?
"A peak is guaranteed to exist because the boundaries are
conceptually negative infinity. At any position, I can check
the slope by comparing nums[mid] with nums[mid+1]. If it's
ascending, a peak must exist to the right (either it keeps
going up to the edge, or it goes down creating a peak). If
it's descending, the peak is either at mid or to the left.
This lets me eliminate half the array each iteration, giving
O(log n) time."
Why Compare with mid+1?
"Comparing with mid+1 tells me the slope direction clearly.
If nums[mid] < nums[mid+1], I'm on an upward slope. If
nums[mid] > nums[mid+1], I'm on a downward slope. This is
simpler and safer than comparing with both neighbors."
📝 Quick Revision Notes
🎯 Core Concept:
Find Peak Element: Peak always exists! Check slope at mid: compare nums[mid] with nums[mid+1]. Ascending (mid < mid+1) → peak on right. Descending (mid > mid+1) → peak on left/mid. Converge with while (left < right). Return index!
⚡ Quick Implementation:
class Test {
public int findPeakElement(int[] a) {
int len = a.length;
int left = 0;
int right = len - 1;
// Same template as Find Minimum in Rotated Sorted Array (left < right and right = mid)
while (left < right) {
int mid = left + (right - left) / 2;
if(mid + 1 < len && a[mid] < a[mid + 1]) { // since they asked strictly increasing
// check right side
// go right side since there is an element greater than existing element being taken
left = mid + 1;
} else {
right = mid; // mid also can be answer
}
}
return left;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.findPeakElement(new int[] {1,2,3,1}) == 2);
System.out.println(t.findPeakElement(new int[] {1,2,1,3,5,6,4}) == 5);
System.out.println(t.findPeakElement(new int[] {1}) == 0);
System.out.println(t.findPeakElement(new int[] {1, 2}) == 1);
System.out.println(t.findPeakElement(new int[] {2, 1}) == 0);
System.out.println(t.findPeakElement(new int[] {1, 2, 3, 4, 5}) == 4);
System.out.println(t.findPeakElement(new int[] {5, 4, 3, 2, 1}) == 0);
System.out.println(t.findPeakElement(new int[] {3, 2, 1, 2, 3}) == 4);
}
}
🔑 Key Insights:
- Pattern: Find Peak via Slope Detection
- Guarantee: Peak always exists (boundary = -∞)
- Compare:
nums[mid]vsnums[mid + 1](slope) - Ascending:
left = mid + 1(peak on right) - Descending:
right = mid(peak on left or mid) - Loop:
while (left < right)(converge) - Return:
left(index, not value!) - Time: O(log n), Space: O(1)
🎪 Memory Aid:
"Check the slope! Up → go right, Down → keep mid!"
Think: "Slope decides direction, converge to peak!"
💡 The Key Insight:
At mid:
nums[mid] < nums[mid + 1]:
Ascending slope ↗
Peak on right
left = mid + 1
nums[mid] > nums[mid + 1]:
Descending slope ↘
Peak on left or at mid
right = mid
⚠️ Critical Details:
1. Loop: while (left < right) ← Not <=
2. Compare: nums[mid] vs nums[mid + 1]
3. Ascending: left = mid + 1
4. Descending: right = mid ← Not mid - 1!
5. Return: left ← Index, not value!
6. Safe: mid + 1 always exists (mid < right)
🔥 Why Peak Always Exists:
Boundaries are -∞:
nums[-1] = -∞
nums[n] = -∞
So:
First element > -∞
Last element > -∞
If increasing: last is peak
If decreasing: first is peak
If mixed: local max is peak
Always at least one peak! ✓
💡 Visual Pattern:
Ascending slope:
?
↗ (peak somewhere ahead)
mid
Descending slope:
↘ (peak at mid or behind)
mid
Check slope → decide direction!
🧪 Edge Cases
Case 1: Single element
Input: nums = [1]
Output: 0
(Always a peak)
Case 2: Two elements - increasing
Input: nums = [1, 2]
Output: 1
(Right edge is peak)
Case 3: Two elements - decreasing
Input: nums = [2, 1]
Output: 0
(Left edge is peak)
Case 4: All increasing
Input: nums = [1, 2, 3, 4, 5]
Output: 4
(Right edge is peak)
Case 5: All decreasing
Input: nums = [5, 4, 3, 2, 1]
Output: 0
(Left edge is peak)
Case 6: Multiple peaks
Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 1 or 5
(Any peak is valid)
Case 7: Valley in middle
Input: nums = [3, 2, 1, 2, 3]
Output: 0 or 4
(Peaks at edges)
All handled correctly! ✓
Related Patterns
- Find Minimum in Rotated Sorted Array (LC 153) - Similar slope logic
- Peak Index in Mountain Array (LC 852) - Simplified version
- Find Peak Element II (LC 1901) - 2D version
Happy practicing! 🎯
Note: This is a beautiful application of binary search to non-sorted arrays! The slope-based decision is elegant and powerful. Master this pattern!