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
8 ай бұрын
Man, this your sentence describes this solution so neatly 😮🔥
@vitzal3691
5 ай бұрын
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
@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
10 ай бұрын
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
10 ай бұрын
@@FullMetalAlgorithmist Unwarranted
@KM-zd6dq
10 ай бұрын
@@FullMetalAlgorithmist You said the truth in the nicest way possible
@drowningpool8356
10 ай бұрын
@@FullMetalAlgorithmist u were indeed brutal, but i completely agree.
@efefeyzimantaroglu4676
2 жыл бұрын
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
10 ай бұрын
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
8 ай бұрын
Very smart!
@Douglasfaparanhos
2 жыл бұрын
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
2 жыл бұрын
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.
@CEOofTheHood
2 жыл бұрын
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
2 жыл бұрын
Agree, if not for stressful interviews, I think most people will kinda like leetcode.
@Deschuttes
2 жыл бұрын
I like getting blown in general but yes, some leetcode problems are actually kind of neet.
@daiki2509
6 ай бұрын
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
6 ай бұрын
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.
@pnthrillz
Ай бұрын
Dude your every algo explanation is top notch! Best in the business! Please continue this
@grok_coder
7 күн бұрын
This is such an elegant solution! Thanks!
@user-id5wg7cz9b
2 ай бұрын
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
@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.
@pawelpow
8 ай бұрын
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-pu6mr
2 жыл бұрын
This is the first time I comment on a KZitem video, this channel is amazing. U got an answer for every single question when I watching your video.
@AminABbasi
17 күн бұрын
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 ```
@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
@hotskull15547
2 ай бұрын
It's crazy because I was thinking of this but could never find a way to implement it, good video!
@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
@EzWorkzzStudios
8 ай бұрын
That second solution was absolutely magic at first haha. Got the hashmap one on LC, came here for the optimized one. Too intuitive.
@yuvrajkukreja1248
14 күн бұрын
What about [2,2,1,1,1,7,9] will it give correct answer?? The second algorithm???
@algoaddicts9473
7 ай бұрын
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.
@shivikamishra3690
2 жыл бұрын
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.
@stevenwang3396
2 жыл бұрын
Very clever, I love it!
@ronnier320
8 ай бұрын
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
@akhma102
Жыл бұрын
Brilliant solution! Thank you for sharing that!
@dinesh.p8642
2 жыл бұрын
Brother, Thanks for the video.
@MP-ny3ep
10 ай бұрын
Amazing solution as always !!!
@user-sf2yl2yw7z
9 ай бұрын
The follow-up was amazing
@ladydimitrescu1155
Жыл бұрын
what a beautiful algorithm and so well explained
@smirk6154
10 ай бұрын
Beautiful explanation as always.
@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
@shuoliu3546
Жыл бұрын
After coding by myself, I checked your video, and definitely you are 真牛逼
@flatmapper
Жыл бұрын
Fantastic second solution, thanks
@putin_navsegda6487
11 ай бұрын
great ! Thank you ! Dictionary solution was pretty obviuous
@lydiajin187
Жыл бұрын
Thank you so much! Your videos helped a lot, really appreciate the detailed explanations.
@tanyaahuja8923
2 жыл бұрын
Love this channel!
@sriramkrishnamurthy4473
2 жыл бұрын
and wow, i love you xD
@jst8922
7 ай бұрын
What NeetCode did on 9:11 it is called "Moore’s Voting Algorithm in O(1) space" kzitem.info/news/bejne/2HptzKdriZF-iaQ 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.
@unitycatalog
2 жыл бұрын
If the majority always exists the median will be that majority. We know how to find median in o(n)
@engineerboi3234
2 жыл бұрын
Best Channel for dsa
@elezavala
2 жыл бұрын
will you do majority element II? And once again, amazing video! c:
@licokr
5 ай бұрын
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...
@Raj10185
Жыл бұрын
AMzing solution thanks neetcode
@atrus3823
4 ай бұрын
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.
@chungu5824
11 ай бұрын
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)?
@sanooosai
5 ай бұрын
great thank you
@K9Megahertz
7 ай бұрын
The real challenge is finding where you would use this in practice.
@VishalKumar-kr9me
Жыл бұрын
Is it expected to come with Moore algorithm solution in the interview?
@marconicolodi7937
2 жыл бұрын
this follow up algorithm is very cool
@vert_sr
2 жыл бұрын
do find the celebrity, its a fun one :)
@NeetCode
2 жыл бұрын
Sure, I'll look into it.
@vert_sr
2 жыл бұрын
@@NeetCode whens the linkedin reveal man haha
@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
@crosswalker45
2 жыл бұрын
thankyou so much...u deserve many subs
@sauravchandra10
6 ай бұрын
I think the best way to learn a new language is to solve some DSA problems like these
@bolt6572
4 ай бұрын
Ty man!!!!!
@madhumithakolkar_
4 ай бұрын
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.
@akhmadillom
Жыл бұрын
How do you come up with such algorithms? Any book recommendation or anything you found helpful in your journey?
@amvids9348
7 ай бұрын
i dont think neetcode came up with the soln, he too must have learnt about it from somewhere
@adilsaju
Ай бұрын
amazinggg!!!!!!!!
@amrholo4445
2 жыл бұрын
Thanks a lot, sir 💕
@MartinCharles
13 күн бұрын
trust me bro it works
@imaadf5124
2 жыл бұрын
The 2nd solution was genius
@MaxPotion001
2 жыл бұрын
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
2 жыл бұрын
n-logn since comparison based search can yield that as best result, and cardinality is infinite.
@servantofthelord8147
5 ай бұрын
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
@symbol767
2 жыл бұрын
I would never have come up with that follow up solution on an interview...
@michaelyao9389
2 жыл бұрын
This is called `voting algorithm`. The majority party will win eventually.
@theteacher010
10 ай бұрын
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
@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
@elvissam1401
Жыл бұрын
Awesome!
@anantprusty2391
5 ай бұрын
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?
@bilguunbatjargal640
5 ай бұрын
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
@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
9 ай бұрын
it wasn better to initialize res with None value instead of 0?
@gauss8134
Жыл бұрын
nice video
@dantonddsa
10 ай бұрын
Would I not require an O(n) algorithm to assert that the majority element exists in the array?
@Erlisch1337
6 ай бұрын
what even is your question?
@rayyanhussain6805
2 жыл бұрын
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.
@yodasonics9799
10 ай бұрын
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
@SudiptaKarmakar87
2 жыл бұрын
Nice, learned something new. I thought you would go the quickselect median route.
@dallasmilanista8291
2 жыл бұрын
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
2 жыл бұрын
When you sort, you are using nlogn time not linear
@user-dk4on9xj7b
2 жыл бұрын
When you sort it, you just need to return the middle element without using a loop
@harishankarkarthik3570
8 ай бұрын
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.
@sahilchauhan3154
Жыл бұрын
can we just sort the array and then apply the algo it will make it easier
@isaacpak1628
3 ай бұрын
"The Moore optimal solution"
@numberonep5404
2 жыл бұрын
This is soooo cool :X
@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.
@yashpokar
Ай бұрын
How could one solve this in the 30 minutes interview, if seeing for the first time
@doublegdog
2 жыл бұрын
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
2 жыл бұрын
Did you get it?
@doublegdog
2 жыл бұрын
@@robin23200 I didn't get the microsoft offer, but I did get an offer from amazon :)
@robin23200
2 жыл бұрын
@@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
2 жыл бұрын
@@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?
@johns3641
2 жыл бұрын
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
2 жыл бұрын
Interesting problem, I'll try to do it soon!
@HarshitKumar-bx3pt
10 ай бұрын
NeetCode is essential for leetcode
@chiraagpala3243
2 жыл бұрын
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?
@prettypasta6230
2 жыл бұрын
god :)
@phardik5610
2 жыл бұрын
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?!
@HarishPentapalli
2 жыл бұрын
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
@tapashmajumder2377
9 ай бұрын
Why you don't pronounce the T's? Your "what" sounds like "wha"? Wha happened to the T at the end? 🙂
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."
@Douglasfaparanhos
2 жыл бұрын
He made that clear on the video!
@SudiptaKarmakar87
2 жыл бұрын
Even with second pass its still linear time, const space.
2 жыл бұрын
@@SudiptaKarmakar87 Yeap
@arushisharma3183
2 жыл бұрын
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
2 жыл бұрын
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.
@shivangrathore
11 ай бұрын
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]
@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]))
Пікірлер: 145