162. Find Peak Element
Problem Description
The problem presents an integer array called nums
which is 0-indexed. We are tasked with finding an index of a peak element. A peak element is defined as an element that is strictly greater than its neighboring elements. Here the term "strictly" means that the peak element must be greater than its neighbors, not equal to them.
Furthermore, the problem scenario extends the array conceptually, so that if you look at the start or end of the array, it's as if there's an invisible -∞
to the left of the first element and to the right of the last element. This means that if the first or last element is greater than their one real neighbor, they also count as peak elements.
We're also given a constraint on the time complexity: the solution needs to run in O(log n)
time, which implies that a simple linear scan of the array is not efficient enough. We need to use an algorithm that repeatedly divides the array into smaller segments—binary search is an example of such an algorithm.
Intuition
Given the requirement to complete the task in O(log n)
time, we must discard a linear scan approach that would take O(n)
time. Instead, we adopt a binary search method due to its logarithmic time complexity, which fits our constraint.
Binary search is a technique often used for searching a sorted array by repeatedly dividing the search interval in half. Although in this case the entire array isn't sorted, we can still use binary search because of the following key insight: if an element is not a peak (meaning it's less than either of its neighbors), then a peak must exist to the side of the greater neighbor.
The reason this works is because of our -∞
bounds at both ends of the array. We imagine a slope up from -∞
to a non-peak element and then down from the non-peak element towards -∞
. Somewhere on that rising or falling slope there must be a peak, which is a local maximum.
So in our modified binary search, instead of looking for a specific value, we look for any peak as follows:
- We take the middle element of the current interval and compare it with its right neighbor.
- If the middle element is greater than its right neighbor, we've found a descending slope, and there must be a peak to the left. Hence, we restrict our search to the left half of the current interval.
- If the middle element is less than its right neighbor, we've found an ascending slope, and a peak exists to the right. We then do our next search on the right half.
- We continue this process of narrowing down our search interval by half until we've isolated a peak element.
This binary search on a wave-like array ensures we find a peak in O(log n)
time, satisfying the problem's constraints.
Learn more about Binary Search patterns.
Solution Approach
The solution leverages a binary search algorithm, which is ideal for situations where we need to minimize the time complexity to O(log n)
. The essence of binary search in this context is to reduce the search space by half after each comparison, making it much faster than a linear approach.
Here's a step-by-step explanation of the implementation:
-
We initialize two pointers,
left
andright
, which represent the boundaries of our current search interval.left
is set to0
, andright
is set to the length of the array minus one (len(nums) - 1
). -
We enter a while loop that continues as long as
left
is less thanright
, ensuring that we are still considering a range of possible positions for a peak element. -
Inside the loop, we calculate the midpoint of the current search interval as
mid = (left + right) >> 1
. The>> 1
operation is a bitwise shift to the right by 1 bit, which is equivalent to dividing by two, but it's often faster. -
We then compare the element at the
mid
position with the element immediately to its right (nums[mid + 1]
). -
If
nums[mid]
is greater thannums[mid + 1]
, the peak must be atmid
or to the left ofmid
. Thus, we setright
tomid
, effectively narrowing the search interval to the left half. -
On the other hand, if
nums[mid]
is less than or equal tonums[mid + 1]
, then a peak lies to the right. Thus, we setleft
tomid + 1
, narrowing the search interval to the right half. -
The loop continues, halving the search space each time, until
left
equalsright
. At this point, we have found the peak because it means thatnums[left]
cannot be smaller than both its neighbors (as per thenums[-1] = nums[n] = -∞
rule). -
We exit the loop and return
left
, which is the index of the peak element.
This approach guarantees finding a peak, if not the highest peak, in logarithmic time.
Here's the code snippet that follows this approach:
1class Solution:
2 def findPeakElement(self, nums: List[int]) -> int:
3 left, right = 0, len(nums) - 1
4 while left < right:
5 mid = (left + right) >> 1
6 if nums[mid] > nums[mid + 1]:
7 right = mid
8 else:
9 left = mid + 1
10 return left
The simplicity of binary search in conjunction with the described logic yields an efficient and elegant solution for finding a peak element.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through the solution with a small example.
Suppose our input array nums
is [1, 2, 3, 1]
. We want to find an index of a peak element.
Initial Setup
- The initial value of
left
is0
. - The initial value of
right
islen(nums) - 1
, which is3
.
Iteration 1
- Calculate the midpoint:
mid = (left + right) >> 1
which is(0 + 3) >> 1 = 1
. - Compare
nums[mid]
andnums[mid + 1]
:nums[1]
is2
, andnums[2]
is3
. - Since
2
is less than3
, we are on an ascending slope. We should move right. - Update
left
tomid + 1
:left
becomes2
.
Iteration 2
left
is now2
andright
is3
.- Calculate the new midpoint:
mid = (left + right) >> 1
which is(2 + 3) >> 1 = 2
. - Compare
nums[mid]
andnums[mid + 1]
:nums[2]
is3
, andnums[3]
is1
. - Since
3
is greater than1
, we're on a descending slope. We should move left. - Update
right
tomid
:right
becomes2
.
Conclusion
- The loop ends when
left
equalsright
, which is now the case (left
andright
are both2
). - Therefore, we have found our peak at index
2
where the element is3
, and it is greater than both its neighbors (where the neighbor on the right is1
, and the neighbor on the left is2
, and conceptually-∞
on both ends).
Thus, the index 2
is returned.
Using this approach with the given example, we can see how the binary search algorithm rapidly narrows down the search to find the peak element, satisfying the O(log n)
time complexity constraint.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findPeakElement(self, nums: List[int]) -> int:
5 # Initialize the start and end pointers.
6 start, end = 0, len(nums) - 1
7
8 # Binary search to find the peak element.
9 while start < end:
10 # Find the middle index.
11 mid = (start + end) // 2
12
13 # If the middle element is greater than its next element,
14 # it means a peak element is on the left side(inclusive of mid).
15 if nums[mid] > nums[mid + 1]:
16 end = mid
17 # Otherwise, the peak is in the right half of the array.
18 else:
19 start = mid + 1
20
21 # When start and end pointers meet, we've found a peak element.
22 return start
23
1class Solution {
2 public int findPeakElement(int[] nums) {
3 int left = 0; // Initialize the left boundary of the search space
4 int right = nums.length - 1; // Initialize the right boundary of the search space
5
6 // Continue the loop until the search space is reduced to one element
7 while (left < right) {
8 // Calculate the middle index of the current search space
9 int mid = left + (right - left) / 2;
10
11 // If the middle element is greater than its next element, then a peak must be to the left (including mid)
12 if (nums[mid] > nums[mid + 1]) {
13 // Narrow the search space to the left half
14 right = mid;
15 } else {
16 // Otherwise, the peak exists in the right half (excluding mid)
17 // Narrow the search space to the right half
18 left = mid + 1;
19 }
20 }
21
22 // When left == right, we have found the peak element's index, return it
23 return left;
24 }
25}
26
1#include <vector> // Include vector header for using the vector container
2
3class Solution {
4public:
5 int findPeakElement(vector<int>& nums) {
6 // Initialize the left and right pointers
7 int left = 0;
8 int right = nums.size() - 1;
9
10 // Perform binary search
11 while (left < right) {
12 // Find the middle index
13 // Using (left + (right - left) / 2) avoids potential overflow of integer addition
14 int mid = left + (right - left) / 2;
15
16 // If the middle element is greater than the next element,
17 // the peak must be in the left half (including mid)
18 if (nums[mid] > nums[mid + 1]) {
19 right = mid;
20 } else {
21 // If the middle element is smaller than the next element,
22 // the peak must be in the right half (excluding mid)
23 left = mid + 1;
24 }
25 }
26 // At the end of the loop, left == right, which points to the peak element
27 return left;
28 }
29};
30
1function findPeakElement(nums: number[]): number {
2 // Initialize the search boundaries to the start and end of the array
3 let leftBoundary: number = 0;
4 let rightBoundary: number = nums.length - 1;
5
6 // Continue searching as long as the search space contains more than one element
7 while (leftBoundary < rightBoundary) {
8 // Find the middle index using bitwise operator
9 const middleIndex: number = leftBoundary + ((rightBoundary - leftBoundary) >> 1);
10
11 // Compare the middle element to its next element
12 if (nums[middleIndex] > nums[middleIndex + 1]) {
13 // If the middle element is greater than the next element,
14 // then a peak element is in the left half (including middle)
15 rightBoundary = middleIndex;
16 } else {
17 // Otherwise, the peak element is in the right half (excluding middle)
18 leftBoundary = middleIndex + 1;
19 }
20 }
21
22 // When leftBoundary equals rightBoundary, we found the peak element.
23 // Return its index.
24 return leftBoundary;
25}
26
Time and Space Complexity
The time complexity of the provided algorithm is O(log n)
, where n
is the length of the input array nums
. The algorithm uses a binary search approach, whereby at each step, it halves the search space. This halving continues until the peak element is found, requiring at most log2(n)
iterations to converge on a single element.
The space complexity of the algorithm is O(1)
as it only uses a constant amount of extra space. The variables left
, right
, and mid
, along with a few others for storing intermediate results, do not vary with the size of the input array nums
, ensuring that the space used remains fixed.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.