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.
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.
This C code performs a binary search on the array 'nums'. We start from the whole array and keep reducing the search space. If nums[mid] is greater than nums[mid+1], we search in the left half since a peak might be possible on the left. Otherwise, we search in the right half. This continues until 'left' equals 'right' and we find the peak.
Time Complexity: O(log n), Space Complexity: O(1)
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.
In this approach, we first handle edge cases for the start and end of the array. Then, we iterate through the array to find the first element greater than its neighbors. While the time complexity is O(n), it provides a straightforward implementation.
Time Complexity: O(n), Space Complexity: O(1)
We define the left boundary of binary search as left=0 and the right boundary as right=n-1, where n is the length of the array. In each step of binary search, we find the middle element mid of the current interval, and compare the values of mid and its right neighbor mid+1:
mid is greater than the value of mid+1, there exists a peak element on the left side, and we update the right boundary right to mid.left to mid+1.left is equal to the right boundary right, we have found the peak element of the array.The time complexity is O(log n), where n is the length of the array nums. Each step of binary search can reduce the search interval by half, so the time complexity is O(log n). The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time Complexity: O(log n), Space Complexity: O(1) |
| Linear Scan (Simpler but Not Optimal) | Time Complexity: O(n), Space Complexity: O(1) |
| Binary Search | — |
| 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 |
BS-9. Find Peak Element • take U forward • 420,325 views views
Watch 9 more video solutions →Practice Find Peak Element with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor