LeetCode 169. Majority Element - Interview Prep Ep 73 | Boyer-Moore majority vote algorithm

[@DaBigWang]

you're vids are great even today, ty fisher

[@mikedepacina8588]

You're channel is underrated. I find your explanations more understandable and clearer than more famous channels😅

[@FisherCoder]

Glad you like them!

[@sugandhm2666]

Nicely explained steve. This channel is a goldmine for leetcode problems

[@FisherCoder]

Thanks and glad you found it helpful!

[@nishant07kumar]

Like your approach for giving multiple solution of a problem and explanation of each problem.

[@FisherCoder]

Glad you found it helpful!

[@victormiene520]

Bless you

[@DecentProgrammer]

Best content. Thanks for the video brother.

[@FisherCoder]

Glad you liked it!

[@QQ-ps2vs]

The best explanation of 169 so far

[@FisherCoder]

Glad you found it helpful!

[@KaisarAnvar]

Subscribed, and I don't regret it. You're a genius....

[@FisherCoder]

Glad it was helpful!

[@victormiene520]

Bless you!

[@SK-yb7bx]

Well explained. I understand how this works now. Subscribed.

[@dinamohamed13600]

I Like your videos, you make things so easy. good job

[@FisherCoder]

Glad to hear that!

[@thomasstephenson4043]

ok thats pretty cool. you are a good teacher. thank you

[@FisherCoder]

Glad it was helpful!

[@VasheshJ]

Thanks this video was helpful. Could you make a video on segment tree?

[@sharanvkt]

thanks a lottt for this easy yet best explaination. you saved my whole day😊

[@FisherCoder]

Glad it helped!

[@pds7890]

Thank you!! It didn't strike me that I can also sort and get middle element!! 😊 Video was helpful!

[@FisherCoder]

Glad it helped!

[@okey1317]

But sorting will add more complexity right? Also is it possible to use in built sorting methods in coding interview?

[@pds7890]

@@okey1317 Yes it does add more complexity. I think the purpose of exploring various ways to solve a problem is to help us solve new problems. 😁

[@lilaiyang5745]

Clear explanation, I understood it just by watching once. Appreciate 💪

[@FisherCoder]

Glad it helped!

[@lxkp3233]

nice explanation! thanks for sharing this video!

[@FisherCoder]

Glad it was helpful!

[@haolicoder-5898]

You are great!

[@FisherCoder]

Glad it's helpful!

[@Sree-uv9bd]

Excellent explanation ! :) thank you

[@FisherCoder]

Glad it was helpful!

[@jitinroy2246]

awesome

[@chaitanyarao6045]

Hi There, Thanks for the explanation, it’s pretty clear and to the point. Would you mind explaining other areas/questions where this algorithm can be utilized.

[@vijayap1929]

Amazing!

[@FisherCoder]

Thank you! Cheers!

[@justinkuang9423]

Was looking for a more optimal space solution, thanks!

[@zfarahx]

I don't think you've added enough #fishercode tags in your video.

[@RajeebLochanChand-b6b]

nice man

[@FisherCoder]

Thanks!

[@guo7580]

Nice explanation. A minor question: why when counter == 0, candidate is reset to nums[i] while we do not increase counter from 0 to 1 (I mean do "counter++"). Based on your explanation, this should be the case.

[@johnathondouglass]

I don't think that works because then you will exit the if statement and possibly increase the counter by 1 again, I think you would be double counting if you included the counter++ in your if statement?

[@ultrma]

The initinal value of counter should be set as 0. Otherwise this fails at [6,5,5]

[@ahsanhabibabir5887]

thnx

[@lephuphan9062]

what is the web browser he used?

[@sysybaba420]

at 6 20, you said counter start from 0 but int counter = 1 initially. I am confused, do you mind explaining? Great video btw thanks!

[@rufan89]

Initially, you are considering the first element of the array, nums[0], as the candidate for the majority element. Since you've already considered an instance of that element, you initialize the counter to 1.

[@amitbhattacharya356]

Nice explanation, but for this [10,9,9,9,10] as input I am getting the wrong answer.

[@amitbhattacharya356]

class Solution { public int majorityElement(int[] nums) { int count = 1; int candidate = nums[0]; for(int i=1; i

[@timwong2396]

@@amitbhattacharya356 Why set the count = 1? if [a, b, a, b], then candidate b has count 1? initial: candidate = 10 , count 1 i = 1 : candidate = 10, count = 0 ( candidate 9 !== 10) i = 2 : candidate = 9, count = 1 ( candidate 9 === 9) i = 3: candidate = 9 , count = 2 ( candidate 9 === 9) i = 4 : candidate = 9 , count = 1 (candidate 10 !== 9 ) so finally return candidate = 9

[@georgetsiklauri]

Well.. what if we're not guaranteed that the majority exists? then this algorithm doesn't work. Imagine the {2, 2, 3, 3, 1} scenario. 3s would balance out the 2s, and finally, 1 becomes the candidate with count 1. Does that mean, that 1 is the majority because of the counter is positive? no; does even the comparison counter>arr.length/2 give me the correct boolean (whether there is a majority present)? no. Your approach works but in a very limited scope. Would have been better to explain those cases as well.

[@andywang6928]

5/2 = 2. Which one here has a total number larger than 2?

[@georgetsiklauri]

Your approach doesn't work, as I've already mentioned this in a below comment. For the better example, consider {1, 2, 3}: These are the steps taken according to your explanation: Step1: candidate = 1; counter = 1; Step2: candidate = 1; counter = 0; Step3: candidate = 3; counter = 1; and 3 is not a majority element here.

[@ArielVolovik]

This algorithm does one thing and one thing only. If a majority element exists, it will return it. This leetcode questions says that *the majority element does exist* - therefore, it works. If you instead need to also check if the majority element exists, then you would go about it differently.

[@gargichaurasia4103]

@@ArielVolovik Yes, then we have the possibility that this candidate might be or might not be majority element. So in order to verify this we need to traverse the array and keep counting the no of occurences of this particular candidate element. If the frequency is more than N/2 than yes this candidate element is the majority element otherwise there exist no majority element. I this should work.

[@kshitijsingh1990]

In that case, you can write a verification function. private static int majorityElement(int[] nums) { int candidate = 0; int count = 0; for (int num : nums) { if (count == 0) { candidate = num; } if (num == candidate) { count++; } else { count--; } } // Verify if the candidate is the majority element if (isMajority(nums, candidate)) { return candidate; } else { // Handle the case when no majority element is found throw new IllegalArgumentException("No majority element found"); } } private static boolean isMajority(int[] nums, int candidate) { int count = 0; int n = nums.length; // Count how many times the candidate appears in the array for (int num : nums) { if (num == candidate) { count++; } } // Return true if the candidate appears more than n/2 times return count > n / 2; }