Find Peak Element
Problem
Given an integer array nums, return the index of a peak element. A peak element is an element that is strictly greater than its neighbors. You may assume nums[-1] = nums[n] = -∞. The array may contain multiple peaks; return the index to any one of the peaks.
- 1 ≤ nums.length ≤ 10⁴
- −2³¹ ≤ nums[i] ≤ 2³¹ - 1
- nums[i] != nums[i + 1] for all valid i
Example
nums = [1,2,3,1]2The array has a peak at index 2 with value 3. The algorithm uses a binary search variant to efficiently locate a peak by comparing mid elements with their neighbors. Starting with l=0 and r=3, it calculates mid=1. Since nums[1] = 2 is less than nums[2] = 3, it moves l to mid+1=2. Now l=r=2, so it returns 2 as the peak index.
Approach
Straightforward Solution
A naive approach scans the array linearly to find any peak, which is O(n) time. This is inefficient for large arrays.
Core Observation
A peak is guaranteed because nums[-1] = nums[n] = -∞. At an index m, compare nums[m] with nums[m+1]. If nums[m] < nums[m+1], then some peak must exist in (m, r] because the sequence is rising at m and cannot keep rising past the right boundary (it must eventually stop rising, which creates a peak). Otherwise nums[m] > nums[m+1], so some peak must exist in [l, m]. This makes it safe to discard half the search range each iteration while keeping at least one peak inside [l, r].
Path to Optimal
The key recognition signals are 'peak element', 'neighbors', and 'return any peak'. These indicate Modified Binary Search because the problem can be framed as searching for a boundary where the slope changes from ascending to descending. By comparing nums[mid] and nums[mid+1], the algorithm decides which half contains a peak, enabling O(log n) time.
Optimal Approach
Use a binary search with pointers l and r. At each iteration, compute mid. If nums[mid] < nums[mid+1], the peak lies to the right, so move l to mid+1. Otherwise, the peak lies to the left or at mid, so move r to mid. Continue until l == r, which is the peak index.
Time
O(log n)
Each iteration halves the search space by moving either l or r, resulting in logarithmic time complexity.
Space
O(1)
Only a fixed number of variables (l, r, m) are used, so the algorithm uses constant auxiliary space.
Pattern Spotlight
Modified Binary Search (Slope-Based Search for Peak)
When searching for a peak or boundary in an array where the property depends on neighbors, compare mid with mid+1 to determine the slope direction and discard the half that cannot contain a peak, guaranteeing logarithmic time.
Solution
| 1 | class Solution: |
| 2 | def findPeakElement(self, nums: List[int]) -> int: |
| 3 | l, r = 0, len(nums) - 1 |
| 4 | |
| 5 | while l < r: |
| 6 | m = l + (r - l) // 2 |
| 7 | |
| 8 | if nums[m] < nums[m + 1]: |
| 9 | l = m + 1 |
| 10 | else: |
| 11 | r = m |
| 12 | |
| 13 | return l |
Step-by-Step Solution
Initialize Search Boundaries to Cover Entire Array
| 3 | l, r = 0, len(nums) - 1 |
Objective
To set the initial left and right pointers to the start and end of the array, defining the search space.
Key Insight
Starting with l=0 and r=len(nums)-1 covers the entire array. This ensures the binary search explores all possible peak locations. The pointers represent the current candidate range where a peak must exist.
Interview Quick-Check
Core Logic
Setting l and r to the array boundaries initializes the binary search over the full input.
State & Boundaries
The search space is inclusive of both l and r, and the loop continues while l < r to ensure convergence.
Iteratively Narrow Search Space by Comparing Midpoint with Next Element
| 5 | while l < r: |
| 6 | m = l + (r - l) // 2 |
| 8 | if nums[m] < nums[m + 1]: |
| 9 | l = m + 1 |
| 10 | else: |
| 11 | r = m |
Objective
To use the slope between nums[mid] and nums[mid+1] to decide which half of the array contains a peak.
Key Insight
If nums[mid] < nums[mid+1], the slope is ascending, so the peak must be to the right of mid. Moving l to mid+1 discards the left half safely. Otherwise, the peak is at mid or to the left, so moving r to mid narrows the search to the left half. This logic exploits the guarantee of a peak's existence and the array's boundary conditions.
Interview Quick-Check
Core Logic
Comparing nums[mid] and nums[mid+1] determines the slope direction, guiding the binary search to discard the half without a peak.
State & Boundaries
The loop condition l < r ensures the search space shrinks until l == r, the peak index.
Common Pitfalls & Bugs
Using mid = (l + r) // 2 without careful boundary checks can cause infinite loops or index errors; using mid + 1 safely accesses the next element.
Return the Peak Index After Convergence
| 13 | return l |
Objective
To return the index where the search pointers converge, which is guaranteed to be a peak.
Key Insight
When l == r, the search space has been narrowed to a single element that satisfies the peak condition. Returning l provides a valid peak index as per the problem's requirements.
Interview Quick-Check
Core Logic
Returning l after the loop terminates returns the index of a peak element found by the binary search.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if nums[m] < nums[m + 1]:Compare the middle element with its immediate right neighbor to determine slope direction.
This comparison is the critical decision point that enables discarding half the search space safely by identifying the slope direction, ensuring logarithmic time complexity.
return lReturn the index where the pointers converge, representing a peak element.
Returning l at convergence is correct because the binary search invariant ensures this index corresponds to a peak element, fulfilling the problem's requirement.
l = m + 1Move the left pointer to mid + 1 if the slope is ascending.
If nums[m] < nums[m+1], the peak must lie to the right, so advancing l to m+1 discards the left half without missing any peak.
r = mMove the right pointer to m to keep the candidate peak range in [l, m].
When nums[m] > nums[m+1], a peak must exist in [l, m], so setting r = m preserves the invariant that a peak remains in the inclusive range while shrinking the search space.
l, r = 0, len(nums) - 1Initialize left and right pointers to the start and end of the array.
Setting l=0 and r=len(nums)-1 defines the full search space for the binary search, ensuring all elements are considered as potential peaks.
m = l + (r - l) // 2Calculate the midpoint of the current search space to avoid overflow.
Using m = l + (r - l) // 2 prevents potential integer overflow and correctly identifies the middle index for binary search partitioning.
while l < r:Begin the binary search loop, continuing while the search space has more than one element.
The condition l < r ensures the loop runs until the search space is reduced to a single element, guaranteeing convergence to a peak.
else:Enter the left-half search branch when nums[m] is not less than nums[m+1].
This line selects the non-rising-slope branch (nums[m] > nums[m+1]), which implies a peak exists in the left side including m. The actual range update happens on the next line.
Test Your Understanding
Why does comparing nums[mid] with nums[mid+1] allow us to discard half the search space safely?
Because if nums[mid] < nums[mid+1], the slope is ascending, so a peak must exist to the right; if nums[mid] >= nums[mid+1], the slope is descending or flat, so a peak exists at mid or to the left. This guarantees that discarding the other half does not exclude any peak.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct Find Peak Element from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Find Peak Element drill