Bhai have a doubt .. after the loop if we check cnt is not equal to 0 and return el then also the program executes properly then why we are again taking second loop ..?
@@suchitakulkarni2744 The first loop will only give you the majority element, the second loop is used to check whether the frequency of the element from the first loop is greater than n/2. You can clearly understand this by watching once again the video from 13.00 where raj bhai explains by changing the last 4 elements to 1.
int majorityElement(vector v) { int n=v.size(); sort(v.begin(),v.end()); return v[n/2]; } this is also accepted and time complexity is O(nlogn) space is O(1)
@@suchitakulkarni2744 if the problem statement says that there will always be a majority element then you don't need the second loop but if it doesn't guarantees a majority element then you have to check. timestamp : 17.00 . hope this clears
No matters how hard the paid courses gang will try to defame you or stop you , we STUDENTS will never stop promoting you among our friends and support you in your journey.❤❤
Hey Striver bro , It will be humble request from myside that could you please explain the approaches in Hindi&English language if possible. It will be very useful for many of students like me.
Understood! Very well.None of them can match your dedication and energy.🔥🔥🔥🔥 And when you explain how algorithm is working the first thing comes in my mind damm! Yarr ye to kisi ne bataya hi nahi tha how the cnt is working.
I'm hating it now. Not able to build intuition myself. Always dependent on video solutions. Sometimes I feel I'm too dumb and not built for this thing. What should I do 😭😭
very great intutions bhaiyaa!!! you are a legend. never thought i would be enjoying dsa and leetcode like this... i dont care i get a job or not but i have to finish this just for the thrill!!!
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India..
better : sorting O(nlogn) int majorityElement(vector& nums) { int n= nums.size(); sort (nums.begin(),nums.end()); return (nums[n/2]); } optimal is the same : moore's
I also thought the same but there are two things here, 1. It should be given that the majority element always exists for given test cases. 2. Time complexity wise Moore's is still better.
Let me help u guys understand : point 1 : moores law gives ans when there is strictly majority element present in the array. point 2 : use this example to understand it in clear way [1,2,1,3,1,4,1,5,1] if last last number was not 1 then it clearly means that there is no majority element in array else its 100% that it will be the last element in above example point 3 : understand it more by seeing these examples [1,2,3,4] gives ans as 4 but its not valid array as (there is no majority element in it) point 4 : there is no chance that we will get any other number other than majority number as ans,if there is strictly majority number present in the array and if the array is not only the valid array i,e(there is no majority element in it) then ans can be any value.
So this is valid if there is strictly a majority, else not possible? [2 2 2 1 1 1 3 3] as per the video logic 3 comes as majority. But N/2 = 8/2 = 4 to be an answer, answer has to satisfy, answer > 4. So seems like no way to . . . .??? Plz help to make things clear
@@AffairWithGeo The question does mention that there does exist a majority element. Your test case itself is invalid becoz it doesn't have any majority element.
I could write all the three approaches without even looking at the solution. Striver's lectures have made my coding skills made this strong. Literally grateful !!
Super Duper Amazing... Your explaination from brute-better-optimal is fantastic with Time and Space complexity. Moor's Voting Algorithm explained by you is really awesome without using any extra space. The best thing like once in a blue moon type.. I liked the most is you explain in a unique way in every tutorial.. Here is.. like.. How Time complexity is O(N) not added (because in problem, array have atleast one majority element. So, here TC < O(N) always at the time of checking majority) in Moore's Voting algorithm at the time of checking 'el' is majourity or not.. And also you explain Space Complexity also. Thankyou Striver for such an amazing tutorial 🔥.
2 things: 1) this algo will give you majority element but it can be true for only last some portion of array(i.e 2 3 2 3 1 algo will give you 1 but it's only true for last portion of array which [1] and it's of size 1 but it's not true for whole array) , now comes to 2nd step 2) algo give you probable majority element, now check whether it's correct or not by iterating over an array In case of 2 3 2 3 1 Algo gives you 1 as probable majority element Now, by applying 2nd you will find out that 1 is not majority element if we consider whole array of size 5 So, it means array doesn't have any majority element Because if it does, it would have caught by algo But the probable majority element that algo gives us (1) is also not an answer, so there is no majority element in an array
I stuck with the algorithm thinking that it only works with last portion of array to find majority element but your excellent explanation removed my confusion, thank you.
Hi Raj, Thanks for the video. As per your explanation, one more slight optimisation we can do in Moore's Voting Algorithm if we're not sure whether majority element exists. Say we have array size n and n%2==0(means and even size array) and if our count value at last is also 0 in that case we do not need to go to the 2nd step i.e. traverse the whole array again to get the occurrence of element(ele variable value). Hope it makes sense.
i just watch the video ,understand the concept but doesn"t code right away i try to solve the same question on leetcode after 1-2 days .this relly help me to use my own mind while code . and amazing job striver for making coding simpler
if array is must having a majority element then do this :- public int majorityElement(int[] nums) { int count = 0 , el = 0; for(int i = 0 ; i < nums.length ; i++){ if(count == 0){ el = nums[i]; count=0; } if(el == nums[i]){ count++; }else{ count--; } if(count > nums.length/2){ break; } } return el; }
I think the code could have been much simpler to understand if we would have wrote like this,just a suggestion :) int majorityElement(int arr[],int n) { int i=0; int cnt=0; for (int j = 0; j < n; j++) { if(arr[j]==arr[i]) cnt++; else cnt--; } if(cnt
Oh God dimag hil Gaya pura. How did someone invent so innovative algorithms and how can someone explain it so lucidly. Striver daa you are just CODING GOD. Uff 🔥🔥🔥. May God bless you always. ❤️❤️
You dont have to loop through the array in the end to verify the count bro count++ and count-- => when this becomes 0 it ensures that total elements so for is 2n and when the final count is > 0 it ensures that the element with count !== 0 will have count > n/2
@takeUForward , awesome explanation, really appreciate your efforts. The way you explain stuff is really remarkable. I see a small bug in the code class Solution: def majorityElement(self, nums: List[int]) -> int: ele = None count = 0 for num in nums: if count == 0: ele = num # count += 1
i thought of an approach in each we sort the given array and return the element present at the index N/2 ..... this approach is taking O(nlogn) time and O(1) space complexity.
While solving the problem I wrote my own solution, it's O(nlogn) because we need to sort the array but it's passing all testcases and even time complexity test : just have a look at it : static int majorityElement(int a[], int size) { // your code here //sorting array here will take O(nlogn) Arrays.sort(a); int count=0; //traversing array once O(n) for(int i=0;i0&&a[i]>a[i-1]){ count=0; } //else increasing count count++; //checking majority if(count>size/2){ return a[i]; } } return -1; }
int majorityElement(vector v) { // Write your code here int cnt=1; int ans; sort(v.begin(),v.end()); for(int i=0;i v.size()/2) { ans=v[i]; } } else{ cnt=1; } } return ans; } This can also be better approach
sort(nums.begin(),nums.end()); int n = nums.size(); return nums[n/2]; we can also use this bcoz the ques suggests majority>n/2 so it will always occupy the n/2 th index.
fantastic explanation, you really went over the algo well. and its such a brilliant algo too. i initially solved with a hashmap, but this is much much better since constant space,
![Eminem - Somebody Save Me (feat. Jelly Roll) [Official Music Video]](http://i.ytimg.com/vi/Vwa0HenQMi4/mqdefault.jpg)
Please watch our new video on the same topic: ruclips.net/video/vwZj1K0e9U8/видео.html
Bhai have a doubt .. after the loop if we check cnt is not equal to 0 and return el then also the program executes properly then why we are again taking second loop ..?
@@suchitakulkarni2744 The first loop will only give you the majority element, the second loop is used to check whether the frequency of the element from the first loop is greater than n/2. You can clearly understand this by watching once again the video from 13.00 where raj bhai explains by changing the last 4 elements to 1.
int majorityElement(vector v) {
int n=v.size();
sort(v.begin(),v.end());
return v[n/2];
} this is also accepted and time complexity is O(nlogn) space is O(1)
@@suchitakulkarni2744 if the problem statement says that there will always be a majority element then you don't need the second loop but if it doesn't guarantees a majority element then you have to check. timestamp : 17.00 . hope this clears
No matters how hard the paid courses gang will try to defame you or stop you , we STUDENTS will never stop promoting you among our friends and support you in your journey.❤❤
one leetcode a day keeps unemployment away
Bro... don't ever say this 🤐
Really?
wah arshad wah
Reality is often disappointing.
not even the bare minimum to get a job bro
"sitting in an interview u cannot invent the algorithm" LMAOOOO xd
tell them brute force then 🙂
Let's march ahead, and create an unmatchable DSA course! ❤
Use the problem links in the description.
Hatsoff to this consistency
Time Stamp
0:43 - Problem Statement
1:45 - Brute Force Solution
2:58 - Better Solution
4:46 - Code (Better Solution)
6:58 - Optimal (Moore's Voting Algorithm)
7:38 - Dry run + Intuition
14:37 - Code
16:52 - Time complexity
17:36 - Outro
Hey Striver bro , It will be humble request from myside that could you please explain the approaches in Hindi&English language if possible. It will be very useful for many of students like me.
You dont have to ask for likes RAJ. You will get them even if you dont say. THis level of top notch content will not go un-noticed.
Wow hats off ❤❤❤🎉
Striver Bhai Level of Dedication and hardwork u put on this is .....
Understood! Very well.None of them can match your dedication and energy.🔥🔥🔥🔥
And when you explain how algorithm is working the first thing comes in my mind damm! Yarr ye to kisi ne bataya hi nahi tha how the cnt is working.
u make me fall in love with coding there was a tym i hated it i started late but yes you are true inspiration
I'm hating it now. Not able to build intuition myself. Always dependent on video solutions. Sometimes I feel I'm too dumb and not built for this thing. What should I do 😭😭
very great intutions bhaiyaa!!! you are a legend. never thought i would be enjoying dsa and leetcode like this... i dont care i get a job or not but i have to finish this just for the thrill!!!
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India..
better : sorting O(nlogn)
int majorityElement(vector& nums) {
int n= nums.size();
sort (nums.begin(),nums.end());
return (nums[n/2]);
}
optimal is the same : moore's
I also thought the same but there are two things here,
1. It should be given that the majority element always exists for given test cases.
2. Time complexity wise Moore's is still better.
@@sachinthakkar5027 yes
Let me help u guys understand :
point 1 : moores law gives ans when there is strictly majority element present in the array.
point 2 : use this example to understand it in clear way [1,2,1,3,1,4,1,5,1]
if last last number was not 1 then it clearly means that there is no majority element in array
else its 100% that it will be the last element in above example
point 3 : understand it more by seeing these examples
[1,2,3,4] gives ans as 4 but its not valid array as (there is no majority element in it)
point 4 : there is no chance that we will get any other number other than majority number as ans,if there is strictly majority number present in the array and if the array is not only the valid array i,e(there is no majority element in it) then ans can be any value.
👏👏
Thanks bro, I was so confused on this point (We could get 1 as the ans despite it not being majority) but your comment cleared it
So this is valid if there is strictly a majority, else not possible?
[2 2 2 1 1 1 3 3] as per the video logic 3 comes as majority. But N/2 = 8/2 = 4 to be an answer, answer has to satisfy, answer > 4. So seems like no way to . . . .???
Plz help to make things clear
@@AffairWithGeo The question does mention that there does exist a majority element. Your test case itself is invalid becoz it doesn't have any majority element.
i dont know why but you really helped me😊😊
I could write all the three approaches without even looking at the solution. Striver's lectures have made my coding skills made this strong. Literally grateful !!
Very good explanation. Better than any paid DSA course in market. Thank you so much Striver bhai.
Please Take care of your health Striver bhaiya.... because i am seeing dark circles around your eyes...📢📢
Understood! Bhai never gone through such type of explanation ....thank you very much....
Understood! Super fantastic explanation as always, thank you so much for your effort!!
Super Duper Amazing... Your explaination from brute-better-optimal is fantastic with Time and Space complexity. Moor's Voting Algorithm explained by you is really awesome without using any extra space.
The best thing like once in a blue moon type.. I liked the most is you explain in a unique way in every tutorial.. Here is.. like.. How Time complexity is O(N) not added (because in problem, array have atleast one majority element. So, here TC < O(N) always at the time of checking majority) in Moore's Voting algorithm at the time of checking 'el' is majourity or not.. And also you explain Space Complexity also. Thankyou Striver for such an amazing tutorial 🔥.
literally you are amazing .
Loved the way you explained brother. You're a true magic man
completed and understood!
Consistency 🔥 🔥.
Thanks for all you do. I really appreciate
understood very well,you are a gem
Understood!
Moore's Voting Algorithm is Awesome.
Understood and practiced the code as always! Let's really Take Ourselves Forward!!
Buk e amar gorom rokto, amra striver er vokto!
great content!
Nice one 😂👌
2 things:
1) this algo will give you majority element but it can be true for only last some portion of array(i.e 2 3 2 3 1 algo will give you 1 but it's only true for last portion of array which [1] and it's of size 1 but it's not true for whole array) , now comes to 2nd step
2) algo give you probable majority element, now check whether it's correct or not by iterating over an array
In case of 2 3 2 3 1
Algo gives you 1 as probable majority element
Now, by applying 2nd you will find out that 1 is not majority element if we consider whole array of size 5
So, it means array doesn't have any majority element
Because if it does, it would have caught by algo
But the probable majority element that algo gives us (1) is also not an answer, so there is no majority element in an array
I stuck with the algorithm thinking that it only works with last portion of array to find majority element but your excellent explanation removed my confusion, thank you.
@@rakeshnagarkar8759 you're welcome dear
Hi Raj,
Thanks for the video.
As per your explanation, one more slight optimisation we can do in Moore's Voting Algorithm if we're not sure whether majority element exists. Say we have array size n and n%2==0(means and even size array) and if our count value at last is also 0 in that case we do not need to go to the 2nd step i.e. traverse the whole array again to get the occurrence of element(ele variable value). Hope it makes sense.
0:00 Introduction of course
0:46 Majority Element(>n/2)
1:48 Brute approach
2:17 Pseudo code (Brute)
2:56 Better solution
4:45 Code-compiler (Better solution)
6:59 Optimal(Moore's Voting Algorithm)
7:56 Algorithm explanation+Dry run
14:37 Code-compiler (Optimal approach)
Understood
Thank You :-)
Understood !!!
Time Stamp
0:43 - Problem Statement
1:45 - Brute Force Solution
2:58 - Better Solution
4:46 - Code (Better Solution)
6:58 - Optimal ( Moore's Voting Algorithm )
7:38 - Dry run + Intuition
14:37 - Code
16:52 - Time complexity
17:36 - Outro
Understood Sir.............Awesome lec.......
i just watch the video ,understand the concept but doesn"t code right away i try to solve the same question on leetcode after 1-2 days .this relly help me to use my own mind while code . and amazing job striver for making coding simpler
Thank you bro i got it
if array is must having a majority element then do this :-
public int majorityElement(int[] nums) {
int count = 0 , el = 0;
for(int i = 0 ; i < nums.length ; i++){
if(count == 0){
el = nums[i];
count=0;
}
if(el == nums[i]){
count++;
}else{
count--;
}
if(count > nums.length/2){
break;
}
}
return el;
}
Thank You Striver Bhaiya for Such a Quality Content...
Understood &&&&&& Love from odisha bhaiya
nicely explained. even though I slept while watching the video, I woke up again and understood the solution xD
thanks
huge respect for you
no words 💖
what a WONDERFULL EXPLANATION sir,understood every thing,please keep making these kinds of videos for us sir, please
understood🥰🥰🥰🥰🥰best DSA videos everr
you can use this solution too........ sort(a.begin(),a.end());
int mid=a.size()/2;
return a[mid];
Thanks for lectures from bottom of my heart.Keep doing good work.
I think the code could have been much simpler to understand if we would have wrote like this,just a suggestion :)
int majorityElement(int arr[],int n) {
int i=0;
int cnt=0;
for (int j = 0; j < n; j++)
{
if(arr[j]==arr[i]) cnt++;
else cnt--;
}
if(cnt
class Solution {
public:
int majorityElement(vector& nums) {
sort(nums.begin(),nums.end());
return nums[nums.size()/2];
}
};
Try your code for [1, 1,2,2]
Understood bhaiya ! Thanks a lot
Very good explanation. Easy to understand. Thanks for posting this video. Hats off to your dedication.
Oh God dimag hil Gaya pura. How did someone invent so innovative algorithms and how can someone explain it so lucidly. Striver daa you are just CODING GOD. Uff 🔥🔥🔥. May God bless you always. ❤️❤️
Seating in Interview you cant discover this algorithm🤣🤣🤣🤣🤣
Done .. Concept clear but want to do revise ❤😊 pls like so it remind me to watch again for revision thankyou bhaiyaa love uh ❤
Completed 7/28!!!
Looking forward more such videos from you bhaiya , you are awesome.
Very well explained
You dont have to loop through the array in the end to verify the count bro
count++ and count-- => when this becomes 0 it ensures that total elements so for is 2n and when the final count is > 0 it ensures that the element with count !== 0 will have count > n/2
oh my god the best course ever
Understood! Really enjoyed your DSA lecture series ❤
@takeUForward , awesome explanation, really appreciate your efforts. The way you explain stuff is really remarkable.
I see a small bug in the code
class Solution:
def majorityElement(self, nums: List[int]) -> int:
ele = None
count = 0
for num in nums:
if count == 0:
ele = num
# count += 1
Thanks for your support❤
wow really good and interactive lecture
Thank you for such in-depth explanation and course❣
Understood, Thank for explaining it so beautifully.
Understood thank you bhaiya
understood. I am going to make that interviewer happy.
Understood . Thank you so much bhaiya for such a clear explanation.
i thought of an approach in each we sort the given array and return the element present at the index N/2 ..... this approach is taking O(nlogn) time and O(1) space complexity.
Hamara driver top gear me gaadi chala raha hai 🔥🔥🔥😁
Understood bro, your explanation is top notch..
Amazing work. Respect!!
i will watch the next video now
Just no words to thank you 🙏🙏🙏
great explanation of moore voting algo..
Understood bro. Thank you for your efforts
Understood. Your explanation is amazing.
While solving the problem I wrote my own solution, it's O(nlogn) because we need to sort the array but it's passing all testcases and even time complexity test :
just have a look at it :
static int majorityElement(int a[], int size)
{
// your code here
//sorting array here will take O(nlogn)
Arrays.sort(a);
int count=0;
//traversing array once O(n)
for(int i=0;i0&&a[i]>a[i-1]){
count=0;
}
//else increasing count
count++;
//checking majority
if(count>size/2){
return a[i];
}
}
return -1;
}
If you sort the array then the answer is simply the element at n/2 index it the sorted array. Nothing to do after sorting
@@AdityaKumar-be7hx 😂😂😅
ohhh
int majorityElement(vector v) {
// Write your code here
int cnt=1;
int ans;
sort(v.begin(),v.end());
for(int i=0;i v.size()/2) {
ans=v[i];
}
}
else{
cnt=1;
}
}
return ans;
}
This can also be better approach
Love the way u teach, wonderful... thnks
thanks striver understood everything
sort(nums.begin(),nums.end());
int n = nums.size();
return nums[n/2]; we can also use this bcoz the ques suggests majority>n/2 so it will always occupy the n/2 th index.
"Sitting in interview , You can't invent this algorithm" funny line.
And Understood
Thanks for making concept soo simple to understand :)
wonderful way of teaching!!! Understood!
Understood. Thanks a lot . Please make more videos
GREAT man on this earth
@takeUforward, Bhayia this course is really awesome.💯
Understood very well brother.
Beautiful algorithm, need to be on quality crack to come up with this in an interview.
sort the array and simply return a[n/2] element always true
Pta ni comment ap tak pahuchega ki ni bt this means alot t us which i can describe in the words ❤
I really appreciate your hard work, bhaiya. Love from the core of my heart from Bangladesh 💝💝
Understood.
understood everything sir awesome video
Very Great Explanation
understood!
Understood. Awesome explanation
Understood, thank you so much
very good feeling confident
Awesome content bro, love you!
thankyou striver!!!! we appreciate your work☺☺
fantastic explanation, you really went over the algo well. and its such a brilliant algo too. i initially solved with a hashmap, but this is much much better since constant space,
Great lecture😇