BS-9. Find Peak Element
ฝัง
- เผยแพร่เมื่อ 15 ก.ย. 2024
- Problem Link: bit.ly/3BEDvZC
Notes/C++/Java/Python codes: takeuforward.o...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/take...
0:00 Introduction of Course
![[LIVE] : ONE ลุมพินี 79 | คู่เอก "ก้องชัย vs อาเมียร์"](http://i.ytimg.com/vi/WfPSA1A0NHc/mqdefault.jpg)
Sorry for the delay :( But I had a product launch, for which I had to spend most of my time in the office. I am back, will try to come with 1/2 videos daily now
Thank you so much sir 🙏
Sir first take rest whenever you have free time then post sir 🥲
Thankyou so much bhaiya for all videos ...🙏🙏❤️❤️
Your content is >>>> whole TH-cam
Understood
Was trying this for the past 2 days, couldn't solve it. Took 1 day break came back at it again with a fresh mind, could solve it in one go by myself. Thanks, your series instills such confidence in me always.
no one asked
@@OrderEmperor 😂 ok bro.
@@OrderEmperor no one asked nested(no one asked if no one asked or not)
@@arunm619 fair enough
@@paraskashyap7362 calling in return statement (recursion)no one asked if no one asked or not that no one asked :----) *without breaking condition
NO ONE CAN TEACH LIKE STRIVER, HE GIVES HIS 100% to his lectures. he want to teach , he compleltly go into the state of teaching , like with full FOCUS & DEDICATION . he enjoy to teach .
and all of this FREE OF COST , LEGEND AKA RAJ VIKRAMDITYA BHAIYA (STRIVER BHAI OP )
❤
the best about this video was the thinking process of how to arrive from linear to binary search in problems like this. execellent stuff.
Thanks striver I completed all your sheets , like twice , they boost my confidence , before watching your solution , i try every question for 30 mins , and regardless i am able to solve it or not , i watch your video for better understanding and side by side mark improtance of question and make notes for revision
ok
Then plz explain why should we consider binary search even though it's not
i have solved these questions already so before but still i watch every video of you because i know there will be something different which ultimately enhance my code writing or intuition skills.
Are you from DAIICT ?
Hey Striver, Your videos are pure gem. Certainly the best DSA course on the planet. Keep going. God Bless You!
Thank you ! wrote the same code without watching the video. All because of you.
the extra afforts for the edgecases is appreciated! keep working on content like this...
There are one mistake in the code when try solve problem on GFG then not pass all the cases the mistake is if(arr[n-1] >= arr[n-2]) return n-1; // use the equal sign also so that can pass all the cases and thank you so much to provide best content
yes, that is because the definition of peak is different in gfg. It says the peak can be greater than or equal to its adjacent elements (a=b) but in leetcode, the peak should be strictly greater (ab)
@@lavanyam3224 And that peak definition seems to be correct because here, it doesn't cover the case when all the elements are equal.
was waiting for these past two weeks and you showed up with another awesome explanation! Thanks dada ❤
Commenting Understood is just a simple thing for your wonderful explanation !!!
Thank you So much for your lectures Striver
it's a blessing that you are in youtube,
but on the other side , people are enjoying DSA now, hence , competition is drastically increasing too.
Didn't even look for completion time of the video!!!.....So that much interesting your videos are❤
SUPERBBBB Explanation! Thankyou so much for your great efforts.
Best explanation on the TH-cam thank you soo much....each and every second of this video is informative.
Amazing explanation Striver my man! Hats off to you for all your hard work for the community.
done with easy part of binary search from monday will start with medium part
lots of love raj bhaiya
GOD LEVEL INTUITION AND EXPLANATION STRIVERRR TYSM < 3!!!
Kaise develop hogi iss intuition from inside?😢
Bro u are the most helpful person for all engineering cse student 🧡❤
Thankyou striver, still maintaining that low=m+1 and high =m-1 thing which makes it super easy to understand!!
Your explanation is crazy. You are really doing a very good job.
Hi Striver, this was an epic explanation. Hats off!
However I think we can only check the left element of mid. If greater then eliminate right. Else eliminate left. No need for the other if condition.
class Solution {
public:
int findPeakElement(vector& arr) {
int n = arr.size();
if(n == 1) return 0;
if(arr[0] > arr[1]) return 0;
if(arr[n-1] > arr[n-2]) return n-1;
int low = 1;
int high = n - 2;
int mid;
while(low arr[mid+1] )
return mid;
//mid-1 greater than mid, peak on left,eliminate right
if(arr[mid-1] > arr[mid])
high = mid - 1;
//peak on right, eliminate left
else
low = mid + 1;
}
return mid;
}
};
he explained it by the end. it may lead to an infinite loop if there are multiple peaks.
for those who are facing problem with the if else part for the right side here is the easy way to think If the element to the right of mid is greater (arr[mid] < arr[mid + 1]), we move to the right half (since there must be a peak in that direction).
00:04 Find the peak element in an array
02:16 Identifying peak elements using the concept of infinity assumptions.
06:42 Peak element finding in a sorted array using binary search
09:03 Binary search to find peak element
13:59 Identifying peak in decreasing curve
16:22 Dealing with the cases of the first and last elements as peak elements.
20:38 Finding peak element in an array using binary search
22:54 In a decreasing curve, the mid element is greater than the right element.
27:08 Binary search can efficiently find the peak element
29:08 Algorithm to find peak element in an array
first of all it's not sorted array 06:42
how you think like that striver i mean your thought process is totally diff how can i achieve this type of thought process honestly Best DSA playlist
Filled with full confidence after watching ur videos.
Was able to do it myself 😮 thnx for building up my logical thinking ❤
Bhaiya I solved this without seeing the video. Because i have learnt the concepts from your earlier videos. Thanks and LOTS of LOVE.
THe last one infinite loop example was very helpful to understand the problems condition clearly.
The man who is making every CSE student's career bright
Tysm first time i got clear cut intution of finding the peak element :) tysm again UNDERSTOOD EVERYTHING:)
Understood! Super awesome explanation as always, thank you very much for your effort, and congrats for your product launch!! Is this idea used to find the derivative local maximum / minimum?
An amazing question learning new patterns of conditions in binary search
This was pretty easy, finally solved it on my own.
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
Understood very well sir!!
No words for your appeciation bhaiya
code for the same :-
int findPeakElement(vector& arr) {
int n = arr.size();
//checking done for initial cases where finding and is very easy
if(n==1) //edgecase1
return 0;
if(arr[0] > arr[1]) //edgecase 2
return 0;
if(arr[n-1] > arr[n-2]) //edgecase 3
return n-1;
// now apply bS on remaining part
int l = 1;
int r = n-2;
while(larr[mid+1] && arr[mid]>arr[mid-1])
{
return mid ;
}
else if (arr[mid]>arr[mid-1]) //mid on the increasing path that means our ans will be in right side
l = mid+1;
else // mid is on the decreasing path peak will be on left side
r = mid -1;
}
return -1;
}
not working for all testcases in coding ninjas
iNSTEAD OF ADDING THE LAST CONDITION WE CAN CHANGE THE ABOE CONDITIONS TO :
else if (nums[mid] < nums[mid + 1])
{
low = mid + 1;
}
else if (nums[mid] < nums[mid - 1])
{
high = mid - 1;
}
COMPLETE CODE:
class Solution
{
public:
int findPeakElement(vector &nums)
{
int n = nums.size();
if (n == 1)
{
return 0;
}
if (nums[0] > nums[1])
{
return 0;
}
if (nums[n - 1] > nums[n - 2])
{
return n - 1;
}
int low = 1;
int high = n - 2;
while (high >= low)
{
int mid = low + (high - low) / 2;
if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1])
{
return mid;
}
else if (nums[mid] < nums[mid + 1])
{
low = mid + 1;
}
else if (nums[mid] < nums[mid - 1])
{
high = mid - 1;
}
}
return 0;
}
};
solved by my own thanks a lot Striver Bro keep spreading the knowledge
at the end of video i am just surprised.......understood very clearly.....thankssss a lottttt striver......
Nice explanation on that hidden test case
3:20 here 3 is also peak
Yes...
understood
Thank you striver for such an amazing explanation...
can we simply find the largest and return that index , it will also give the peak😜
it will take o(n) if im not wrong!?
Damn, was eagerly waiting for this!!!
Someone wrote and I quote "Striver can transfer his confidence to his students" .
great content no one teach like this atleast for free
Hii Striver , I think if it chooses else part then it will go towards either left part or right one but in the end we will end up having one element as the peak one. Don't understand on that part. Can you please explain this??
welcome back, waited for you every single day
If we are to return an array of indices where peaks are found(all peak) can we still apply binary search by making some modifications and applying if else checkups. 🤔
int start = 0;
int end = n - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (arr[mid] < arr[mid + 1]) {
start = mid + 1;
}
else {
end = mid;
}
}
return start; (how about this ,easy and covers every edge case)
This is the brute linear solution :
class Solution {
public:
int findPeakElement(vector& nums) {
//Brute force:
int n = nums.size();
int ans = INT_MIN;
int peak_index = -1;
if(n==1) return 0;
for(int i = 0; i < n; i++){
if (nums[i] > ans) {
ans = nums[i];
peak_index = i;
}
}
return peak_index;
}
};
Firstly the brute force psudeo code will only for:
1) array which has one peak element.
2) array is in ascending order
3) array is in descending order.
while(low < high-1){
mid = (low+high)/2;
if(arr[mid]>arr[mid+1] && arr[mid]>arr[mid-1]) return arr[mid];
if(arr[mid+1]>arr[mid]) low = mid+1;
else high = mid-1;
}
if(arr[low]>arr[high]) return arr[low];
else return arr[high];
initially came up with this solution, it was working and was accepted in leetcode
at 21:15 correction* if(arr[o] > arr[1]) return 0; the first index is the peak
Hey Striver , the above method did not worked for this array : {1,1,51,2,3,4,5,6,7,7} , it gave "No Peak".
you cannot have same value at 2 consecutive indexs, therefore this is not a valid input
if(arr[mid]>=arr[mid+1] && arr[mid]>=arr[mid-1]) return mid; // just add a equal operator to handle plateau case
nums[i] != nums[i + 1] for all valid i as mentioned in problem. but (1,51,2,3,4,5,6,7) 51,7 is peak so it will ignore 51 and pick 7 as peak
Understood,thanks striver for this amazing video.
if we give last condition (else high = mid -1;) that will work for both 1 peak element and also multi peak element.
Sir please complete as soon as possible please sir 🙏🙏😢
Bs-9 Done ✅
Weekend 27 July 2024
7:43 pm
But what if question is [1,2,1,3,5,6,4] , it will eliminate left half and go to right where peak is not there
Thank You Striver..Understood everything🙂
Amazing explanation! thanks teacher :)
So someone please clear my doubt binary search is for sorted elements and here the elements might or might not be sorted so will the results be right in all cases if true then why we say BS is applied on sorted elements?
Reversal of a peak is called trough. 30:29
wow, the reversal peak, beautiful
Understood .best Explanation 👍
absolute beauty of a question
Great video sir..thank u for saving us
Bestest explanation ❤
while going through your tutorial i am just taking hint for some question how to eliminate left or right array rest of the code i am doing myself?
int findPeakElement(vector &arr) {
int n= arr.size();
if(n==1){
return 0;
}
if(arr[0]>arr[1]){
return 0;
}
if(arr[n-1]>arr[n-2]){
return n-1;
}
int low =1;
int high=n-1;
int mid= low+(high-low)/2;
while(lowarr[mid-1]&& arr[mid]>arr[mid+1]){
return mid;
}
else if(arr[mid]>arr[mid-1] && arr[mid]
In the last example peak element will be 3 instead of 5 @3:34
How can we print all peak elements? Example - [1, 2, 1, 3, 5, 6, 4] where 2 and 6 are peaks and it only prints 6.
Our bs solution is forged in a way that we move towards one og the peak, to return multiple peak or all peaks, there isn't a solution having O(log n) complexity, for that you can take help of linear search.
How about if we have duplicates, then simply do that low++ and high-- ?
Compiling your Code...
> Success!
Running Test Cases...
> TestCase - Easy Failed
Wrong Answer
Your program's output doesn't match the expected output. You can try testing your code with custom input and try putting debug statements in your code.
Your submission failed for the following input
Arg 1: An Integer Array, For e.g [1,2,3]
[1,1000000000,1000000000]
Test As Custom Input
The expected return value:
1000000000
Your function returned the following:
-1
Final Verdict
> Wrong Answer
Failing for input - [1,1000000000,1000000000] can someone help me Identify the error(Note: the code is same as mentioned in this video)
Excellent explanation
Kya question samjhaya hai bhai 👍👍👍
there is also a brute force approach using stl ....that is we know whatever the case is.... the maximum element of the vector is always a peak element...so we just return the index of the max element....
int ind = max_element( nums.begin(), nums.end() ) - nums.begin() ;
ig
Fantastic teaching...!
Strivers Sir You Are The Best
very good explanation .
God level content 🥵 🔥🔥
DSA me bhaiyaa aap BAAP ho , ye sayad appko khud nahi pata , Love u bhaiya
Hey To use Binary Search Array should be sorted right but we are not sorting the array
thanks striver understood everything
Very well explained. Understood
after elimination one half how can you say the peak will be present at other half, there is a chance that that peak also present at eliminated half.. anyone can explain..
what happens when mid mid+1 and mid-1 element are same and hence peak can be on any side ? is that test case not included on leetcode where there is only one peak and mid mid+1 and mid-1 are same
this will not considered any test case for the peak element
If the array contains a continuous peak ,i.e, same values repeating as peak like (1,2,2,1) we can use the condition of (arr[mid]>=arr[mid-1] && arr[mid]>=arr[mid+1]) this will handle a case like this
will save us one iteration maybe... yes haha
luv the way u teach
far better than other vedio
THANK U STRIVER
UNDERSTOOD 👌👌👌👌👏👏👏👏
Great Playlist . 👍
What if we have to find the maximum peak element out of all peak elements? Can we still do it in O(log n) ?
Understood.
NICE SUPER EXCELLENT MOTIVATED
But what if we need to find all the peak elements. then linear search is the only option I think 🤔🤔🤔🤔🤔🤔or their any better algo
sir, what will be peak element if all elements in array will be same eg {3,3,3}
invalid input h na, question pdho
@@takeUforward sir, actually gfg me ek test case hai esa {2,2}
@@adityasood04 just do a small change in the condition for finding peak use equal in both equation
If arr[mid]>=arr[mid-1] and arr[mid]>=arr[mid+1]:
return mid
@@shramanjain08still error!!
@@shramanjain08 thanks bro🥂