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 receive an integer array nums 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 accessing outside the array is treated as negative infinity, which guarantees at least one peak exists.
Approach 1: Linear Scan (O(n) time, O(1) space)
The most direct strategy is to iterate through the array and check whether the current element is greater than its adjacent elements. For index i, verify nums[i] > nums[i-1] and nums[i] > nums[i+1]. Edge cases are handled by treating missing neighbors as negative infinity, so the first or last element can also be a peak. The algorithm simply scans left to right and returns the first peak encountered. This approach uses constant extra memory and is easy to implement, but it requires examining every element in the worst case.
This method is useful when simplicity matters more than performance or when the array size is small. It demonstrates a clear understanding of the peak definition but does not take advantage of the structure of the problem.
Approach 2: Binary Search Approach (O(log n) time, O(1) space)
The optimal solution applies binary search to the array. Instead of looking for a specific value, the search uses the slope between adjacent elements to determine where a peak must exist. At each step, compare nums[mid] with nums[mid + 1]. If nums[mid] > nums[mid + 1], the peak lies on the left side (including mid) because the sequence is descending. Otherwise, the peak must exist on the right side because the sequence is ascending.
This observation works because any ascending slope must eventually lead to a peak, and any descending slope means a peak already exists behind it. Repeatedly narrowing the search interval halves the remaining elements each iteration, giving O(log n) time complexity with constant space.
The approach treats the array like a landscape of slopes and peaks rather than a collection of values. It leverages properties of arrays and the divide‑and‑conquer nature of binary search to locate a valid peak efficiently without scanning the entire input.
Recommended for interviews: Interviewers expect the binary search solution. The linear scan proves you understand the peak definition and boundary cases, but it runs in O(n). The binary search approach reduces the complexity to O(log n) and demonstrates strong algorithmic reasoning. Explaining the slope observation—why moving toward the larger neighbor guarantees a peak—usually separates a solid solution from a great one.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1)
| 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) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Good for quick implementation or very small arrays where simplicity matters more than performance |
| Binary Search | O(log n) | O(1) | Preferred interview solution when the array is accessible by index and logarithmic performance is required |
BS-9. Find Peak Element • take U forward • 261,178 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