Majority Element II | Brute-Better-Optimal
HTML-код
- Опубликовано: 8 фев 2025
- Problem Link: bit.ly/3vIsCTH
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
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
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
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.
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
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 😂
Even before that, when will I reach in the interview.
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
How ? Can you explain ?
yes it will work, it will skip the previously taken e1 or e2
@@the_avii_7 Do a dry run for the array he showed the failed case, and this code would run succesfully.
@lamexd Yes. I was confused at that time. But later I understood it and forgot to edit my comment.
can you explain how does cancelling two elements for sake of one is working
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
#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
use any extension
@@mohamadsultankhatri Thank, you 🤝
use extension called dark reader
@@john_doe_2231 Thanks John
The way you simplifies the things is amazing❤❤❤
for last step to add element to list we have to check for duplicate elements also
int mini = int(n / 3) + 1;
if (cnt1 >= mini) ls.push_back(el1);
if (cnt2 >= mini && el1!=el2) ls.push_back(el2);
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 😂
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;
}
};
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
Bro that simulation of code is amazing ❤❤❤
Understood!!
And I wish I could have knew about this Channel earlier 😢
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
Understood and perfect explanation as always!
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;
}
Understood, thank you striver for this amazing video.
Beautifully explained. Good work Raj.
i didn't understand the intuition in the optimal solution of this problem even though I understood the Moore's voting algorithm
I will recommend you first understand Majority Element I ( > n/2 or element occurring more than 50% of n) then it would be definitely clear.
Understood! Thank you sooo much Striver
Watch from 15:12 if you've already followed his > n/2 approach problems
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
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
thank u so much A very much helpful content and so deep way of making clearity with the problem👍👍👍👍
Perfect series ever
Understood bro. awesome explaination.
Thankyou! You're the best.
goood work bhaiya ji
may god give you everything you want in life😀
Understood Awesome as usual
Understood!🤩
understood thnx for the video ❤❤❤❤👌👌👌👌💕💕
Awesome explanation!! ❤
very nice videos!! keep making them. Thank you!!
Understood #day 5 striver sde sheet. Still long way to go , I am always missing optimal solution 😢
I hope you are also doing well, take care 👍
Chamak gya concept striver bhaiyaa❤
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✅🔥🔥
awesome content , love from westbengal🤗🤗🤗
Understood, thanks!
Tysm Striver Understood everything
understood, thanks for the great video
For [0,0,0], my code was returning [0,0] because both ele1 and ele2 were being set to 0, and I didn’t check if they were the same before adding to the result list.
Fix:
I added a condition to ensure ele1 and ele2 are distinct before adding ele2 to the result list.
int mini=(nums.length/3)+1;
if(cnt1>=mini) ls.add(ele1);
if(cnt2>=mini && ele1!=ele2) ls.add(ele2);
MORE VIDEOS ON SOLVING LEETCODE OR GFG PROBLEMS
🙏🙏
TEACH US THE WAY TO APPROACH THE OPT.SOLUTION
FOR ANY GIVEN PROBLEM
Great explanation.
Understood and waiting for more stuff
Thank you. Understood it
Understood striver ⚡
Understood bhaiya..!!
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
Thanks Striver!
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]
Understood bhaiya 🙏 ❤️
Understood. Thank you.
Great job mann!!
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
no it won't, it will add only when arr[i] == mini, not when arr[i] > mini, so no need to add extra condition
Understood ✨
first video where optimal doesnt feels like an optimal , the map method was far better ,but yeah , theoretically that optimal one is better
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!
understood thankyou so much striver :)
Can someone explain the intution behind cancelling both cnts when we come across a different element?
Thank you
Small request Striver ,can you please add the new YT video link in the SDE sheet instead ot the older videos
Doing it already!
UNDERSTOOD👍
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.
thanks!
Thanks a lot Bhaiya
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
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
when list size is 2 why we break up pls help in simple words
Thank you..
superb sir
UNDERSTOOOD
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🤔
Understood, thanks :)
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?
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
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
UNDERSTOOD
Thanks ❤
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.
Understood 😊
Understood ❤️
Understood !
understood bhaiya
understood!
We inspire by u striver, can we know by whom u inspire or inspired by??
at the end is the manual check necessary?
plz upload the video regularly
What is the application being used to teach?
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?
tysm sir
Understood😃
You are remaking many of the older array videos , will you be doing the same for LL ,stacks etc ?