If anyone is confused as to why are we manually checking, we are doing it because it is not guarenteed in the question that there are 2 majority elements, there can be 0,1 or 2 majority elements
manual checking is for cases where no such element exists. {1,2,3,4,5,6} candidate1 = 6 after processing for loop. But it is not so we check by using frequency test. If it fails = return -1 else return candidate.
Bhya I've just completed your Dp playlist, i am amazed how beautifully u interconnect previous concepts into new questions like in 0/1, unbounded ,MCM.. Thanks a lot again, now I've confidence to solve any DP question...
How did u go about solving DSA problems. Do u read the question on leetcode or coding ninja and try to come up with a Brute better optimal solution. Or u directly watch the solution video and then try to solve the problem.
@@manan-543 bro, for approaching any dsa problem i personally follow these steps. 1. Reading the problem statement(at least twice) 2. Dry run, needless to say most important step 3. Writting algorithm and pseudo code on my notebook. 4. Code part 5. Intuition 6. Complexity Analysis. And lastly, plateform doesn't matter, i mainly solve on codeforces and leetcode and sometimes gfg..
@@leetcoder6569 thanks for advice . But what i meant is that if you're new to a topic like u mentioned dynamic programming, do u watch the video solution from striver first and then code it? Or do u first read the question and try to come up with a solution on your own.
Great explanation. Adding on to the above explanation. If we change the placement of 3rd and 4th else if condition to first and second then we don't need to write extra steps. Example: for(int i=0; i
Bhaiya please please upload the video daily from now onwards placement are coming so please from today onwards upload daily it will be so helpful in parallel to that take care of your health you are providing a free education we all always pray you to be healthy and wealthy
#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...
How to enable Dark mode in TUF Website ? 01:12 Problem Statement 02:02 Observation 03:46 Brute force using Looping 05:32 Pseudocode 07:25 Complexity 07:59 Better approach using Hashing 11:49 Pseudocode 13:08 Complexity 14:39 Optimal approach n/2 times (Extended Boyer Moore’s Voting Algorithm) 14:54 Code 15:10 Intuition for n/3 times 19:14 Dry run 22:37 Code 25:47 Complexity
One question, do we even need to do the optimal algorithm? I mean the folks taking the interview are mostly pleased with a working solution. Even though the optimal algorithm is actually more optimized in terms of space but it is less readable and also very verbose than the better solution which might be a drawback. Speaking from experience.
in the last for loop we use else if instead of using if to avoid the testcase [0,0,0]. code: class Solution { public: vector majorityElement(vector& nums) { int n = nums.size(); int el1 = INT_MIN; int el2 = INT_MIN; int cnt1=0; int cnt2=0; for(int i=0;i n/3) ans.push_back(el2); return ans; } };
For those who have problem in understanding why we cannot have more than 2 majority elements in this case : - An element can be a majority element only if it appears more than floor(n/3) times, i.e it should appear atleast n/3 + 1 time . Only two such elements are possible in an array. Let's prove this by contradiction. I will assume that we have three majority element possible in an array then minimum size of array is 3 * (n/3 + 1) which is equal to n + 3. But we know that we have only n elements in an array , hence it is not possible to have more than 2 majority elements.
clear explenation. this logic is not working in leetcode testcase [1,1,1,2,3,7,8,1,6,9] .I think we need some changes in the logic in case of one element being the answer. This is my first doubt after studying 100s of dsa problems from this channel
bro in yout example there are only one element which is greater than n/3 and in list answer we have to return list which contain 2 such element which is greater than n/3
I did it first😁 vector majorityElement(vector V) { sort(V.begin(),V.end()); vector ls; int n=V.size(); int el = V[0]; int count = 1; for(int i=1 ; i(n/3)){ ls.push_back(el); } el = V[i]; count = 1; }
For optimal , can we do something like sort the array first then using for loop we can have every element's first and last occurences and difference of these two will give the no. of times that particular element occured and if that count is greater than n/3 we'll save it. Obviously the T.C. will be nlogn but I think it's good to be optimal and O(n) will be most optimal.
Hey @takeUforward Rather than checkng if the any element is being already tracked at the other count, can we change the order of checking. I was wondering if this will work always, it seems to be working for me. class Solution: def majorityElement(self, nums: List[int]) -> List[int]: ele1 = None ele2 = None c1 = 0 c2 = 0 # checking if the element is equal first rather than if count is zero. for ele in nums: if ele == ele1: c1+=1 elif ele == ele2: c2+=1 elif c1==0: ele1 = ele c1+=1 elif c2==0: ele2 = ele c2+=1 else: c1-=1 c2-=1 c1 = 0 c2 = 0 for ele in nums: if ele == ele1: c1+=1 elif ele == ele2: c2+=1 n=len(nums) res = [] if c1>n//3: res.append(ele1) if c2>n//3: res.append(ele2) return res
Ahh one question, that el and cnt logic was meant to do what exactly in the bigger scheme, because el1, el2 and cnt1, cnt2 are done for tracking two elements, I just tried this array [1,1,3,2,1,4,4,1] in the hopes to find some understanding, does it tell us the max frequency number and hence we use both el1 and el2 to get two most frequently happening numbers? In this array [1,1,3,2,1,1,4,4,4] we should get el as the highest frequency 1 but we get 4, then what is the need of doing this?
Great explaination but @striver can you please tell me why we substract from both cnt1 and cnt2? And can this be implement for any values n/x where x can be 1,2,3,4?
Sir, in the optimal approach, we hv taken two separate variables for storing the two majority elements. And here the array size is just 8. What if the array size is 10 or something. In that case, we can hv more than 2 majority elements. How can Moore's voting algorithm be applied in that case.
vector majorityElement(vector v) { // Write your code here int n=v.size(); vector ans; sort(v.begin(),v.end()); int count=0; int a=floor(n/3); if(n==1){ return v; } for(int i=1;ia){ if (count
6:40 In this code suppose the array is {1,1,2,2,3,3,4,4} then the TC will be N^2 because inside loop will run for Eveysingle time as nothing will be added in list. What if instead we right condition as if i==0 || nums[i] ! = nums[i-1] so here it will skip the number which are repeated!! Anyone can Correct me if I am wrong. Your most welcome.
can someone explain why we are doing c1- - as well as c2 - - in the else part of the optimal approach. Logically one element should cancel out only one other element so why are we cancelling out two elements against 1 element.
20:29 Can anyone please help me on why else if is so much imp? I mean if both counters are zero, why can't we reset them to 1 at the same time. This is confusing me
class Solution { public: vector majorityElement(vector& nums) { vector ans; map mp; int n = nums.size(); int mini = floor(n / 3) + 1; for (int i = 0; i < n; i++) { mp[nums[i]]++; } for (auto& p : mp) { if (p.second == mini) { ans.push_back(p.first); } } return ans; } }; what is wrong in this code?
I have a doubt in the optimal answer code: if instead of if(cnt2==0 && nums[i]!=ele1){ ele2=nums[i]; cnt2=1; } I replace it with : else if(cnt2==0 && nums[i]!=ele1){ ele2=nums[i]; cnt2=1; } The code doesnt pass all test cases. I do not understand why. If both cnt1 and cnt2 are zero it anyways will not be executed since ele1==nums[i]. So why does it fail?
because it is possible that we have 0 number of answer or 1 number of answer but in case of n/2 its gurranted to have a answer, we simply finding the 2 number which have maximum frequency and then checking they are valid or not P.S. pls like the comment if you found helpful
I have a doubt if the array length is 10 and array would be like [1, 1, 1, 2, 5, 2, 5, 2, 5, 6] so here majority element should be [1, 2, 5] since each element occurs >n/3 times but it only returns 2 elements [1, 2]
Check the constraints Whatever is the A[i] range, ele1 and ele2 will be from that range itself, and INT_MIN is most likely below that range, so surely won't be an ans.
Yes, I faced the same issue, but for that I made a change which passed all the test cases including 0,0,0 At last when we are pushing elements in the answer array, don't write both the conditions in the 'if' statement. Use if(elm1>=mini) ..... else if (ele2>=mini)... Don't use 'if' in both, use 'else if', in the second statement. This way, the same element won't be compared and added twice to the answer array.
@@ayushichoudhary1019 that still won't work when there are 2 different majority elements only the first one will get inserted into the ans vector. So. instead we have to do something like if( c11 > mini){ // cout mini && el2 != el1){ // cout
Hey, I have this doubt that if there are 3 elements in the list that appear n/3 times how we will get the third element which part of the code id keeping track of that.
it is not possible to have more than 2 elements.if the length of array is multiple of 3 then the floor can exist 3 times in the array. but the element1 and 2 should continue more than floor .i hope you get the idea
![[UNCUT] The Loyal Pin ปิ่นภักดิ์ EP.7 (1/4)](http://i.ytimg.com/vi/2rPGOyKs0VE/mqdefault.jpg)
Do give us a like, it won't cost you anything, but it will motivate me more. Also don't forget to comment "understood" if you did.
Bro Notes link is not visible. How to access it.
ok
When will this damn interviewer be happy? 😂😂😂😂
😂😂
When you give the optimal approach🤣
😂
when u write exactly the same code he has in his mind 😂
If anyone is confused as to why are we manually checking, we are doing it because it is not guarenteed in the question that there are 2 majority elements, there can be 0,1 or 2 majority elements
Thankyou so much
manual checking is for cases where no such element exists.
{1,2,3,4,5,6}
candidate1 = 6 after processing for loop.
But it is not so we check by using frequency test.
If it fails = return -1
else
return candidate.
Bhya I've just completed your Dp playlist, i am amazed how beautifully u interconnect previous concepts into new questions like in 0/1, unbounded ,MCM.. Thanks a lot again, now I've confidence to solve any DP question...
How did u go about solving DSA problems. Do u read the question on leetcode or coding ninja and try to come up with a Brute better optimal solution. Or u directly watch the solution video and then try to solve the problem.
@@manan-543 bro, for approaching any dsa problem i personally follow these steps.
1. Reading the problem statement(at least twice)
2. Dry run, needless to say most important step
3. Writting algorithm and pseudo code on my notebook.
4. Code part
5. Intuition
6. Complexity Analysis.
And lastly, plateform doesn't matter, i mainly solve on codeforces and leetcode and sometimes gfg..
@@leetcoder6569 thanks for advice . But what i meant is that if you're new to a topic like u mentioned dynamic programming, do u watch the video solution from striver first and then code it? Or do u first read the question and try to come up with a solution on your own.
@@manan-543 i solve it on my own at first, and i watch striver video only for optimal approaches.
Great explanation. Adding on to the above explanation. If we change the placement of 3rd and 4th else if condition to first and second then we don't need to write extra steps.
Example:
for(int i=0; i
Bhaiya please please upload the video daily from now onwards placement are coming so please from today onwards upload daily it will be so helpful in parallel to that take care of your health you are providing a free education we all always pray you to be healthy and wealthy
+1
@@vidhusingh2792 please bhaiya +1
#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...
i was able to solve it on my own cuz i've watched the previous majority n/2 ele video carefully .ty bhaiya
bhai mai toh phir bhi nhi kr paya🥲
@@sarthakbahuguna7958 same
How to enable Dark mode in TUF Website ?
01:12 Problem Statement
02:02 Observation
03:46 Brute force using Looping
05:32 Pseudocode
07:25 Complexity
07:59 Better approach using Hashing
11:49 Pseudocode
13:08 Complexity
14:39 Optimal approach n/2 times (Extended Boyer Moore’s Voting Algorithm)
14:54 Code
15:10 Intuition for n/3 times
19:14 Dry run
22:37 Code
25:47 Complexity
use any extension
@@mohamadsultankhatri Thank, you 🤝
use extension called dark reader
@@john_doe_2231 Thanks John
One question, do we even need to do the optimal algorithm? I mean the folks taking the interview are mostly pleased with a working solution. Even though the optimal algorithm is actually more optimized in terms of space but it is less readable and also very verbose than the better solution which might be a drawback. Speaking from experience.
It's not necessary for the interview but it's necessary for the coding round, the better the code more the chances you are going in second round.
in the last for loop we use else if instead of using if to avoid the testcase [0,0,0].
code:
class Solution {
public:
vector majorityElement(vector& nums) {
int n = nums.size();
int el1 = INT_MIN;
int el2 = INT_MIN;
int cnt1=0;
int cnt2=0;
for(int i=0;i n/3) ans.push_back(el2);
return ans;
}
};
The way you simplifies the things is amazing❤❤❤
i didn't understand the intuition in the optimal solution of this problem even though I understood the Moore's voting algorithm
Understood!!
And I wish I could have knew about this Channel earlier 😢
set MajorityElementByCountThree(vector arr){
int count = 0;
int threshold = arr.size() / 3;
map Leader;
set elements;
for(int i = 0 ; i < arr.size() ; i++){
Leader[arr[i]]++;
if(Leader[arr[i]] > threshold){
elements.insert(arr[i]);
}
}
return elements;
}
More optimal
19:05 - bro wtf... I listened to you and side by side made notes as if this pseudocode was the exact ans to this problem. LOL 😂
Bro that simulation of code is amazing ❤❤❤
Understood! Super amazing explanation as always, thank you very very much for your effort!!
For those who have problem in understanding why we cannot have more than 2 majority elements in this case : -
An element can be a majority element only if it appears more than floor(n/3) times, i.e it should appear atleast n/3 + 1 time . Only two such elements are possible in an array. Let's prove this by contradiction.
I will assume that we have three majority element possible in an array then minimum size of array is 3 * (n/3 + 1) which is equal to n + 3. But we know that we have only n elements in an array , hence it is not possible to have more than 2 majority elements.
Bhaiya please upload daily videos 🙂🙂🙂... Your playlists are the best
Sure I will try my best. Timestamps XD
clear explenation. this logic is not working in leetcode testcase [1,1,1,2,3,7,8,1,6,9] .I think we need some changes in the logic in case of one element being the answer. This is my first doubt after studying 100s of dsa problems from this channel
there can only be one elements as the answer, the example you sharing is an invalid one.
@@takeUforward [1,1,1,2,3,7,8,1,6,9] this test case is invalid ,how?
verify krenge toh automatically false ele remove ho jayega
@@nasim3987bro u got to know the answer...??
bro in yout example there are only one element which is greater than n/3 and in list answer we have to return list which contain 2 such element which is greater than n/3
I did it first😁
vector majorityElement(vector V) {
sort(V.begin(),V.end());
vector ls;
int n=V.size();
int el = V[0];
int count = 1;
for(int i=1 ; i(n/3)){
ls.push_back(el);
}
el = V[i];
count = 1;
}
}
return ls;
}
For optimal , can we do something like sort the array first then using for loop we can have every element's first and last occurences and difference of these two will give the no. of times that particular element occured and if that count is greater than n/3 we'll save it.
Obviously the T.C. will be nlogn but I think it's good to be optimal and O(n) will be most optimal.
that will distort the input array,. so you are involving an extra space in order to solve the problem, but yes this can be a solution as well.
hey !! I came up with the same brute force approach :D
Understood #day 5 striver sde sheet. Still long way to go , I am always missing optimal solution 😢
Beautifully explained. Good work Raj.
Hey @takeUforward
Rather than checkng if the any element is being already tracked at the other count, can we change the order of checking. I was wondering if this will work always, it seems to be working for me.
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
ele1 = None
ele2 = None
c1 = 0
c2 = 0
# checking if the element is equal first rather than if count is zero.
for ele in nums:
if ele == ele1:
c1+=1
elif ele == ele2:
c2+=1
elif c1==0:
ele1 = ele
c1+=1
elif c2==0:
ele2 = ele
c2+=1
else:
c1-=1
c2-=1
c1 = 0
c2 = 0
for ele in nums:
if ele == ele1:
c1+=1
elif ele == ele2:
c2+=1
n=len(nums)
res = []
if c1>n//3:
res.append(ele1)
if c2>n//3:
res.append(ele2)
return res
Sir the brute approach is not working instead if the ls[0] we have to use the find(ls.begin() , ls.end() , nums[i]) != ls.end()
Ahh one question, that el and cnt logic was meant to do what exactly in the bigger scheme, because el1, el2 and cnt1, cnt2 are done for tracking two elements, I just tried this array [1,1,3,2,1,4,4,1] in the hopes to find some understanding, does it tell us the max frequency number and hence we use both el1 and el2 to get two most frequently happening numbers? In this array [1,1,3,2,1,1,4,4,4] we should get el as the highest frequency 1 but we get 4, then what is the need of doing this?
Watch from 15:12 if you've already followed his > n/2 approach problems
Understood! Thank you sooo much Striver
Great explaination but @striver can you please tell me why we substract from both cnt1 and cnt2? And can this be implement for any values n/x where x can be 1,2,3,4?
Check moore's voting algorithm then you would get the intuiton!! for the first part of the question
MORE VIDEOS ON SOLVING LEETCODE OR GFG PROBLEMS
🙏🙏
TEACH US THE WAY TO APPROACH THE OPT.SOLUTION
FOR ANY GIVEN PROBLEM
Sir, in the optimal approach, we hv taken two separate variables for storing the two majority elements. And here the array size is just 8. What if the array size is 10 or something. In that case, we can hv more than 2 majority elements. How can Moore's voting algorithm be applied in that case.
vector majorityElement(vector v) {
// Write your code here
int n=v.size();
vector ans;
sort(v.begin(),v.end());
int count=0;
int a=floor(n/3);
if(n==1){
return v;
}
for(int i=1;ia){
if (count
Understood bro. awesome explaination.
6:40
In this code suppose the array is {1,1,2,2,3,3,4,4} then the TC will be N^2 because inside loop will run for Eveysingle time as nothing will be added in list.
What if instead we right condition as if i==0 || nums[i] ! = nums[i-1] so here it will skip the number which are repeated!!
Anyone can Correct me if I am wrong. Your most welcome.
it is not given in the question that the array will be sorted
I thinking the code is wrong because it checks the 0th index in the list but the array can be of any order so I think he made a mistake
Understood, thank you striver for this amazing video.
When current element is not equal to el1 but its equal to el2 then we are increaiong cnt2 but why we are not decreasing the vote for cnt1?
I hope you are also doing well, take care 👍
Perfect series ever
Great explanation.
can someone explain why we are doing c1- - as well as c2 - - in the else part of the optimal approach. Logically one element should cancel out only one other element so why are we cancelling out two elements against 1 element.
I had the same question. If u find the answer then let me know
Chamak gya concept striver bhaiyaa❤
20:29 Can anyone please help me on why else if is so much imp? I mean if both counters are zero, why can't we reset them to 1 at the same time. This is confusing me
Small request Striver ,can you please add the new YT video link in the SDE sheet instead ot the older videos
Doing it already!
class Solution {
public:
vector majorityElement(vector& nums) {
vector ans;
map mp;
int n = nums.size();
int mini = floor(n / 3) + 1;
for (int i = 0; i < n; i++) {
mp[nums[i]]++;
}
for (auto& p : mp) {
if (p.second == mini) {
ans.push_back(p.first);
}
}
return ans;
}
}; what is wrong in this code?
use p.second>=mini not always equal like [2,2,2]
why we do cnt1-- and cnt2-- both?? please tell logic behind this
because int final answer list we can have max to max 2 element only
Thankyou! You're the best.
very nice videos!! keep making them. Thank you!!
I have a doubt in the optimal answer code: if instead of
if(cnt2==0 && nums[i]!=ele1){
ele2=nums[i];
cnt2=1;
}
I replace it with :
else if(cnt2==0 && nums[i]!=ele1){
ele2=nums[i];
cnt2=1;
}
The code doesnt pass all test cases. I do not understand why. If both cnt1 and cnt2 are zero it anyways will not be executed since ele1==nums[i]. So why does it fail?
Understood Awesome as usual
Thank you. Understood it
i m writing the code in java ,it is not able to pass the [0,0,0] test case
understood thnx for the video ❤❤❤❤👌👌👌👌💕💕
awesome content , love from westbengal🤗🤗🤗
What's the intution behind doing the manual check? Why can't we get the exact answer just same as n/2 case?
because it is possible that we have 0 number of answer or 1 number of answer but in case of n/2 its gurranted to have a answer, we simply finding the 2 number which have maximum frequency and then checking they are valid or not
P.S. pls like the comment if you found helpful
brute solution is only for upto n=9,, what to do if n is greater than 9 in brute solution for ex; n=15
I have a doubt if the array length is 10 and array would be like [1, 1, 1, 2, 5, 2, 5, 2, 5, 6] so here majority element should be [1, 2, 5] since each element occurs >n/3 times but it only returns 2 elements [1, 2]
it returns nothing, bcoz 10/3 is 3.33 and it should return a number which is more than 3 times.
Tysm Striver Understood everything
in 14:18 code it will add duplicates also
yes we will need to add an if condition to check if that element is already present or not
Like we used to HashMap(java) to store the frequency , we can use hasharray to do the same as well right?
yes you can, but hasharray will not work if N is very large.
Understood and waiting for more stuff
Can someone explain the intution behind cancelling both cnts when we come across a different element?
UNDERSTOOD👍
Understood!🤩
We inspire by u striver, can we know by whom u inspire or inspired by??
what is the need to manually count?
Understood, thanks!
You are remaking many of the older array videos , will you be doing the same for LL ,stacks etc ?
how can you say that INT_MIN will not be a solution?
Check the constraints
Whatever is the A[i] range, ele1 and ele2 will be from that range itself, and INT_MIN is most likely below that range, so surely won't be an ans.
Understood✅🔥🔥
sir pr chat gpt toh hash maps ki time complexity O(1) bta raha hai or avg case ki O(N) bta raha
Understood❤
Thanks Striver!
Understood. Thank you.
understood thankyou so much striver :)
Understood bhaiya 🙏 ❤️
code is not working if elements are like 0,0,0
Yes, I faced the same issue, but for that I made a change which passed all the test cases including 0,0,0
At last when we are pushing elements in the answer array, don't write both the conditions in the 'if' statement.
Use
if(elm1>=mini) .....
else if (ele2>=mini)...
Don't use 'if' in both, use 'else if', in the second statement. This way, the same element won't be compared and added twice to the answer array.
@@ayushichoudhary1019 fantastic thank you
@@ayushichoudhary1019 that still won't work when there are 2 different majority elements only the first one will get inserted into the ans vector.
So. instead we have to do something like
if( c11 > mini){
// cout mini && el2 != el1){
// cout
Understood bhaiya..!!
Understood
Those who have difficulty in understanding, can go for shreesh sir pepcoding majority element 2
Understood!
understood
Great job mann!!
Understood ✨
plz upload the video regularly
thanks!
Thanks a lot Bhaiya
UNDERSTOOD!
superb sir
at 7:24 code is not the correct for all of the test case. has not anyone dry run that code for all test cases🤔
Yes the code is wrong
Hey, I have this doubt that if there are 3 elements in the list that appear n/3 times how we will get the third element which part of the code id keeping track of that.
it is not possible to have more than 2 elements.if the length of array is multiple of 3 then the floor can exist 3 times in the array. but the element1 and 2 should continue more than floor .i hope you get the idea
Understood, thanks :)
tysm sir
Bhaiya please if possible handwriting improve krlo thodi. Dry run ke vakt kuch samaz nahi aaya .
There isn't any link to access the java code
why we subtracting count1 and count2;
I have the same question
Understood. Edge case also Understood
why do we need to manually check after applying algo?
Just for verification we do, because sometimes it happens last few iterations we get such an element which is not greater than n/2 or n/3
Understood....