Majority Element II - Leetcode 229 - Python

[@anonymoussloth6687]

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

[@shyam4034]

That will happen only when you practice and learn the patterns in the questions

[@pacerq5337]

that's why you need to prepare and learn especially from neetcode.

[@li-xuanhong3698]

@@sambro890 this will not satisfy the O(1) space complexity

[@leeroymlg4692]

there are easier solutions to come up with instead, but not as efficient. I'm sure it's rare to come up with the perfect solution in an interview

[@buttofthejoke]

​@@pacerq5337yeah but that only means you've mugged up the answers. that doesn't mean that you're a better developer than someone who just missed visiting this problem

[@lenzvital2776]

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)

[@UpTwist]

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

[@ngneerin]

Boyer Moore. Thanks

[@sambro890]

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

[@NeetCodeIO]

Yeah it's definitely more intuitive, but I believe the memory usage is higher with this solution.

[@sambro890]

@@NeetCodeIO yes. Your solution is better.

[@IntelliStar_]

Such a beautiful implementation of Boyer Moore's algorithm!

[@dumbfailurekms]

neetcode....is a legend

[@tanish5662]

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.

[@Pegasus02Kr]

great explanation. still think the additional condition makes it unnecessarily complicated though

[@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

[@ronbuchanan5432]

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

[@infoknow3278]

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

[@rebellious_703]

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

[@chuckle_pugz96]

yeah because of n/3. if the question asked n/4 we would have used len(hashMap) >3

[@plsgivemecat]

@@chuckle_pugz96 So generalizing for n/k, would we use len(hashmap) > (k-1) ?

[@chuckle_pugz96]

​@@plsgivemecat yep correct

[@satwiktatikonda764]

My doubt is cant we do majority element 1 also in this approach If any one has any idea ,let me know

[@ngneerin]

He already showed it in some other video. Same way, little simpler though

[@batman8377]

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

[@sangeethajain7446]

u can traverse through the list again for counting the possible 2 most frequent elements. any inbuilt function too will run through the loop to give u counts the algorithm would still be O(n) asymptomatically and the total work leetcode will do while submitting will be in its constraints ,No TLE

[@pacerq5337]

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

[@adityaparab4314]

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

[@Kan-JenLiu]

at most the size of the map is 3

[@adityaparab4314]

@@Kan-JenLiu thanks!

[@ignitedminds6164]

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

[@littletiger1228]

extra space needed

[@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

[@NeetCodeIO]

it definitely works on this example, I would dry run it to prove it to yourself

[@disenchanted_dove]

[2 , 1 , 1 , 3 , 1 , 4 , 5 , 6] index 0 - map {2: 1} index 1 - map{2: 1, 1: 1} index 2 - map {2: 1, 1: 2} index 3 - map { 1: 1 } index 4 - map {1 : 2} index 5 - map { 1: 2, 4: 1} index 6 - map { 1: 1} index 7 - map {1: 1, 6: 1} see if you got these right. you are probably including the current iteration element in map after decrementing the counters which is not correct.

[@melvinjijumathew3022]

@@disenchanted_dove in the end he is checking again to verify if the element frequency is greater than n/3 using count function

[@ttheguyy]

How to solve this with O(1) space?

[@DeathSugar]

have two hashmaps of size 3 and return vector of size 2. and follow algo on the viideo.

[@Akhillbj]

HashMaps are N space

[@NeetCodeIO]

Hashmaps are not necessarily O(n) space. In this problem it's important to "remove" all elements with a count of 0, after the size of the map grows to 3.

[@DeathSugar]

@@Akhillbj if you wipe/pop elements from it at the certain size it's pretty much constant to the named size. Think of it as some cache not the regular hashmap

[@reggie06]

@@NeetCodeIO hey neetcode, I have noticed not a lot of people have a great understanding of the concept of space and time complexities, with there being a lot of confusions such as seeing a double for loop and assuming thats o(n^2) in time, or a hashmap/stack/any other data structure and assuming that means we are using at least linear space. I think it would be very valuable discussing what complexities mean in algorithms, how to evaluate them, and how they can be useful. It would also be interesting in hearing what you think the importance of them in terms of tech interviews and how likely someone will have to explain the space complexity of their code for example

[@ihsannuruliman4005]

solve unique binary trees II

[@sambro890]

class Solution: def generateTrees(self, n: int) -> List[Optional[TreeNode]]: dp = {} def memo(start, end): all_trees = [] if start > end: return [None,] elif (start, end) in dp: return dp[(start, end)] else: for i in range(start, end + 1): left = memo(start, i - 1) right = memo(i + 1, end) for r in right: for l in left: current = TreeNode(i) current.left = l current.right = r all_trees.append(current) dp[(start, end)] = all_trees return dp[(start, end)] return memo(1, n) unique binary trees II using memoization

[@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

[@satwiktatikonda764]

Tc is O(N) for iterrating over nums array and o(N) for count so final TC is o(n^2) wch is not desired

[@shubhamraj25]

it's def unoptimized lol, the follow up asks for a O(1) SC solution and the one you are giving is O(n) space complexity

[@reggie06]

@@shubhamraj25 How would his gabriel is sol be o(n) space?

[@Александр-ф9в3х]

I'm tired of skipping videos with Indian accents. You saved me bro

[@shubham_bit2]

The guy is still an indian though, there's no escape

[@adityaparab4314]

I guess knowledge is more important than accent....sorry we are smarter than wherever you're from.😅

[@illu1na]

​@@shubham_bit2lol there is no escape 😂😂😂

[@reggie06]

@@adityaparab4314 To be fair, there is a ton of computer science youtubers with very thick indian accents where it seems like half of the time they aren't even speaking english. So I can definitely feel the main commenter on this one haha