📚 Table of Contents
📋 Problem Statement
Find an index that is strictly greater than its immediate neighbors. Any valid peak is acceptable.
Examples
Example 1:
Input: nums = [1,2,3,1]Output: 2
Example 2:
Input: nums = [1,2,1,3,5,6,4]Output: 1 or 5
Constraints
1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1nums[i] != nums[i+1]
🎯 Real-World Analogy
Hiking Toward a Summit
If the trail slopes upward from mid to mid+1, a peak must exist to the right. If it slopes downward or flat-left direction, a peak exists on the left side.
Binary search keeps only the side guaranteed to contain at least one summit.
💡 Key Insights
- Compare
nums[mid]andnums[mid+1]to infer slope direction. - If ascending, peak is on right side; if descending, peak is on left including mid.
- At least one peak always exists with virtual -infinity boundaries.
- Need only one peak, so logarithmic narrowing is valid.
- Loop ends when left == right, which is a peak index.
💻 Solution Approaches
Approach 1: Linear Scan
Time: O(N) | Space: O(1)
Find first drop and return previous element index.
Approach 2: Binary Search on Slope (Recommended)
Time: O(log N) | Space: O(1)
Use slope between mid and mid+1 to discard half of search space.
Python Implementation
from typing import List
def find_peak_element(nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left
JavaScript Implementation
function findPeakElement(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
🔍 Step-by-Step Walkthrough
Trace [1,2,1,3,5,6,4]:
left=0 right=6 mid=3. Compare 3 and 5 -> ascending -> left=4.
left=4 right=6 mid=5. Compare 6 and 4 -> descending -> right=5.
left=4 right=5 mid=4. Compare 5 and 6 -> ascending -> left=5.
left == right == 5. Peak index is 5.
⚡ Complexity Analysis
Time Complexity: O(log N)
- Each step removes half the interval.
- Only constant work per iteration.
Space Complexity: O(1)
- Index pointers only.
- No extra collections.
🔧 Edge Cases
- Single element array -> index 0
- Strictly increasing array -> last index peak
- Strictly decreasing array -> first index peak
- Multiple peaks -> any valid index accepted
- Length two array -> larger index between the two
🧪 Test Cases
Python
def is_peak(nums, i):
left = nums[i - 1] if i - 1 >= 0 else float('-inf')
right = nums[i + 1] if i + 1 < len(nums) else float('-inf')
return nums[i] > left and nums[i] > right
def test_find_peak_element():
i1 = find_peak_element([1,2,3,1])
assert i1 == 2
arr = [1,2,1,3,5,6,4]
i2 = find_peak_element(arr)
assert is_peak(arr, i2)
assert find_peak_element([1]) == 0
assert find_peak_element([2,1]) == 0
print("✅ all tests passed")
JavaScript
function testFindPeakElement() {
console.assert(findPeakElement([1,2,3,1]) === 2, "test 1");
const i = findPeakElement([1,2,1,3,5,6,4]);
console.assert([1,5].includes(i), "test 2");
console.assert(findPeakElement([1]) === 0, "test 3");
console.log("✅ all tests passed");
}
💼 Interview Tips
- State why a peak always exists with virtual -infinity edges.
- Explain slope-based elimination, not just code mechanics.
- Use
mid + 1safely by keeping loop conditionleft < right. - Highlight that any peak is valid output.
- Mention O(log N) follow-up and why linear scan is suboptimal.
🎓 Key Takeaways
- Slope direction is enough to decide which half still contains a peak.
- Binary search works beyond exact-value lookups.
- Careful loop invariants make this proof and implementation clean.