Problem:
Given an integer array return the index of any peak element in it.
Find a solution in O(logn) time.
A peak element is an element which is greater than its neighbors.
Its neighbors are the immediate elements to its left and right.
you can return any peak element.
So for example , if the input is :
[1,2,1,3,2,5]
We can return either the index 1 or the index 3 because :
At index 1 we have the element 2 which is greater than its left and right neighbors (both 1)
At index 3 we have the element 3 which is also greater than its neighbors ( 1 and 2)
Assumptions:
- For the first element in the array there is no left neighbor , so you can consider it as greater than its left neighbor.
- Similarly for the last element in the array there is no right neighbor , so you can consider it greater than its right neighbor.
Try out the solution here:
https://leetcode.com/problems/find-peak-element/
Solution:
The brute force approach would be to scan each element and check its neighbors . The moment you find a peak return it. This will take O(n) time complexity.
Here is the code:
class Solution {
public int findPeakElement(int[] nums) {
boolean greaterThanPrevious,greaterThanNext;
for(int i= 0;i<nums.length;i++){
if(i == 0 ) {
greaterThanPrevious = true;
}
else{
greaterThanPrevious = nums[i] > nums[i-1];
}
if(i == nums.length - 1){
greaterThanNext = true;
}else{
greaterThanNext = nums[i] > nums[i+1];
}
if(greaterThanPrevious && greaterThanNext){
return i;
}
}
return -1;
}
}
We can do better than this even in O(n) time complexity.
Notice that no matter what the values of the elements in the array are , you can always find a peak element!
Let’s consider the three possibilities:
All the elements are in ascending order:
For example , consider the array:
[1,2,3,4,5]
In this case we still have a peak element which is the last element 5.
So if elements are in ascending order , then you have to keep moving along the array until you reach the last element.
All the elements are in descending order:
For example , consider the array:
[5,4,3,2,1]
In this case we don’t have to move at all , just return the first element which is the peak.
So if elements are in descending order , don’t move along the array , just return the first element.
The elements are not sorted:
For example consider the array:
[1,5,3,2,8,4]
In this case you will have at least one peak between the first and the last element of the array.
As you see there are two peaks 5 and 8 at indices 1 and 4 respectively.
You can find any of the peak.
Let’s say we want to find the first peak 5.
All you have to do is keep moving along the array if the current element is less than the next element.
The moment the current element is greater than the next element you return that index.
So you just need to check one condition in your code as you move along the array:
If next element is greater than the current element return the index.
You don’t have to bother about checking for the other condition because you will keep moving along the array in that case.
Here is the code:
class Solution {
public int findPeakElement(int[] nums) {
for(int i= 0;i<nums.length - 1;i++){
if(nums[i] > nums[i+1]) return i;
}
return nums.length -1;
}
}
Since we check for the next element of each element , we will iterate only till the last but one element.
If we don’t find any peak within this range that means we are in an ascending slope so the last element is the peak and we return it .
This approach though much simpler and elegant still has time complexity O(n).
We can improve this time complexity through binary search.
Using Binary Search recursively:
In this approach we choose the middle element.
And then we check for the same condition which we previously checked.
If the current element is greater than the next element then it means we are in a descending slope so the peak is either the current element or some element before it, so will branch left and search only in the left half recursively.
If the current element is lesser than the next element then it means we are in an ascending slope so the peak is definitely not the current element so we branch right and search only in the right half recursively.
If there is only one element left then we have reached the peak and return that element
Here is the code:
class Solution {
public int findPeakElement(int[] nums) {
return search(nums,0,nums.length-1);
}
public int search(int[] nums,int l,int r){
if(l==r) return l;
int mid = (l+r)/2;
if(nums[mid] > nums[mid+1]){
return search(nums,l,mid);
}else{
return search(nums,mid+1,r);
}
}
}
The time complexity is O(log n ) since we branch left or right at each stage.
Space complexity is also O(log n) since recursion uses a stack internally for each recursive call.
Using Binary Search and Iteration:
We can implement the same logic that we used in recursion using iteration.
Here is the code for that:
class Solution {
public int findPeakElement(int[] nums) {
int l = 0;
int r = nums.length -1;
while(l!= r){
int mid = (l+r)/2;
if(nums[mid] > nums[mid+1]){
r = mid;
}else{
l = mid+1;
}
}
return l;
}
}
Here we just change the left and middle pointers according to whether we are in an ascending slope or a descending slope.
Time complexity is the same as before.
Space complexity is O(1) since we don’t use any extra memory.
That’s it!
Leave a Reply