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!
@captainmarvel38348 ай бұрын
Man, this your sentence describes this solution so neatly 😮🔥
@vitzal36915 ай бұрын
I needed this explanation, thanks (:
@user-su9vz7ww6pАй бұрын
"Algorithm is not possible to come up with unless you have solved this question before" that is actually motivating
@jewsefjones23 сағат бұрын
Thank you for the algo name.
@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.
@FullMetalAlgorithmist11 ай бұрын
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-george11 ай бұрын
@@FullMetalAlgorithmist Unwarranted
@KM-zd6dq10 ай бұрын
@@FullMetalAlgorithmist You said the truth in the nicest way possible
@drowningpool835610 ай бұрын
@@FullMetalAlgorithmist u were indeed brutal, but i completely agree.
@efefeyzimantaroglu46762 жыл бұрын
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.
@sudhanshushekhar422211 ай бұрын
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..
@kamalasowmya71209 ай бұрын
Very smart!
@Douglasfaparanhos2 жыл бұрын
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 👏👏
@bolhoso2 жыл бұрын
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.
@CEOofTheHood2 жыл бұрын
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.
@NeetCode2 жыл бұрын
Agree, if not for stressful interviews, I think most people will kinda like leetcode.
@Deschuttes2 жыл бұрын
I like getting blown in general but yes, some leetcode problems are actually kind of neet.
@user-id5wg7cz9b2 ай бұрын
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
@daiki25096 ай бұрын
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.
@sraghav426 ай бұрын
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.
@algoaddicts94737 ай бұрын
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.
@geniusinmaking6 сағат бұрын
the question already takes care of that, we are given that a majority element (appearing more than n/2 times) is guaranteed
@pnthrillz2 ай бұрын
Dude your every algo explanation is top notch! Best in the business! Please continue this
@pawelpow8 ай бұрын
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
@NguyenLe-pu6mr2 жыл бұрын
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.
@AminABbasi29 күн бұрын
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 ```
@grok_coder20 күн бұрын
This is such an elegant solution! Thanks!
@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.
@arihantd Жыл бұрын
My approach was return the middle of the sorted array, const space but nlogn time
@iamstudying3892 ай бұрын
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
@yuvrajkukreja124826 күн бұрын
What about [2,2,1,1,1,7,9] will it give correct answer?? The second algorithm???
@adityakulkarni27642 жыл бұрын
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
@hotskull155472 ай бұрын
It's crazy because I was thinking of this but could never find a way to implement it, good video!
@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)?
@shivikamishra36902 жыл бұрын
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.
@EzWorkzzStudios8 ай бұрын
That second solution was absolutely magic at first haha. Got the hashmap one on LC, came here for the optimized one. Too intuitive.
@ronnier3209 ай бұрын
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
@surengriezy702 ай бұрын
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
@stevenwang33962 жыл бұрын
Very clever, I love it!
@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
@lydiajin187 Жыл бұрын
Thank you so much! Your videos helped a lot, really appreciate the detailed explanations.
@akhma102 Жыл бұрын
Brilliant solution! Thank you for sharing that!
@dinesh.p86422 жыл бұрын
Brother, Thanks for the video.
@putin_navsegda648711 ай бұрын
great ! Thank you ! Dictionary solution was pretty obviuous
@VishalKumar-kr9me Жыл бұрын
Is it expected to come with Moore algorithm solution in the interview?
@MP-ny3ep11 ай бұрын
Amazing solution as always !!!
@servantofthelord81475 ай бұрын
Excellent vid as usual. I'm curious - did defaultdicts not exist at the time this video was made?
@shuoliu3546 Жыл бұрын
After coding by myself, I checked your video, and definitely you are 真牛逼
@smirk615411 ай бұрын
Beautiful explanation as always.
@flatmapper Жыл бұрын
Fantastic second solution, thanks
@licokr6 ай бұрын
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...
@user-sf2yl2yw7z9 ай бұрын
The follow-up was amazing
@ladydimitrescu1155 Жыл бұрын
what a beautiful algorithm and so well explained
@tanyaahuja89232 жыл бұрын
Love this channel!
@sriramkrishnamurthy44732 жыл бұрын
and wow, i love you xD
@elezavala2 жыл бұрын
will you do majority element II? And once again, amazing video! c:
@Raj10185 Жыл бұрын
AMzing solution thanks neetcode
@akhmadillom Жыл бұрын
How do you come up with such algorithms? Any book recommendation or anything you found helpful in your journey?
@amvids93487 ай бұрын
i dont think neetcode came up with the soln, he too must have learnt about it from somewhere
@atrus38235 ай бұрын
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.
@engineerboi32342 жыл бұрын
Best Channel for dsa
@harishankarkarthik35709 ай бұрын
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.
@jst89227 ай бұрын
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.
@MaxPotion0012 жыл бұрын
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.
@SudiptaKarmakar872 жыл бұрын
n-logn since comparison based search can yield that as best result, and cardinality is infinite.
@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
@crosswalker452 жыл бұрын
thankyou so much...u deserve many subs
@unitycatalog2 жыл бұрын
If the majority always exists the median will be that majority. We know how to find median in o(n)
@yodasonics979911 ай бұрын
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
@sanooosai6 ай бұрын
great thank you
@rayyanhussain68052 жыл бұрын
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.
@bolt65724 ай бұрын
Ty man!!!!!
@dantonddsa11 ай бұрын
Would I not require an O(n) algorithm to assert that the majority element exists in the array?
@Erlisch13377 ай бұрын
what even is your question?
@vert_sr2 жыл бұрын
do find the celebrity, its a fun one :)
@NeetCode2 жыл бұрын
Sure, I'll look into it.
@vert_sr2 жыл бұрын
@@NeetCode whens the linkedin reveal man haha
@marconicolodi79372 жыл бұрын
this follow up algorithm is very cool
@amrholo44452 жыл бұрын
Thanks a lot, sir 💕
@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]
@dallasmilanista82912 жыл бұрын
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?
@ishanrathi37902 жыл бұрын
When you sort, you are using nlogn time not linear
@user-dk4on9xj7b2 жыл бұрын
When you sort it, you just need to return the middle element without using a loop
@sahilchauhan3154 Жыл бұрын
can we just sort the array and then apply the algo it will make it easier
@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
@SudiptaKarmakar872 жыл бұрын
Nice, learned something new. I thought you would go the quickselect median route.
@snubefi10 ай бұрын
it wasn better to initialize res with None value instead of 0?
@theteacher01011 ай бұрын
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
@madhumithakolkar_5 ай бұрын
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.
@anantprusty23915 ай бұрын
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?
@bilguunbatjargal6405 ай бұрын
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
@adilsaju2 ай бұрын
amazinggg!!!!!!!!
@elvissam1401 Жыл бұрын
Awesome!
@imaadf51242 жыл бұрын
The 2nd solution was genius
@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
@sauravchandra106 ай бұрын
I think the best way to learn a new language is to solve some DSA problems like these
@MartinCharles25 күн бұрын
trust me bro it works
@K9Megahertz7 ай бұрын
The real challenge is finding where you would use this in practice.
@symbol7672 жыл бұрын
I would never have come up with that follow up solution on an interview...
@numberonep54042 жыл бұрын
This is soooo cool :X
@gauss8134 Жыл бұрын
nice video
@chiraagpala32432 жыл бұрын
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?
@johns36412 жыл бұрын
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 :)
@NeetCode2 жыл бұрын
Interesting problem, I'll try to do it soon!
@HarshitKumar-bx3pt11 ай бұрын
NeetCode is essential for leetcode
@yashpokarАй бұрын
How could one solve this in the 30 minutes interview, if seeing for the first time
@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.
@doublegdog2 жыл бұрын
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.
@robin232002 жыл бұрын
Did you get it?
@doublegdog2 жыл бұрын
@@robin23200 I didn't get the microsoft offer, but I did get an offer from amazon :)
@robin232002 жыл бұрын
@@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?
@doublegdog2 жыл бұрын
@@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?
@michaelyao93892 жыл бұрын
This is called `voting algorithm`. The majority party will win eventually.
@isaacpak16284 ай бұрын
"The Moore optimal solution"
@HarishPentapalli2 жыл бұрын
Why can we not use statistics.mode() function on the given list?
@ganjinaveen7338 Жыл бұрын
return max(set(nums),key=nums.count) OR return Counter(nums).most_common(1)[0][0] OR return mode(nums
@phardik56102 жыл бұрын
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?!
@prettypasta62302 жыл бұрын
god :)
@eamytb11 күн бұрын
“Believe me it works” is not a good explanation
2 жыл бұрын
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."
@Douglasfaparanhos2 жыл бұрын
He made that clear on the video!
@SudiptaKarmakar872 жыл бұрын
Even with second pass its still linear time, const space.
2 жыл бұрын
@@SudiptaKarmakar87 Yeap
@tapashmajumder23779 ай бұрын
Why you don't pronounce the T's? Your "what" sounds like "wha"? Wha happened to the T at the end? 🙂
@arushisharma31832 жыл бұрын
The follow-up solution fails for such a test case: [1, 13]. The answer would become 1, but there's actually no majority element.
@parasgaba78092 жыл бұрын
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.
@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]))