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!
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'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".
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 👏👏
@@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.
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.
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
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.
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.
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
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.
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 ```
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)?
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
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...
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)
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
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.
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
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
What NeetCode did on 9:11 it is called "Moore’s Voting Algorithm in O(1) space" th-cam.com/video/wD7fs5P_MVo/w-d-xo.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.
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.
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
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
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?
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]
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.
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
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?
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.
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 :)
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.
@@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?
""" 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
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."
![[FULL EP.73] เปิดบ้าน 70 ล้าน "แป้ง Zbing" ยกมาทั้งญี่ปุ่น l เคหสถานบานปลาย l One Playground](http://i.ytimg.com/vi/YBnJhTt07Pg/mqdefault.jpg)
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 (:
"Algorithm is not possible to come up with unless you have solved this question before" that is actually motivating
Thank you for the algo name.
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 👏👏
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!
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.
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
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.
the question already takes care of that, we are given that a majority element (appearing more than n/2 times) is guaranteed
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.
This is the first time I comment on a TH-cam video, this channel is amazing. U got an answer for every single question when I watching your video.
Dude your every algo explanation is top notch! Best in the business! Please continue this
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
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.
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
Yea, but only if we can have O(n) as our space complexity.
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
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
```
Excellent vid as usual. I'm curious - did defaultdicts not exist at the time this video was made?
This is such an elegant solution! Thanks!
It's crazy because I was thinking of this but could never find a way to implement it, good video!
That second solution was absolutely magic at first haha. Got the hashmap one on LC, came here for the optimized one. Too intuitive.
My approach was return the middle of the sorted array, const space but nlogn time
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
What about [2,2,1,1,1,7,9] will it give correct answer?? The second algorithm???
Is it expected to come with Moore algorithm solution in the interview?
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)?
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
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...
will you do majority element II? And once again, amazing video! c:
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
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
Very clever, I love it!
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.
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
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
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.
What NeetCode did on 9:11 it is called "Moore’s Voting Algorithm in O(1) space"
th-cam.com/video/wD7fs5P_MVo/w-d-xo.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.
Brother, Thanks for the video.
If the majority always exists the median will be that majority. We know how to find median in o(n)
Brilliant solution! Thank you for sharing that!
After coding by myself, I checked your video, and definitely you are 真牛逼
great ! Thank you ! Dictionary solution was pretty obviuous
Beautiful explanation as always.
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.
Amazing solution as always !!!
The follow-up was amazing
what a beautiful algorithm and so well explained
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
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
Thank you so much! Your videos helped a lot, really appreciate the detailed explanations.
Fantastic second solution, thanks
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
Love this channel!
and wow, i love you xD
Would I not require an O(n) algorithm to assert that the majority element exists in the array?
what even is your question?
it wasn better to initialize res with None value instead of 0?
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 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.
can we just sort the array and then apply the algo it will make it easier
do find the celebrity, its a fun one :)
Sure, I'll look into it.
@@NeetCode whens the linkedin reveal man haha
AMzing solution thanks neetcode
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]
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.
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
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?
thankyou so much...u deserve many subs
Nice, learned something new. I thought you would go the quickselect median route.
this follow up algorithm is very cool
The real challenge is finding where you would use this in practice.
Ty man!!!!!
I would never have come up with that follow up solution on an interview...
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
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.
great thank you
The 2nd solution was genius
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 think the best way to learn a new language is to solve some DSA problems like these
Thanks a lot, sir 💕
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?
"""
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]))
How could one solve this in the 30 minutes interview, if seeing for the first time
amazinggg!!!!!!!!
trust me bro it works
This is called `voting algorithm`. The majority party will win eventually.
Awesome!
nice video
This is soooo cool :X
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?!
NeetCode is essential for leetcode
Why can we not use statistics.mode() function on the given list?
return max(set(nums),key=nums.count)
OR
return Counter(nums).most_common(1)[0][0]
OR
return mode(nums
"The Moore optimal solution"
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
god :)
“Believe me it works” is not a good explanation
Why you don't pronounce the T's? Your "what" sounds like "wha"? Wha happened to the T at the end? 🙂
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.