Find Peak Element - Java Coding Interview Guide
Learn how to solve the Find Peak Element problem using Binary Search in Java with detailed explanation, intuition, dry run, optimized solution, production use cases, complexity analysis, common mistakes, and interview questions.
Find Peak Element
Java Coding Interview Track
Binary Search — Lesson 04
Ordered Lessons
| # | Lesson |
|---|---|
| 01 | Binary Search |
| 02 | Search Insert Position |
| 03 | First Last Position |
| 04 | Find Peak Element ← |
| 05 | Search Rotated Array |
| 06 | Binary Search Interview |
Problem Statement
A peak element is an element that is strictly greater than its adjacent elements.
Given an integer array nums, return the index of any peak element.
You may assume:
nums[i] != nums[i + 1]- You can imagine
nums[-1] = -∞ - You can imagine
nums[n] = -∞
The solution must run in O(log n) time.
Example 1
Input
nums = [1,2,3,1]
Output
2
Peak = 3
Example 2
Input
nums = [1,2,1,3,5,6,4]
Output
5
Peak = 6
Another valid answer: 1
Understanding the Problem
Example
1 2 3 1
↑
Peak
A peak is simply higher than both neighbors.
Another example
1 3 2 5 4
↑ ↑
Two Peaks
The problem accepts any one of the peaks.
Why Binary Search Works
Unlike traditional Binary Search, we are not searching for a target value.
Instead, we observe the slope.
If
nums[mid] < nums[mid+1]
we are moving uphill, meaning a peak must exist on the right.
If
nums[mid] > nums[mid+1]
we are moving downhill, meaning a peak exists on the left (possibly at mid).
This allows us to eliminate half of the search space every iteration.
Visualization
1 2 3 1
↑
Peak
---------
1 2 1 5 6 4
↑
Peak
Algorithm
left = 0
right = n-1
while(left < right)
mid
nums[mid] < nums[mid+1]
left = mid+1
else
right = mid
Return left
Dry Run
nums
1 2 3 1
Iteration 1
left = 0
right = 3
mid = 1
nums[mid] = 2
nums[mid+1] = 3
Go Right
left = 2
Iteration 2
left = 2
right = 3
mid = 2
nums[mid] = 3
nums[mid+1] = 1
Go Left
right = 2
Loop Ends
left = right = 2
Answer
2
Java Solution
public class FindPeakElement {
public static int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
public static void main(String[] args) {
int[] nums = {1,2,3,1};
System.out.println(findPeakElement(nums));
}
}
Complexity Analysis
| Operation | Complexity |
|---|---|
| Time | O(log n) |
| Space | O(1) |
Why Compare with mid + 1?
The comparison tells us the direction of the slope.
2 < 5
Increasing
Peak →
-------------------
5 > 2
Decreasing
Peak ←
This guarantees that one side always contains a peak.
Visualization of Slope
graph TD
Increasing["Increasing"] --> N_1_2_3_4_5["1 2 3 4 5"]
N_1_2_3_4_5["1 2 3 4 5"] --> Peak_Right["Peak Right"]
Peak_Right["Peak Right"] --> N_["-----------------"]
N_["-----------------"] --> Decreasing["Decreasing"]
Decreasing["Decreasing"] --> N_5_4_3_2_1["5 4 3 2 1"]
N_5_4_3_2_1["5 4 3 2 1"] --> N_1["←"]
N_1["←"] --> Peak_Left["Peak Left"]
Production Use Cases
Sensor Data
Detect the highest measurement in a local region.
Stock Analysis
Identify local price peaks for technical analysis.
Signal Processing
Detect peaks in ECG, EEG, or audio signals.
Image Processing
Find intensity peaks in image histograms.
Traffic Monitoring
Identify peak traffic periods from sorted measurements.
Performance Monitoring
Detect CPU or memory usage spikes.
Common Mistakes
Using Linear Search
Works correctly but takes
O(n)
instead of
O(log n)
Using left <= right
Incorrect.
The optimized solution should use
while(left < right)
Accessing mid - 1
Not required.
Only compare
nums[mid]
nums[mid+1]
which avoids boundary issues.
Forgetting Multiple Peaks
Any valid peak index is acceptable.
Interview Tips
Mention these observations:
- Binary Search works because one side always contains a peak.
- We are searching based on the slope, not a target value.
- There may be multiple valid answers.
- The algorithm guarantees logarithmic complexity.
Related Problems
- Binary Search
- Peak Index in Mountain Array
- Search in Rotated Sorted Array
- Local Minimum
- Maximum in Bitonic Array
- Binary Search on Answer
Interview Questions
1. What is a peak element?
Answer
A peak element is an element that is greater than both of its adjacent elements.
2. Why can Binary Search solve this problem?
Answer
By comparing nums[mid] and nums[mid + 1], we determine whether we are moving uphill or downhill. A peak must exist in the chosen half, allowing us to discard the other half.
3. What is the time complexity?
Answer
O(log n) because the search space is reduced by half during each iteration.
4. What is the space complexity?
Answer
O(1) because the iterative solution uses constant extra space.
5. Why compare only with mid + 1?
Answer
The comparison is enough to determine the direction of the slope and guarantees that one side contains a peak.
6. Can there be multiple peaks?
Answer
Yes. The problem requires returning the index of any one valid peak.
7. What happens if the array has only one element?
Answer
That single element is considered a peak because its virtual neighbors are -∞.
8. Why does the loop use left < right?
Answer
The search ends when both pointers converge to the same index, which is the peak.
9. Where is this concept used in production?
Answer
Signal processing, stock market analysis, sensor monitoring, image processing, traffic analytics, and performance monitoring.
10. What problems are related to this pattern?
Answer
Peak Index in Mountain Array, Maximum in Bitonic Array, Local Minimum, Search in Rotated Array, and Binary Search on Answer.
Quick Revision
| Concept | Value |
|---|---|
| Pattern | Binary Search on Slope |
| Target Search | No |
| Compare | nums[mid] vs nums[mid + 1] |
| Time Complexity | O(log n) |
| Space Complexity | O(1) |
| Multiple Answers | Yes |
| Interview Frequency | ⭐⭐⭐⭐☆ |
Key Takeaways
- Find Peak Element is a classic Binary Search variation based on slope analysis, not target searching.
- Comparing adjacent elements helps determine which half must contain a peak.
- The algorithm guarantees O(log n) time and O(1) space.
- Multiple peak elements may exist, and returning any valid peak is acceptable.
- This pattern forms the basis for solving Mountain Array, Bitonic Array, and other optimization problems using Binary Search.