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

⭐ Shop on Amazon to support me: www.amazon.com/?tag=fishercod...
⭐ NordVPN to protect your online privacy: go.nordvpn.net/aff_c?offer_id...
⭐ NordPass to help manage all of your passwords: go.nordpass.io/aff_c?offer_id...
LeetCode 169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
Problem link: leetcode.com/problems/majorit...
Solutions explained:
Boyer-Moore majority vote algorithm: en.wikipedia.org/wiki/Boyer%E...
Time complexity: O(n)
Space complexity: O(1)
⭐ Support my channel and connect with me:
/ @fishercoder
// TOOLS THAT I USE:
○ Memory Foam Set Keyboard Wrist Rest Pad - amzn.to/3cOGOAj
○ Electric Height Adjustable Standing Desk - amzn.to/2S9YexJ
○ Apple Magic Keyboard (Wireless, Rechargable) - amzn.to/36gy5FJ
○ Apple Magic Trackpad 2 (Wireless, Rechargable) - amzn.to/36ltimu
○ Apple MacBook Pro - amzn.to/30iSvKE
○ All-In One Printer - amzn.to/34etmSi
○ Apple AirPods Pro - amzn.to/2GpVYQf
○ My new favorite Apple Watch - amzn.to/2EIIUFd
// MY FAVORITE BOOKS:
○ Introduction to Algorithms - amzn.to/36hxHXD
○ Designing Data-Intensive Applications - amzn.to/2S7snOg
○ Head First Java - amzn.to/2ScLDKa
○ Design Patterns - amzn.to/2SaGeU2
Follow me on Github for complete LeetCode solutions: github.com/fishercoder1534/Le...
Support me on Patreon: / fishercoder
My ENTIRE Programming Equipment and Computer Science Bookshelf:
www.amazon.com/shop/fishercoder
And make sure you subscribe to my channel!
Your comments/thoughts/questions/advice will be greatly appreciated!
#softwareengineering #leetcode #algorithms #coding #interview #SDE #SWE #SiliconValley #programming #datastructures

[@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!

[@SK-yb7bx]

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

[@nishant07kumar]

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

[@FisherCoder]

Glad you found it helpful!

[@QQ-ps2vs]

The best explanation of 169 so far

[@FisherCoder]

Glad you found it helpful!

[@sharanvkt]

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

[@FisherCoder]

Glad it helped!

[@lis3435]

nice explanation! thanks for sharing this video!

[@FisherCoder]

Glad it was helpful!

[@thomasstephenson4043]

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

[@FisherCoder]

Glad it was helpful!

[@Sree-uv9bd]

Excellent explanation ! :) thank you

[@FisherCoder]

Glad it was helpful!

[@dinamohamed13600]

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

[@FisherCoder]

Glad to hear that!

[@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.

[@DecentProgrammer]

Best content. Thanks for the video brother.

[@FisherCoder]

Glad you liked it!

[@KaisarAnvar]

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

[@FisherCoder]

Glad it was helpful!

[@VasheshJ]

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

[@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. 😁

[@justinkuang9423]

Was looking for a more optimal space solution, thanks!

[@victormiene520]

Bless you!

[@haolicoder-5898]

You are great!

[@FisherCoder]

Glad it's helpful!

[@victormiene520]

Bless you

[@jitinroy2246]

awesome

[@lilaiyang5745]

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

[@FisherCoder]

Glad it helped!

[@vijayap1929]

Amazing!

[@FisherCoder]

Thank you! Cheers!

[@zfarahx]

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

[@lephuphan9062]

what is the web browser he used?

[@user-tl4fm3zn7u]

nice man

[@FisherCoder]

Thanks!

[@ahsanhabibabir5887]

thnx

[@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]

[@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.