Majority Element II - Leetcode 229 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
10:05 - Coding Explanation

leetcode 229

#neetcode #leetcode #python

[anonymoussloth]

i don't understand how we can come up with this in an interview or OA without already knowing it before

[UpTwist]

Thanks for the daily

It's Boyer Moore's algorithm btw if anyone wants to read up on it.

[sambro]

This is my solution using Hashmap and easier to understand

class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
res = []
n = len(nums)
hashmap = {}
for ele in nums:
if ele not in hashmap:
hashmap[ele] = 1
else:
hashmap[ele] += 1
k = n // 3
for key, val in hashmap.items():
if val > k:
res.append(key)
return res

[pasupathi]

Since you have done the hard part, here is java version where I was able to play with streams 🙂
Map<Integer, Integer> h = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
h.merge(nums[i], 1, (a, b) -> a + b);
if (h.size() > 2) {
h.entrySet().removeIf(a -> {
a.setValue(a.getValue() - 1);
return a.getValue() == 0;
});
}
}

if (h.isEmpty()) {
return Collections.emptyList();
}

return -> -> > (nums.length / 3))
.map(a -> a.getKey())

[lenzvital]

def majorityElement(nums):
if not nums:
return []

# 1st pass
count1, count2, candidate1, candidate2 = 0, 0, 0, 1
for n in nums:
if n == candidate1:
count1 += 1
elif n == candidate2:
count2 += 1
elif count1 == 0:
candidate1, count1 = n, 1
elif count2 == 0:
candidate2, count2 = n, 1
else:
count1, count2 = count1-1, count2-1

# 2nd pass
return [n for n in (candidate1, candidate2)
if nums.count(n) > len(nums) // 3]


Space complexity = O(1), Time complexity = O(n)

[ngneerin]

Did not understand half of what you did in code. But I did the same as follows:
def majorityElement(nums):
m = {}
for num in nums:
if num in m: m[num] += 1
elif len(m) < 3: m[num] = 1
else:
for k in list(m):
if m[k] == 1: del m[k]
else: m[k] -= 1

n = {}
for num in nums:
if num in n:
n[num] += 1
elif num in m:
n[num] = 1

ans = []
for k, v in n.items():
if v > len(nums) // 3: ans.append(k)
return ans

[tanish]

I have a doubt, I am not sure if people will address but i think if we dont delete an element in hashmap, it will stay there with the content 0. I am not sure how the python backend complier works, but it kind of stricked me. So i used del Dict[key] in my code.

[IntelliStar_]

Such a beautiful implementation of Boyer Moore's algorithm!

[jagdishtirumala]

python hashmap solution
```
from collections import Counter

class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
frequency = Counter(nums)
check = len(nums)/3
return [key for key, values in frequency.items() if values > check]
```

[ronbuchanan]

Thanks neety, but I'm lacking the intuition in your explanation which I think is very important

[PegasusKr]

great explanation.

still think the additional condition makes it unnecessarily complicated though

[rebellious_]

We say hashMap count > 2 because of n/3 or it is just a trick?

[satwiktatikonda]

My doubt is cant we do majority element 1 also in this approach

If any one has any idea, let me know

[infoknow]

hey neetcode solve potd 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

[adityaparab]

if we are using a map how is the space complexity still O(1)..?

[batman]

Hi guys! How can we replace "if nums.count(n) > len(nums) // 3" in Java without using another loop?

[pacerq]

Why don't we need a **deep copy** of the dictionary of new_count here?

[ignitedminds]

class Solution(object):
def majorityElement(self, nums):
n=len(nums)
count={}
result1=n/3
list1=[]
for i in nums:
if i in count:
count[i]+=1
else:
count[i]=1
for key, value in count.items():
if value>result1:
list1.append(key)
else:
pass
return list1

[gabriel-accetta]

Another way of doing it is checking if the count of the current number is equal to len(nums)//3 + 1, if it is you append the number to result

actually i dont know if that solution is worse in some way, im accepting corrections

[shivam-codes]

what if test case is [2, 1, 1, 3, 1, 4, 5, 6], I dont understand how your logic is going to wok here ?? the answer is [1], how is your logic going to get me answer to mentioned test case ? can anyone explain