Find Peak Element — Solution in Python, Java & C++
Find Peak Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Yahoo.
Find Peak Element is a medium coding problem on arrays and binary search, asked in Yahoo interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search
- Asked at: Yahoo
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A peak element is strictly greater than its neighbors. Given an array nums that strictly increases and then strictly decreases (so it has exactly one peak), return the index of the peak in O(log n) time.
(Either part may be empty: a strictly increasing or strictly decreasing array peaks at an end.)
Example 1
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is the peak, at index 2.
Example 2
Input: nums = [1,2,1,0,-1]
Output: 1
Constraints
1 <= nums.length <= 30-1000 <= nums[i] <= 1000nums strictly increases then strictly decreases (exactly one peak).
Hints for Find Peak Element
Hint 1
Compare nums[mid] with nums[mid+1]: rising means the peak is to the right.
Hint 2
Falling means the peak is at mid or to the left.
How to solve Find Peak Element
You do not need to see the whole array to find the peak — you only need to know which way the slope runs. Comparing nums[mid] with its right neighbour tells you that: still rising means the peak is further right, already falling means the peak is at mid or to its left. Halve the range on that answer alone.
Approach
- Keep a range
[lo, hi]and loop whilelo < hi. - Take
mid = lo + (hi - lo) / 2, which is always strictly less thanhi, somid + 1is safe to read. - If
nums[mid] < nums[mid + 1]you are on the rising side — the peak is strictly right, solo = mid + 1. - Otherwise you are at or past the summit — set
hi = mid, keepingmidas a candidate. - When the range collapses,
lois the peak's index.
Why it works
The array rises strictly and then falls strictly, so the comparison with the right neighbour is a clean test of which side of the summit mid sits on. If it is rising, every index at or left of mid is also below the peak, so discarding them is safe; if falling, everything right of mid is below nums[mid], so the peak is at mid or earlier. The invariant "the peak is in [lo, hi]" survives both branches, and the range always shrinks.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
- Use
hi = mid, notmid - 1— a falling comparison does not rulemidout. - The loop must be
lo < hi; withlo <= hiandhi = midit never ends. mid + 1is only in bounds because the loop guaranteesmid < hi; computingmidwith the upper half would break that.- A strictly increasing or strictly decreasing array is allowed — the peak is then at an end, which this handles without special cases.
Reference solution
Python
from typing import List
def findPeakElement(nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1
else:
hi = mid
return loJava
public static 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]) lo = mid + 1;
else hi = mid;
}
return lo;
}C++
int findPeakElement(vector<int>& nums) {
int lo = 0, hi = (int) nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < nums[mid + 1]) lo = mid + 1;
else hi = mid;
}
return lo;
}JavaScript
var findPeakElement = function(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < nums[mid + 1]) lo = mid + 1;
else hi = mid;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search