Majority Element - Leetcode 169 - Python
Vložit
- čas přidán 28. 06. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/majorit...
0:00 - Read the problem
1:40 - Drawing Explanation
2:24 - Coding Solution #1
5:23 - Explain Follow-up
12:35 - Coding Follow-up
leetcode 169
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
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!
Man, this your sentence describes this solution so neatly 😮🔥
I needed this explanation, thanks (:
How do people come up with those solutions. It's like magic!
True. Smart people out there.
This is a test if someone had seen the question.I don't think someone can come up with the solution on their own.
@@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.
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..
Very smart!
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.
I don't know you but don't give up it gets better.
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".
@@FullMetalAlgorithmist Unwarranted
@@FullMetalAlgorithmist You said the truth in the nicest way possible
@@FullMetalAlgorithmist u were indeed brutal, but i completely agree.
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 👏👏
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.
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.
Agree, if not for stressful interviews, I think most people will kinda like leetcode.
I like getting blown in general but yes, some leetcode problems are actually kind of neet.
This is the first time I comment on a CZcams video, this channel is amazing. U got an answer for every single question when I watching your video.
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.
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.
Brilliant solution! Thank you for sharing that!
It's crazy because I was thinking of this but could never find a way to implement it, good video!
Dude your every algo explanation is top notch! Best in the business! Please continue this
Thank you so much! Your videos helped a lot, really appreciate the detailed explanations.
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
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.
My approach was return the middle of the sorted array, const space but nlogn time
Very clever, I love it!
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
Amazing solution as always !!!
Beautiful explanation as always.
Fantastic second solution, thanks
what a beautiful algorithm and so well explained
That second solution was absolutely magic at first haha. Got the hashmap one on LC, came here for the optimized one. Too intuitive.
The follow-up was amazing
great ! Thank you ! Dictionary solution was pretty obviuous
will you do majority element II? And once again, amazing video! c:
Brother, Thanks for the video.
AMzing solution thanks neetcode
After coding by myself, I checked your video, and definitely you are 真牛逼
Thanks a lot, sir 💕
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)?
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
thankyou so much...u deserve many subs
Is it expected to come with Moore algorithm solution in the interview?
Best Channel for dsa
How do you come up with such algorithms? Any book recommendation or anything you found helpful in your journey?
i dont think neetcode came up with the soln, he too must have learnt about it from somewhere
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
Excellent vid as usual. I'm curious - did defaultdicts not exist at the time this video was made?
this follow up algorithm is very cool
Love this channel!
and wow, i love you xD
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?
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.
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?
When you sort, you are using nlogn time not linear
When you sort it, you just need to return the middle element without using a loop
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...
If the majority always exists the median will be that majority. We know how to find median in o(n)
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
this is a simpler and faster solution
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
What NeetCode did on 9:11 it is called "Moore’s Voting Algorithm in O(1) space"
czcams.com/video/wD7fs5P_MVo/video.html
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.
Nice, learned something new. I thought you would go the quickselect median route.
The 2nd solution was genius
I would never have come up with that follow up solution on an interview...
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
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.
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.
Ty man!!!!!
Would I not require an O(n) algorithm to assert that the majority element exists in the array?
what even is your question?
can we just sort the array and then apply the algo it will make it easier
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
This is soooo cool :X
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
great thank you
Sort the array in place and then just return the value at the middle.
that will be O(nlogn) , the follow up question requires an approach with O(n) complexity
Awesome!
do find the celebrity, its a fun one :)
Sure, I'll look into it.
@@NeetCode whens the linkedin reveal man haha
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.
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.
Did you get it?
@@robin23200 I didn't get the microsoft offer, but I did get an offer from amazon :)
@@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?
@@robin23200 i signed an NDA, but they were all leetcode-like, basically what neetcode posts about.
@@doublegdog are they really going to know if you post the questions?
it wasn better to initialize res with None value instead of 0?
I think the best way to learn a new language is to solve some DSA problems like these
what about input [1,1,2,3,4], your second algorithm return 4.. am I missing something
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
The real challenge is finding where you would use this in practice.
nice video
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?!
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 :)
Interesting problem, I'll try to do it soon!
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?
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
amazinggg!!!!!!!!
This is called `voting algorithm`. The majority party will win eventually.
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.
n-logn since comparison based search can yield that as best result, and cardinality is infinite.
Why can we not use statistics.mode() function on the given list?
NeetCode is essential for leetcode
"The Moore optimal solution"
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.
god :)
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?
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.
return max(set(nums),key=nums.count)
OR
return Counter(nums).most_common(1)[0][0]
OR
return mode(nums
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."
He made that clear on the video!
Even with second pass its still linear time, const space.
@@SudiptaKarmakar87 Yeap
The follow-up solution fails for such a test case: [1, 13]. The answer would become 1, but there's actually no majority element.
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.
Why you don't pronounce the T's? Your "what" sounds like "wha"? Wha happened to the T at the end? 🙂
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]
"""
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]))
magic 🪄