BS-9. Find Peak Element
Вставка
- Опубліковано 27 вер 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
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 UA-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
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
the best about this video was the thinking process of how to arrive from linear to binary search in problems like this. execellent stuff.
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!
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.
Thank you ! wrote the same code without watching the video. All because of you.
Commenting Understood is just a simple thing for your wonderful explanation !!!
Thank you So much for your lectures Striver
Woah, solved this at once! Think I'm learning this concept!
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).
Didn't even look for completion time of the video!!!.....So that much interesting your videos are❤
The man who is making every CSE student's career bright
done with easy part of binary search from monday will start with medium part
lots of love raj bhaiya
Amazing explanation Striver my man! Hats off to you for all your hard work for the community.
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
Bro u are the most helpful person for all engineering cse student 🧡❤
Best explanation on the UA-cam thank you soo much....each and every second of this video is informative.
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.
Was able to do it myself 😮 thnx for building up my logical thinking ❤
Your explanation is crazy. You are really doing a very good job.
Filled with full confidence after watching ur videos.
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 was pretty easy, finally solved it on my own.
An amazing question learning new patterns of conditions in binary search
Nice explanation on that hidden test case
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;
}
};
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;
}
THe last one infinite loop example was very helpful to understand the problems condition clearly.
Bhaiya I solved this without seeing the video. Because i have learnt the concepts from your earlier videos. Thanks and LOTS of LOVE.
3:20 here 3 is also peak
Yes...
at the end of video i am just surprised.......understood very clearly.....thankssss a lottttt striver......
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
Damn, was eagerly waiting for this!!!
Understood very well sir!!
No words for your appeciation bhaiya
Tysm first time i got clear cut intution of finding the peak element :) tysm again UNDERSTOOD EVERYTHING:)
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
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!?
absolute beauty of a question
great content no one teach like this atleast for free
Understood.
Understood,thanks striver for this amazing video.
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 )
❤
welcome back, waited for you every single day
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?
Strivers Sir You Are The Best
Sir please complete as soon as possible please sir 🙏🙏😢
Thank You Striver..Understood everything🙂
wow, the reversal peak, beautiful
Understood .best Explanation 👍
Amazing explanation! thanks teacher :)
Kya question samjhaya hai bhai 👍👍👍
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.
Excellent explanation
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;
}
};
at 21:15 correction* if(arr[o] > arr[1]) return 0; the first index is the peak
God level content 🥵 🔥🔥
understood 😇
if we give last condition (else high = mid -1;) that will work for both 1 peak element and also multi peak element.
Understood
Reversal of a peak is called trough. 30:29
UNDERSTOOD 👌👌👌👌👏👏👏👏
THANK U STRIVER
UNDERSTOOD
Understood Bhaiya
Fantastic teaching...!
Understood boss!!
far better than other vedio
NICE SUPER EXCELLENT MOTIVATED
Very well explained. Understood
Great Playlist . 👍
DSA me bhaiyaa aap BAAP ho , ye sayad appko khud nahi pata , Love u bhaiya
understood striver
Thank you Bhaiya
Understood!
Loved it
Mind blowing video..
understood, you are BEST !
luv the way u teach
shukriya habibi ..
Understood Very Well!
thank you
you are really great one ..
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
Thank you striver 😇🙌
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
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)
Lovely striver.
I don't think people can explain like this.
understood
Understood . Thanks a lot.
awesome
Understood Striver :)
we can see sleep in his eyes, but still he is doing.
crazy😴
Understood !!!!!!!!!!!!!!!!!!!!!
3:42 at last there are 2 peak elements
5 and 3
Understood perfectly!!!!
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??
BEST!