Watch 10 video solutions for Find Peak Element, a medium level problem involving Array, Binary Search. This walkthrough by take U forward has 420,325 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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-231 <= nums[i] <= 231 - 1nums[i] != nums[i + 1] for all valid i.Problem Overview: You are given an integer array where a peak element is strictly greater than its neighbors. The task is to return the index of any peak element. The array may contain multiple peaks, and you can return any valid one. The challenge is to do better than scanning the entire array.
The problem sits at the intersection of array traversal and binary search. The key observation: if an element is smaller than its right neighbor, a peak must exist on the right side. If it is smaller than the left neighbor, a peak must exist on the left side. This property allows logarithmic search.
Approach 1: Linear Scan (Simpler but Not Optimal) (Time: O(n), Space: O(1))
The most direct solution iterates through the array and checks each element against its neighbors. For index i, verify whether nums[i] > nums[i-1] and nums[i] > nums[i+1]. Edge elements only need one comparison because the array boundaries are treated as negative infinity.
This approach performs a single pass through the array. The first element greater than its next neighbor or the first descending point guarantees a peak. Although the logic is simple and easy to implement, it requires examining up to all n elements, resulting in O(n) time complexity and O(1) space.
Approach 2: Binary Search Approach (Time: O(log n), Space: O(1))
The optimal solution uses binary search by analyzing the slope between adjacent elements. Pick a midpoint mid and compare nums[mid] with nums[mid + 1]. If the right neighbor is larger, the array is ascending at that point, so a peak must exist in the right half. Otherwise, a peak exists in the left half including mid.
This works because any increasing slope eventually leads to a peak, and any decreasing slope already passed one. Each comparison eliminates half of the search space. The algorithm continues shrinking the range until left == right, which points to a peak index.
This approach never needs extra memory and performs at most log2(n) iterations, giving O(log n) time and O(1) space. It demonstrates how binary search can work on unsorted arrays when a structural property (like slope direction) guarantees a solution.
Recommended for interviews: Interviewers typically expect the binary search solution. The linear scan shows you understand the peak definition, but the O(log n) approach proves you can recognize patterns that allow binary search without a fully sorted array. Explaining the slope insight clearly is usually the key step during interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | When simplicity matters or when introducing the concept before optimizing |
| Binary Search | O(log n) | O(1) | Preferred for interviews and large arrays where logarithmic search is expected |