Majority Element II | Brute-Better-Optimal
Vložit
- čas přidán 27. 07. 2024
- Problem Link: bit.ly/3vIsCTH
Notes/C++/Java/Python codes: takeuforward.org/data-structu...
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/takeUforward
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
When will this damn interviewer be happy? 😂😂😂😂
😂😂
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.
The way you simplifies the things is amazing❤❤❤
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
Understood! Super amazing explanation as always, thank you very very much for your effort!!
Beautifully explained. Good work Raj.
Bro that simulation of code is amazing ❤❤❤
very nice videos!! keep making them. Thank you!!
Understood, thank you striver for this amazing video.
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
Understood Awesome as usual
Chamak gya concept striver bhaiyaa❤
Understood bro. awesome explaination.
Thankyou! You're the best.
i didn't understand the intuition in the optimal solution of this problem even though I understood the Moore's voting algorithm
Tysm Striver Understood everything
Understood!!
And I wish I could have knew about this Channel earlier 😢
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
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
Understood and waiting for more stuff
Great job mann!!
Understood, thanks!
Understood bhaiya 🙏 ❤️
awesome content , love from westbengal🤗🤗🤗
understood thankyou so much striver :)
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
Understood. Thank you.
Understood!🤩
Understood✅🔥🔥
Thanks Striver!
Understood bhaiya..!!
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 😂
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
understood thnx for the video ❤❤❤❤👌👌👌👌💕💕
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.
Understood ✨
UNDERSTOOD!
Understood, thanks :)
I hope you are also doing well, take care 👍
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?
Understood ❤️
UNDERSTOOD👍
MORE VIDEOS ON SOLVING LEETCODE OR GFG PROBLEMS
🙏🙏
TEACH US THE WAY TO APPROACH THE OPT.SOLUTION
FOR ANY GIVEN PROBLEM
Understood ❤
Thanks a lot Bhaiya
superb sir
thanks!
Understood 😊
Bhaiya please upload daily videos 🙂🙂🙂... Your playlists are the best
Sure I will try my best. Timestamps XD
Understood 🎉
Understood #day 5 striver sde sheet. Still long way to go , I am always missing optimal solution 😢
Understood 👍👍
understood !
Understood !
understood bhaiya
UNDERSTOOD
Thanks ❤
Understood 😁😁
UNDERSTOOOD
Understood!!
plz upload the video regularly
Understood😃
You are remaking many of the older array videos , will you be doing the same for LL ,stacks etc ?
Understood.
understood👍
Understood :)
tysm sir
thankyou sir
understood 🤩🤩🤩
Understood
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
understood :)
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
awesome
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
Small request Striver ,can you please add the new YT video link in the SDE sheet instead ot the older videos
Doing it already!
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....
tnx
Can someone explain the intution behind cancelling both cnts when we come across a different element?
understtooodd
Great
Understood. Edge case also Understood
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
Watch from 15:12 if you've already followed his > n/2 approach problems
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?
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?
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]
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;
}
We inspire by u striver, can we know by whom u inspire or inspired by??
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
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
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()
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.
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
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
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