Majority Element I | Majority Element II : Boyer-Moore | Made Simple | Leetcode - 229 and 169

iPad PDF Notes - github.com/MAZ...
This is the 63rd Video on our Arrays (1-D & 2-D) Playlist.
In this video we will try to solve a very very famous array Problem - Majority Element I and Majority Element II (Leetcode-229 & Leetcode-169).
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Majority Element I and Majority Element II
Company Tags : AMAZON | GOOGLE
My solutions on Github (C++ & JAVA) :
Majority Element - I github.com/MAZ...
Majority Element - II github.com/MAZ...
Leetcode Link :
Majority Element - I leetcode.com/p...
Majority Element - II leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approaches Summary :
Majority Element I - The algorithm iterates through the array, maintaining a count variable and a candidate variable. It initializes the count to 0 and the candidate to NULL. For each element in the array, it checks if the count is zero. If so, it sets the count to 1 and updates the candidate to the current element. If the current element is equal to the candidate, it increments the count; otherwise, it decrements the count. The algorithm does not explicitly check the frequency of the candidate, as it is guaranteed that a majority element exists. Finally, it returns the majority element found using this approach.
Majority Element II - It employs a variation of the Boyer-Moore Voting Algorithm to identify two potential majority elements (maj1 and maj2) and then validates their frequencies in a second pass. The algorithm initializes two candidates (maj1 and maj2) and their corresponding counts (count1 and count2) to NULL and 0, respectively. It also calculates the required frequency threshold (freq) based on the array size. The first loop iterates through the array, updating the counts and candidates based on the Boyer-Moore Voting Algorithm. In the second pass, the algorithm counts the occurrences of maj1 and maj2 in the array and checks if they meet the frequency criteria. The elements that satisfy the condition are added to the result vector, which is then returned. This approach ensures that the elements included in the result vector appear more than ⌊ n/3 ⌋ times in the given array.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[@shivamtomar9658]

bhaiya aapko etni depth m knowledge h hr ek topic. bhot hardworking ho bhaiya aap. 🙏

[@codestorywithMIK]

Hi there, I am just like you all. With more practice and consistency we all can gain more knowledge. Thank you for joining this journey with me . Let’s keep it going 💪😇🙏❤️

[@shivamtomar9658]

@@codestorywithMIK thank you so much bhaiya forever ♥

[@nagmakhan672]

@@codestorywithMIK Hats off to your humbleness. You are so down to earth..

[@user-ub2is4rs4x]

@@codestorywithMIKwe are with you in this journey ❤

[@aws_handles]

@@codestorywithMIK👌🏻👌🏻

[@TheLearningMonk]

Initialize majority1 = NULL and majority2 also, fails the test cases when the array having less then 3 element, so Initialize with INT_MAX. Btw thank you so much bhaiya for those quality videos and easy explanation❤🙏

[@codestorywithMIK]

Thank you 😇🙏

[@abhayroadlines528]

after watching 1 or 2 videos for the same problem, I stuck with this video and got my mind crystal clear with all of the doubts about the algorithm. Thank you so much❤

[@codestorywithMIK]

Thank you ❤️🙏

[@Akashkumar_12]

Your explanation is very clear brother and thank you so much 😊

[@Ankita-sd5gp]

The way you explain even the important caches and makes it easier with story is the most amazing thing. Kudos to you. Really appreciate all your work !

[@HarshitKumar-gn5wf]

i was solved it with the brute force without using any hint and was very happy because it was my first medium level challenge that i solved on my own, but then after seeing this that there is a more optimal approach , i was happy and sad at the same time :)))

[@codestorywithMIK]

Never be sad. Trust me this is the process how we learn and grow. Together we are in this journey and we will definitely improve with time. Let’s keep moving 😇🙏

[@AlishaKhan-ww3io]

Wow, i was hoping to find Part I in Your playlist and here i got both 😍 Thanks a lot

[@avishkarrangari2328]

i get to learn something new everyday, thanks for your explanation mate hope to see more in the future .😁

[@codestorywithMIK]

Thank you 😇🙏

[@newglobal7271]

Wow , What a great Explaination !!!! maja agya❤❤❤❤❤❤❤❤❤❤

[@codestorywithMIK]

Thank you 😇🙏

[@anuppatankar4294]

Great Video 😍

[@codestorywithMIK]

Thank you 😇🙏

[@deepjyotidas37]

No doubt striver atcha padhata hai ! Maine uske moore voting algorithm dekha tha but samajh mein nahi aya tumhara 2-3 minute dekh-kar hi samaj mein aagaya. Brilliant !!

[@codestorywithMIK]

It means a lot to me 🙏❤️ Thank you for watching and trusting my content.

[@herculean6748]

wow, I really liked that part when you explained why we need to check the elements first and not blindly update when the count becomes zero

[@codestorywithMIK]

Glad it helped. Thank you 😇🙏

[@herculean6748]

@@codestorywithMIK I watch your videos even after solving the question, because I know I will learn something new :)

[@codestorywithMIK]

Means a lot 😇🙏

[@xiaoshen194]

I did majority element 1 in O(1) time complexity 🎉

[@MdAli-jc3fe]

how ??

[@EB-ot8uu]

big fan of your teaching style

[@ugcwithaddi]

Best explanation found since morning 👌🏻👌🏻

[@Momentsofmagic28]

Both I and II 🤩 Was waiting for you only sir.

[@nagmakhan672]

Crystal clear as always. One stop solution 👌

[@shashanksharma2258]

Thank you so much bhaiya bahut badhiya samjhaya

[@codestorywithMIK]

Thank you 😇🙏

[@sachinmohanty4577]

The algorithm is pretty awesome.. MIK you are just awesome just like this algo ❤

[@codestorywithMIK]

And you guys are awesome too. Thank you so much 😇🙏❤️

[@souravjoshi2293]

You are the best bro. Hats off to your knowledge 🔥

[@nibaronkumar2484]

Brother you are doing great job, love from Bangladesh❤❤💕💕

[@codestorywithMIK]

Thank you so much 😇🙏 Love from India 🇮🇳 ❤️

[@nagmakhan3165]

Waited for your videos only 🔥🔥👌

[@disastermaster4226]

ty sir

[@NikhilSharma-qc1ez]

Bhai maja aa gya Nice Explaination

[@EnglsihCommByNawaz]

There is a condition diff in Majority Element 2 that is you didn't use else if( nums[i] == majorityElemen1 ) count1++; and else if( nums[i]== majorityElemen2 ) count2++;

[@codestorywithMIK]

Hi there, I did use these two conditions : if(nums[i] == maj1) count1++; else if(nums[i] == maj2) count2++; Can you please elaborate what you mean above ? Thank you 😇🙏

[@EnglsihCommByNawaz]

Sorry Sir ! In Majority Element 1 ques you used this condition that i.e after count condition that i e if(majorityElem == nums[I]) count1++ by fault I'm thinking in Majority 2 question you used the condition above count I'm thinking you forget to mention these conditions after updating the count. But Thanks for explaining in such depth!!

[@tutuimam3381]

Thanks a lot ❤❤

[@JoyAcharyatvl]

nice bhai , like always

[@codestorywithMIK]

Thank you 😇🙏

[@yikes3807]

thank u was waiting for video. love your videos sir best...

[@codestorywithMIK]

So nice of you 😇🙏

[@EnglsihCommByNawaz]

One of the best explanation ❤

[@codestorywithMIK]

Thank you so much 😇🙏

[@sushanthgupta626]

Hi sir i have one simple doubt why we are reducing cnt1 and cnt2 both, in maj 1 question you explained that as some other candidate is increasing instead we can say one candidates vote is decreasing.. similarly here we should have decrease for one candidate only why both?

[@sauravchandra10]

Clear and concise, thanks

[@codestorywithMIK]

Glad it was helpful! 😇🙏❤️

[@adarshrajpathak0]

great teaching skill 👏

[@mewaconite]

awesome... very very clear solution video .... thank you MIK !🙂

[@codestorywithMIK]

Thank you 😇🙏

[@aswithasai4015]

was waiting for your video thank youu

[@codestorywithMIK]

Hope you enjoyed it! Thank you 😇🙏

[@vivekbhardwaj9289]

Sir, Would you please provide the java code for the same. I'm having issue with the wrong answer. (Leetcode 229)

[@ShubhamNancheOfficial]

I used your algo in Java, don't know why it failed at int[] nums = { 1, 1, 2, 3, 4, 1, 1, 5, 6, 7, 1, 1, 8, 9, 10, 1, 11, 12, 13, 14 }; as the test input My code (in Java): public List majorityElement(int[] nums) { // Boyer & Moore's voting algorithm if (nums.length 13 maj2 > 14 // verify if they are actually majority List res = new ArrayList(); int target = nums.length / 3; count1 = 0; count2 = 0; for (int i = 0; i < nums.length; i++) { if (majority1 == nums[i]) { count1++; } else if (majority2 == nums[i]) { count2++; } } if (count1 > target) { res.add(majority1); } if (count2 > target) { res.add(majority2); } return res; }

[@mohithadiyal6083]

The best explanation 😊

[@codestorywithMIK]

Thank you for watching 😇🙏

[@badbaboye]

Thanks

[@ashutoshpandey1639]

Bhaiya initially first element ko maj1 and maj2 ku nhi bna diya, isme kya dikkat aaegi

[@codestorywithMIK]

Good Qn and I should have covered this too. Let me try to explain here : What if you assign maj1 = nums[0]; maj2 = nums[1] in the beginning. Let's take an example : [1,1,1,3,3,2,2,2] If you do so, you will be assigning maj1 = 1 and maj2 = 1 as well. This will assume both maj1 and maj2 are same which will be wrong and won't work as per our logic written inside for loop. Really hope this helps. Would suggest you to a complete dry run of this example above. Thank you ♥

[@Memerluffy]

16:37

[@newglobal7271]

One more think sir , please discuss time & space complexity , for this solution will it be(Tc->O(n)+O(n)=O(n) and as it takes only 2 element so the Sc be O(1)?

[@codestorywithMIK]

You are absolutely correct 🙌😇

[@aws_handles]

hats off

[@gauravbanerjee2898]

Thanks a lot bhaiya ❤❤

[@adarshamit7860]

bhaiya leetcode number 3020 ki video hai? which was asked in weekly contest 382, I was not able to find it in your channel ... if somebody found it please share with me!!

[@umeshbisht1054]

Thanku bhaiya ❤

[@codestorywithMIK]

Thank you 😇🙏

[@code_runner3843]

Great bhaiya❤

[@codestorywithMIK]

Thank you 😇🙏

[@dayashankarlakhotia4943]

class Solution { public List majorityElement(int nums){ Listans=newArrayList >>(); int m1=-1,m2=-1,cnt1=0,cnt2=0; for(int num;nums) if(num==m1){ ++cnt1; }else if(num==m2){ ++cnt2; }else if (cnt1 ==0){ m1=num; ++cnt1; }else if(cnt2 ==0){ m2=num; ++cnt2 ; }else { --cnt1; --cnt2; } cnt1=0; cnt2 =0; for(num:nums) if(num==m1) ++cnt1; elseif (num==m2) ++cnt2; if(cnt1 >nums.length/3) ans.add(m1); if(cnt2 >nums.length/3) ans.add (m2); return ans; } };

[@aniketpandey1913]

why are we doing both count1-- and count2-- together and not just count1-- or count2--, I'm not able to understand, have gone through some post but didn't get the intuition

[@codestorywithMIK]

Hi there, Actually if you want to do only count1 - - Or want to do only count2 - - , Then the qn is on what basis we take that decision. So the intuition behind this lies in the core of this Algorithm that “when we see a new element which is neither equal to maj1 or maj2, it is actually a threat (candidate for becoming maj1 or maj2 in future) and hence it will impact both the count1 and count2” Hope this helps 😇🙏

[@aniketpandey1913]

@@codestorywithMIK understood thanks

[@keertilata20]

BESTTT💙💙

[@codestorywithMIK]

Thank you 😇🙏

[@Samtoosoon]

for(int &num:nums) isme mujhe confusion hoti hai stl walle loop mai

[@Samtoosoon]

Range based loops got it

[@harsh.jain22]

bhaiya mai brute force se toh kar leta hu par optimal approach ata hi nhi h mind me , jaise is question me mujhe pta hi nhi tha ye boyer-moore algo ke baare me , toh kya aapne jab ye question pehli baar attempt kiya tha toh : kya aapko is algo ke baare me pehle se pta tha ? ya aapko bhi solutions dekhne padte hai ?

[@codestorywithMIK]

Hi Harsh, The first time when I had seen this qn long ago, I remember I didn’t know about this algorithm. Then I studied and explored this algorithm. Then now I am able to remember this algo and solve this qn. Trust me , this is how we learn and grow with time by seeing more qns.

[@naveen_soni_1]

Very nice explained please provide this ppt

[@codestorywithMIK]

Sure thing. You can find the Link for the PDF notes in the Description. Let me share it here also : github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-229%20%26%20169%20-%20Majority%20Element%20I%20%26%20II.pdf Thank you for watching ❣

[@anikpal7862]

My initial approach class Solution { public: vector majorityElement(vector& nums) { int n = nums.size(); vector ans; unordered_map mp; for(int i = 0; i < n; i++) { mp[nums[i]]++; } for(auto x: mp) { if (x.second > n/3) { ans.push_back(x.first); } } return ans; } };

[@codestorywithMIK]

Keep it up 👍🏻

[@mathematics7746]

2223334 isme to highest frequency 2 or 3 ka hai fir dry run krne se to 4 ayega last me candidate ye case kaise handle hoga using this algorithms can you please tell me??

[@codestorywithMIK]

Here is how the flow will go for your test case : i = 0 maj1 = 2, count1 = 1 i = 1 maj1 = 2, count1 = 2 i = 2 maj1 = 2, count1 = 3 i = 3, maj2 = 3, count2 = 1 i = 4 maj2 = 3, count1 = 2 i = 5 maj2 = 3, count1 = 3 i = 6 count1- - count2- - i goes out of bounds. maj1 = 2 maj2 = 3 So this will work for this test case too. Hope this helps. Thank you for watching 😇🙏❤️

[@codeandtalk6]

❤❤❤

[@sidhanttiwari942]

majority 2 waale main dono ka count kyu decrease kr rhe thhe?

[@codestorywithMIK]

Hi there, Actually if you want to do only count1 - - Or want to do only count2 - - , Then the qn is on what basis we take that decision. So the intuition behind this lies in the core of this Algorithm that “when we see a new element which is neither equal to maj1 or maj2, it is actually a threat (candidate for becoming maj1 or maj2 in future) and hence it will impact both the count1 and count2” Hope this helps 😇🙏

[@sidhanttiwari942]

@@codestorywithMIK thanks It makes sense

[@dayashankarlakhotia4943]

my journey comleted one year please refers Low level design playlist

[@codestorywithMIK]

Well noted 👍🏻

[@molyoxide8358]

Bro with your permission I will post the video's link in my LC solution. So, pls provide your LC profile link for creidts.

[@codestorywithMIK]

Sure 🙏❤️ you can mention my channel name/link

[@molyoxide8358]

@@codestorywithMIK OK sure bhaiya

[@HealthyOm]

always something specials

[@codestorywithMIK]

Thank you 😇🙏

[@yadav.nitin03]

Yo🎉

[@codestorywithMIK]

Thank you 😇🙏

[@Samtoosoon]

Null kyu kiya maj ko asign samjh nhi aaya

[@jelouche]

because maj currently is not know, you can also take it INT_MIN

[@Memerluffy]

13:08