Majority Element - Leetcode 169 - Python

[@nvjrane]

The 'Boyer-Moore Voting' Algorithm is not possible to come up with unless you have solved this question before. But, you have explained it well. Just one idea why this algorithm works: Because this majority element occurs more than n/2 (floor value) times, even if other elements will 'vote against it', it will win. Thanks for the video!

[@captainmarvel3834]

Man, this your sentence describes this solution so neatly 😮🔥

[@vitzal3691]

I needed this explanation, thanks (:

[@АндрейВласов-д3ь]

"Algorithm is not possible to come up with unless you have solved this question before" that is actually motivating

[@jewsefjones]

Thank you for the algo name.

[@maprohu]

So where did Boyer and Moore get it from? 🤔

[@pratikshanaik4143]

Been grinding leetcode for almost a year. Came up with the Hash Map solution on my own and I have never felt so good. Consistency is the key my friends ! Also, shout out to NeetCode for being the backbone of my prep.

[@niladrisekharnath]

I don't know you but don't give up it gets better.

[@FullMetalAlgorithmist]

I'll be brutally honest, if you are proud of coming up with a simple hashmap solution for an easy problem even after grinding for a year, then i wouldn't really call it as "grinding".

[@justine-george]

@@FullMetalAlgorithmist Unwarranted

[@KM-zd6dq]

@@FullMetalAlgorithmist You said the truth in the nicest way possible

[@drowningpool8356]

@@FullMetalAlgorithmist u were indeed brutal, but i completely agree.

[@Douglasfaparanhos]

Wow, at first I had serious doubts that the second solution would work. But when you explained why (because it is guaranteed that the maximum is more than half array size) that made total sense! I would never ever think about it! Thanks a lot 👏👏

[@bolhoso]

Dude, I can even feel you're excited to explain the O(1) space solution. By far the best resource I've found on youtube explaining algo problems.

[@efefeyzimantaroglu4676]

How do people come up with those solutions. It's like magic!

[@saleem-hadad]

True. Smart people out there.

[@samuelmayna]

This is a test if someone had seen the question.I don't think someone can come up with the solution on their own.

[@FoxInTheBasement]

@@samuelmayna exactly. "shoulders of giants". big tech isnt expecting hyper geniuses who pull phd level math solutions out of their ass in every round of their interviews. They do expect you to have been taught and recognize the times to use these solutions.

[@sudhanshushekhar4222]

Exactly.....in an interview it's actually very hard to come up with solutions like this.... unless you have seen this type of problem earlier..

[@kamalasowmya7120]

Very smart!

[@CEOofTheHood]

Man I love having my mind blown. I got this feeling when doing this question and leetcode range addition 370. Both blew my mind. It's why I will never stop doing leetcode not just for interviews but just for the sake of learning something this awesome.

[@NeetCode]

Agree, if not for stressful interviews, I think most people will kinda like leetcode.

[@Deschuttes]

I like getting blown in general but yes, some leetcode problems are actually kind of neet.

[@daiki2509]

What about an input of [2, 2, 1, 1, 3, 3, 1]? For index 3, the count will be zero. Then, the count for 3 will be two minus one, but "3" is not the majority number.

[@sraghav42]

Your input does not follow the problem's constraint - the problem assures that the input will always have a majority element (which means it should occur more than half the length of the input array). In your case 1's occur only 3 times which is not more than half the size of the array.

[@DurgaSivaLokeshTelaprolu]

your dictionary code was bit tricky :) A simpler code for this would be: class Solution: def majorityElement(self, nums: List[int]) -> int: n = len(nums) my_dict = {} for num in nums: my_dict[num] = 1 + my_dict.get(num, 0) if my_dict[num] > n/2: return num

[@pawelpow]

I came up with this solution before finding out about the Boyer-Moore algorithm. This seems to work and is also linear time complexity with a constant space complexity as I'm doing operations in-place... def majority(numbers): if len(numbers) == 1: return numbers[0] left, right = 0, 1 while right < len(numbers): if numbers[left] is None: left += 1 if numbers[right] is None: right += 1 continue if numbers[left] != numbers[right]: numbers[left] = None numbers[right] = None left += 1 right += 1 else: right += 1 # Return the first non-nil element for num in numbers: if num is not None: return num

[@arjn00]

For the HashMap solution this was what I came up with. Thoughts? def majorityElement(self, nums: List[int]) -> int: # T: O(n) S: O(n) # Frequency Dictionary to keep track of each num and it's count # defaultdict(int) initializes each key with default val 0 to avoid KeyError freqDict = defaultdict(int) # Majority variable to check the num's count against majority = len(nums) // 2 # For each number in the array for i in nums: # Increment the numm's count in the dictionary freqDict[i] += 1 # If at any point the num's count passes the majority, return the num if (freqDict[i] > majority): return i

[@pnthrillz]

Dude your every algo explanation is top notch! Best in the business! Please continue this

[@ronnier320]

Initialize an element m and a counter i with i = 0 For each element x of the input sequence: If i = 0, then assign m = x and i = 1 else if m = x, then assign i = i + 1 else assign i = i − 1 Return m

[@MTX1699]

The second solution too was kinda an obvious one, given the output needs to be the majority element, because the majority element will always and always outpower any types of combinations of other elements because at the end, it is occuring more than half of the time.

[@chungu5824]

Ive just started leetcode and dealing with time complexities and such, I came up with this solution: from collections import Counter class Solution: def majorityElement(self, nums: List[int]) -> int: nums_list = dict(Counter(nums)) for num in nums_list.items(): if num[1] > len(nums) / 2: return num[0] I was just wondering would this also not be O(1) or would it be O(n) and if so why is the solution in the video o(1) not O(n)?

[@NguyenLe-pu6mr]

This is the first time I comment on a KZbin video, this channel is amazing. U got an answer for every single question when I watching your video.

[@AminABbasi]

Thanks for the Video, indeed I did the first solution but the second seems more efficient. I it's not necessary to compare "n == res" since the count is the representation of majority element not element itself, this is my code: ``` count = 0 for num in nums: if count == 0: result = num count += 1 else: count += 1 return result ```

[@hotskull15547]

It's crazy because I was thinking of this but could never find a way to implement it, good video!

[@grok_coder]

This is such an elegant solution! Thanks!

[@EzWorkzzStudios]

That second solution was absolutely magic at first haha. Got the hashmap one on LC, came here for the optimized one. Too intuitive.

[@arihantd]

My approach was return the middle of the sorted array, const space but nlogn time

[@iamstudying389]

if only there was a way to sort in o (1) most of the questions WILL BE SO EASYYY. i wish i be the one to find such a way

[@licokr]

This is a way I used to understand the second algorithm. The question makes sure there is definitely the majority number. You can think of there are only two possibilities. the majority number and numbers that aren't majority. If there are five 1, three 2, two 4. The count variable is changing depending on the order of the numbers, but actually, each number is counted as many as its number. Because the increasing number is under the court === 0 if logic, right? So in the end, the winner will become the majority number. I don't know this is a good way to explain this, a little bit with intuitive feeling as well...

[@algoaddicts9473]

I think here you missed a case in moore's voting algo Lets take the example [2,2,1,1,3,2,4] Here first 2,2 and 1,1 will cancel out then 3 and 2 will cancel out then last element remaining will be 4 which is wrong answer if returned. So you have to add a case atlast to check if the element is greater than the n/2 (n -> size of array). If the question says there is definitely a majority element (element with count > n/2) then you can go with your approach.

[@geniusinmaking]

the question already takes care of that, we are given that a majority element (appearing more than n/2 times) is guaranteed

[@surengriezy70]

class Solution: def majorityElement(self, nums: List[int]) -> int: result = 0 count = 0 for num in nums: if count == 0: result = num if num == result: count +=1 else: count -= 1 return result ###For beginners

[@LydiaGetachew]

The follow-up was amazing

[@putin_navsegda6487]

great ! Thank you ! Dictionary solution was pretty obviuous

[@jrickyramos]

first leetcode solution to get on my own! Had to watch the video for the follow up though... great solution and perfectly explained as always! count = Counter(nums) items = count.items() length = len(nums) for n,i in items: if i > length/2: return n

[@shivikamishra3690]

A smaller and easier solution: count = {} for n in nums: count[n] = 1 + count.get(n,0) if count[n]>len(nums)//2: return n

[@milesl577]

this is a simpler and faster solution

[@taimoorali818]

Yea, but only if we can have O(n) as our space complexity.

[@yuvrajkukreja1248]

What about [2,2,1,1,1,7,9] will it give correct answer?? The second algorithm???

[@kat0uttahellotp779]

No element in that list appears more than n/2 times. So it wouldn't be a valid input

[@dinesh.p8642]

Brother, Thanks for the video.

[@ladydimitrescu1155]

what a beautiful algorithm and so well explained

[@shuoliu3546]

After coding by myself, I checked your video, and definitely you are 真牛逼

[@adityakulkarni2764]

Hi neetcode, that was quite an explanation, actually there is part 2 also of this problem, problem no. 229. Plz upload it's video, peace

[@VishalKumar-kr9me]

Is it expected to come with Moore algorithm solution in the interview?

[@Raj10185]

AMzing solution thanks neetcode

[@engineerboi3234]

Best Channel for dsa

[@akhma102]

Brilliant solution! Thank you for sharing that!

[@MP-ny3ep]

Amazing solution as always !!!

[@flatmapper]

Fantastic second solution, thanks

[@smirk6154]

Beautiful explanation as always.

[@yodasonics9799]

My implementation of the 2nd solution ended up using slightly more memory(20mb) than my hashmap solution (19.9mb) Is that because the test cases didn't push the hashmap to its worst case O(n) or is that just leetcode being leetcode

[@siyinglin3813]

Thanks for the explanation but the second method still seems O(n) though. Is there any O(1) solution?

[@atrus3823]

Great video, good explanation, and interesting algorithm, but what is with people making everything a class? You don’t use self at all, so your one method is basically a static method, which are essentially useless in Python. However, because you haven’t marked it static, you need to instantiate the class (or call it statically with something passed in as self), which is pointless, since it has no data or state. There is no harm in defining module-level functions. I try to avoid classes in Python, and only use them when they are providing some significant advantage.

[@tanyaahuja8923]

Love this channel!

[@sriramkrishnamurthy4473]

and wow, i love you xD

[@servantofthelord8147]

Excellent vid as usual. I'm curious - did defaultdicts not exist at the time this video was made?

[@brandondavison3099]

I almost has the O(n) time and O(1) solution. I was able to code it myself after watching half the video but mine is different. def majorityElement(self, nums: List[int]) -> int: res, count = nums[0], 1 for i in range(1, len(nums)): count += 1 if nums[i] == res else -1 if count == 0: res = nums[i] count = 1 return res

[@sahilchauhan3154]

can we just sort the array and then apply the algo it will make it easier

[@marconicolodi7937]

this follow up algorithm is very cool

[@stevenwang3396]

Very clever, I love it!

[@dantonddsa]

Would I not require an O(n) algorithm to assert that the majority element exists in the array?

[@Erlisch1337]

what even is your question?

[@jst8922]

What NeetCode did on 9:11 it is called "Moore’s Voting Algorithm in O(1) space" kzbin.info/www/bejne/rXWal6ZrhcSAjNE 11:26 when counter goes back to 0 with current candidate for majority element , then the new candidate (next in the line) for majority element is selected.

[@lydiajin187]

Thank you so much! Your videos helped a lot, really appreciate the detailed explanations.

[@PremPal-uy4nm]

""" My Notes for this problem Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. """ """ Approach 1: Hash Table Tc: O(n) & SC:o(n) #1. Basically, we are using hash table to keep track of occurance of particualar item in array. we do this by storing record in this format ht={item:no of occurrence} #2. While visting every item we increase it no of occurrence by 1. and if it is the new item that we have just encountered then we will set no of ocuurance to 1. #3. Now we will check for the current item's no of occurrence. If we found no of occurrence is more than *max appearance of any item encountered so far* then it means our current item on which we are iterating will be our current most occurred value. This make sense but one question here. How do we know what is the max appearance of any item so far? #4. Every time we visit the item, we compare the current item's ocuurnace to prvious max apperance of any item so far. Which ever will be bigger that will be our max appearance for any item so far. In our next iteration we will use this value to decide if the new item worthy to become most occured item or not so far. """ def majorityElement(nums): ht={} maxCount,res=0,0 for n in nums: ht[n]=1+ ht.get(n,0) #1 & #2 if ht[n]>maxCount: #3 res=n maxCount=max(ht[n],maxCount) #4 return res print(majorityElement([3,2,3])) 3 """ Approach 2: Boyer Moore's Algorithm TC: O(n) & SC:(1) 1. Basically it is the game of + and -. 2.Intially we asume first item is our most occurred value. 3. Every time we visit new item we ask ourself this question. Is this the same item which i visited previously? - If yes, then this item has a chance to become the most occurred value so I will increase its count by one. - If no, then it means this item might not be the most occurred value, so I will decrease the counter by one. 4. If my inital asumption is wrong then at some point my count will become 0. Means, - My intial asumption may or may not be true in future. so We need to rethink about this. - We decided to bet on the next upcoming item and repeat form step 1 to 4. """ def majorityElement(nums): res,count=0,0 for n in nums: if count==0: #2 res=n #4 if n==res: #3 count+=1 else: count-=1 return res print(majorityElement([3,2,3]))

[@akhmadillom]

How do you come up with such algorithms? Any book recommendation or anything you found helpful in your journey?

[@amvids9348]

i dont think neetcode came up with the soln, he too must have learnt about it from somewhere

[@MaxPotion001]

u could also sort the array and then return the middle element since the majority is always gonna be more than half of the array.

[@SudiptaKarmakar87]

n-logn since comparison based search can yield that as best result, and cardinality is infinite.

[@unitycatalog]

If the majority always exists the median will be that majority. We know how to find median in o(n)

[@crosswalker45]

thankyou so much...u deserve many subs

[@ijazm]

Sort the array in place and then just return the value at the middle.

[@prakhargupta1745]

that will be O(nlogn) , the follow up question requires an approach with O(n) complexity

[@kentsu1254]

what about input [1,1,2,3,4], your second algorithm return 4.. am I missing something

[@And1997Ruz]

Yes, you are 1 is seen more than any other number in the array, sure. But it doesn't make it a majority, I guess. Since it's only seen 2 times, which is not more than 50% (not enough to be the majority) So your proposed input is incorrect

[@snubefi]

it wasn better to initialize res with None value instead of 0?

[@madhumithakolkar_]

This algorithm fails for the example - [2,2,1,1,3,1], it will have the last value of candidate as 3, but the answer should actually be 1.

[@imaadf5124]

The 2nd solution was genius

[@harishankarkarthik3570]

Proof of correctness of Bayer-Moore algorithm (By Strong Induction on the length of the sequence): Base Case (n = 1): If there is only one element, then it is trivially the majority element and the one that the algorithm returns. Therefore, the algorithm satisfies the base case. Induction Hypothesis: Let the algorithm be valid for all sequences whose size is strictly less than k, where k >= 2. Induction Step: Let c be the first element of the sequence and index i be the location where the count of c becomes zero for the first time (when you run the algorithm). Running the algorithm from index i + 1 to the end, it is identical to running the algorithm afresh on this subsequence. Therefore, if we can show that the majority element of the entire sequence is also the majority element of this subsequence, then by the induction hypothesis our algorithm will return this value and our proof is complete. Until index i, the occurence of c = occurences of all other elements. Therefore, the maximum reduction in the count of the majority element is (i + 1)/ 2, whereas the reduction of sequence size is (i + 1). Therefore, the majority element remains unchanged and so the proof is complete.

[@shivangrathore]

I couldn't optimize my original solution, and I wasn't sure how to improve it further. So, I searched for help on needcode. How do you manage to come up with such highly optimized solutions? class Solution: def majorityElement(self, nums: List[int]) -> int: nums.sort() check = len(nums) // 2 for i in range(len(nums) - check): if nums[i] == nums[i + check]: return nums[i] return nums[0]

[@sanooosai]

great thank you

[@anantprusty2391]

I tried this logic with input [2,2,2,2,3,3,4,5,1,1,1] where 2 is the majority. But the solution gives output as 1. Am I missing something?

[@binguuuuuuu]

Yes this case it wont work. But problem statement says majority vote has to be bigger than n/2. So in your test case 2 is not higher than n/2 which wont work

[@rayyanhussain6805]

Hey there! Nice explanation! Understood everything. But how do we find majority element if there is no assurance that there will be a majority element in each test case?

[@deekshithshetty4090]

Do the same thing, but just before returning the number check the number of times that particular number is appearing (makes the time to O(2n) ), if it is greater than n/2 return element else return -1.

[@elezavala]

will you do majority element II? And once again, amazing video! c:

[@SudiptaKarmakar87]

Nice, learned something new. I thought you would go the quickselect median route.

[@sauravchandra10]

I think the best way to learn a new language is to solve some DSA problems like these

[@gauss8134]

nice video

[@dallasmilanista8291]

Hey, can you clear my doubt! Can I just sort the array and use a loop to increment count if the next element is equal to current element? This way, I'd still be using Constant space and Linear time right?

[@ishanrathi3790]

When you sort, you are using nlogn time not linear

[@小二杨-o5r]

When you sort it, you just need to return the middle element without using a loop

[@vert_sr]

do find the celebrity, its a fun one :)

[@NeetCode]

Sure, I'll look into it.

[@vert_sr]

@@NeetCode whens the linkedin reveal man haha

[@K9Megahertz]

The real challenge is finding where you would use this in practice.

[@amrholo4445]

Thanks a lot, sir 💕

[@elvissam1401]

Awesome!

[@MartinCharles]

trust me bro it works

[@symbol767]

I would never have come up with that follow up solution on an interview...

[@michaelyao9389]

This is called `voting algorithm`. The majority party will win eventually.

[@HarshitKumar-bx3pt]

NeetCode is essential for leetcode

[@bolt6572]

Ty man!!!!!

[@theteacher010]

Don't think I could have come up with the algorithm on the fly in an interview. Is there a list of esoteric algorithms that we should brush up on just in case? XD

[@adilsaju]

amazinggg!!!!!!!!

[@samuelmayna]

I don't know how someone would come up with the follow up solution in 20ish or 30ish minutes interview.FAANG is a serious joke.I only LC only for the money.

[@ganjinaveen7338]

return max(set(nums),key=nums.count) OR return Counter(nums).most_common(1)[0][0] OR return mode(nums

[@chiraagpala3243]

Are you going to be doing more problems like this one with not so commonly known algorithms? or do you think you will ever go back to making videos for hard tagged problems again?

[@johns3641]

Hi Neetcode, can you please do LC 673. Number of Longest Increasing Subsequence? I can't find a good video of it online and am super confused. I think you'd do a great job explaining it :)

[@NeetCode]

Interesting problem, I'll try to do it soon!

[@numberonep5404]

This is soooo cool :X

[@doublegdog]

man i wish my recent microsoft interview had this question haha. love your channel btw. Curious on your thoughts. I think I did well on 2/4 interviews. do you guys think i will get the job? still waiting to hear back.

[@robin23200]

Did you get it?

[@doublegdog]

@@robin23200 I didn't get the microsoft offer, but I did get an offer from amazon :)

[@robin23200]

@@doublegdog that’s awesome! Do you mind sharing your interview process. Do you remember the questions that were on OA and the on-site. We’re they similar to leetcode?

[@doublegdog]

@@robin23200 i signed an NDA, but they were all leetcode-like, basically what neetcode posts about.

[@StfuSiriusly]

@@doublegdog are they really going to know if you post the questions?

[@HarishPentapalli]

Why can we not use statistics.mode() function on the given list?

[@phardik5610]

Hi, but will that algo work if we have to return -1 in case , there are no majority elements occuring more than n/2 times?!

[@yashpokar]

How could one solve this in the 30 minutes interview, if seeing for the first time

[@isaacpak1628]

"The Moore optimal solution"

[@prettypasta6230]

god :)

[@arushisharma3183]

The follow-up solution fails for such a test case: [1, 13]. The answer would become 1, but there's actually no majority element.

[@parasgaba7809]

Becuase that's not a valid test case. The input nums has to has one majority element, that's the constraint for this leetcode problem.

[@eamytb]

“Believe me it works” is not a good explanation

Be aware, Boyer-Moore majority vote algorithm won't guarantee to return always correct element because from (en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm#Description); "Even when the input sequence has no majority, the algorithm will report one of the sequence elements as its result. However, it is possible to perform a second pass over the same input sequence in order to count the number of times the reported element occurs and determine whether it is actually a majority. This second pass is needed, as it is not possible for a sublinear-space algorithm to determine whether there exists a majority element in a single pass through the input." Of course this is not related this Leetcode problem because in its explanation; "You may assume that the majority element ALWAYS exists in the array."

[@Douglasfaparanhos]

He made that clear on the video!

[@SudiptaKarmakar87]

Even with second pass its still linear time, const space.

@@SudiptaKarmakar87 Yeap

[@tapashmajumder2377]

Why you don't pronounce the T's? Your "what" sounds like "wha"? Wha happened to the T at the end? 🙂