A peak element is an element that is strictly greater than its neighbors.
The nature of the input will be "It will be in an increasing fashion but suddenly will start to decrease at some point. That point will be pivot point".
We need to find that Pivot Point. One thing is for sure that it kinda involves sorted array.
Whenever the array is sorted, it will always involve "Binary Search".
class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length;
if(n==1)
return 0;
int low = 0, high = n-1;
while(low<high){
int mid = low + (high-low)/2;
if(mid>low && mid<high && nums[mid-1]<nums[mid] && nums[mid]>nums[mid+1])
return mid;
else if(nums[mid]<nums[mid+1])
low = mid+1;
else
high = mid-1;
}
return low;
}
}
Thanks for reading 🥰
Feel free to comment ✍️
Follow for more 🤝 && Happy Coding 🚀
If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7
Top comments (5)
One quick question.You mentioned that its gonna be in increasing
Fashion but at some pivot point it's gonna decrease so technically it's not sorted so we couldn't apply binary search but your approach implies that array is already *sorted
Agenda of the entire question is to find the "pivot" point. We are taking advantage of the fact that it(array) is increasing initially but after some point it starts to decrease. We can also use O(n) approach, by comparing with the next element. Binary search is for optimization purpose.
Yaa good idea of using advantage of increasing upto pivot,so what if the iteration crosses the pivot we can't use it right? As you see I couldn't figure out this pattern and also the "return low" statement at the end ,btw how to notice this pattern?
Could you plz elaborate your thought process? Tanuja
Thanks in advance
Perhaps I'm confusing sorted with ordered here but if the array is sorted isn't just a case of getting the max? So nuns[0] or nums[nums.length-1] depending on which order it is sorted?
But it changes order but we shouldn't change the order