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.In #162 Find Peak Element, the goal is to locate an index where the element is greater than its neighbors. A simple observation is that a peak always exists because the array edges can act as boundaries. While a linear scan can check each element against its neighbors, a more efficient approach uses Binary Search.
The key idea is to compare the middle element with its next neighbor. If nums[mid] > nums[mid+1], a peak must lie on the left side (including mid). Otherwise, the peak lies on the right side. By repeatedly narrowing the search space, we move toward a peak without scanning the entire array.
This strategy works because the array behaves like a sequence of slopes. Binary search reduces the search range at each step, achieving O(log n) time with O(1) extra space, making it the optimal interview-friendly solution.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Linear Scan | O(n) | O(1) |
| Binary Search | O(log n) | O(1) |
take U forward
The binary search approach is used to achieve the O(log n) time complexity. Binary search leverages the idea that if an element is not a peak and is less than its right neighbor, then a peak must exist on the right half of the array. Similarly, if it is less than its left neighbor, a peak must exist on the left half of the array. Thus, we keep narrowing down the search window until we find a peak.
Time Complexity: O(log n), Space Complexity: O(1)
1function findPeakElement(nums) {
2 let left = 0, right = nums.length - 1;
3 while (left < right) {
4
This JavaScript solution uses binary search logic in a similar fashion to other implementations. We utilize Math.floor for dividing by 2 to ensure we get a proper mid index, and adjust the search bounds based on comparisons.
Though not adhering to the O(log n) requirement, a linear scan is straightforward. It involves checking each element to see if it is a peak element, which can serve as a quick solution, but not fulfilling the constraints in a theoretical context. Practically, it can be used in scenarios where constraints are more relaxed or strictly linear approaches are preferred.
Time Complexity: O(n), Space Complexity: O(1)
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations frequently appear in FAANG-style interviews. It tests understanding of binary search patterns, edge cases, and reasoning about array properties rather than simple element lookup.
The problem primarily uses arrays since the elements are stored in a sequential structure. Binary search logic is applied directly on the array indices without requiring additional data structures.
Binary search works because if the current element is smaller than the next one, the slope is increasing and a peak must exist on the right side. If it is larger, a peak must exist on the left side. This property guarantees a peak within the chosen half.
The optimal approach uses binary search. By comparing the middle element with its neighbor, you can determine which side must contain a peak and shrink the search range. This reduces the time complexity to O(log n).
This Python solution iterates over the list from the second to the second-last element checking if they qualify as a peak. The linear scan makes this a practical yet less optimal choice for peak finding.