Majority Element - Leetcode 169 - Python

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

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[nvjrane]

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

[pratikshanaik]

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.

[Douglasfaparanhos]

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

[efefeyzimantaroglu]

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

[bolhoso]

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

[CEOofTheHood]

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

[DurgaSivaLokeshTelaprolu]

your dictionary code was bit tricky :)

A simpler code for this would be:

class Solution:
def majorityElement(self, nums: List[int]) -> int:
n = len(nums)
my_dict = {}
for num in nums:
my_dict[num] = 1 + my_dict.get(num, 0)
if my_dict[num] > n/2:
return num

[daiki]

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.

[NguyenLe-pumr]

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

[pnthrillz]

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

[pawelpow]

I came up with this solution before finding out about the Boyer-Moore algorithm. This seems to work and is also linear time complexity with a constant space complexity as I'm doing operations in-place...

def majority(numbers):
if len(numbers) == 1:
return numbers[0]

left, right = 0, 1

while right < len(numbers):
if numbers[left] is None:
left += 1

if numbers[right] is None:
right += 1
continue

if numbers[left] != numbers[right]:
numbers[left] = None
numbers[right] = None

left += 1
right += 1
else:
right += 1

# Return the first non-nil element
for num in numbers:
if num is not None:
return num

[MTX]

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.

[arjn]

For the HashMap solution this was what I came up with. Thoughts?

def majorityElement(self, nums: List[int]) -> int:
# T: O(n) S: O(n)

# Frequency Dictionary to keep track of each num and it's count
# defaultdict(int) initializes each key with default val 0 to avoid KeyError
freqDict = defaultdict(int)

# Majority variable to check the num's count against
majority = len(nums) // 2

# For each number in the array
for i in nums:
# Increment the numm's count in the dictionary
freqDict[i] += 1

# If at any point the num's count passes the majority, return the num
if (freqDict[i] > majority):
return i

[jst]

What NeetCode did on 9:11 it is called "Moore’s Voting Algorithm in O(1) space"


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.

[adityakulkarni]

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 <3

[EzWorkzzStudios]

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

[hotskull]

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

[AminABbasi]

Thanks for the Video, indeed I did the first solution but the second seems more efficient.
I it's not necessary to compare "n == res" since the count is the representation of majority element not element itself, this is my code:

```
count = 0

for num in nums:
if count == 0:
result = num
count += 1
else:
count += 1

return result
```

[shivikamishra]

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

[aviraljanveja]

It is difficult to come up with something like Boyer Moore on the spot. I think most people intuitively come up with the dictionary / hash table based solution. Now one advantage there is that it could be faster than boyer moore in the average case as you can return an element as soon as its count is greater than n / 2 without having to traverse through the rest of the array. The boyer moore algorithm on the other hand has to traverse the entire array once.