@@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
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
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.
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
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
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.
@@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
@@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
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
[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.
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
@@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
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
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
i don't understand how we can come up with this in an interview or OA without already knowing it before
That will happen only when you practice and learn the patterns in the questions
that's why you need to prepare and learn especially from neetcode.
@@sambro890 this will not satisfy the O(1) space complexity
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
@@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
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)
Thanks for the daily
It's Boyer Moore's algorithm btw if anyone wants to read up on it.
Boyer Moore. Thanks
Such a beautiful implementation of Boyer Moore's algorithm!
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
Yeah it's definitely more intuitive, but I believe the memory usage is higher with this solution.
@@NeetCodeIO yes. Your solution is better.
neetcode....is a legend
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.
great explanation.
still think the additional condition makes it unnecessarily complicated though
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
thank youuuu
We say hashMap count > 2 because of n/3 or it is just a trick?
yeah because of n/3. if the question asked n/4 we would have used len(hashMap) >3
@@chuckle_pugz96 So generalizing for n/k, would we use len(hashmap) > (k-1) ?
@@plsgivemecat yep correct
if we are using a map how is the space complexity still O(1)..?
at most the size of the map is 3
@@Kan-JenLiu thanks!
Hi guys! How can we replace "if nums.count(n) > len(nums) // 3" in Java without using another loop?
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
Thanks neety, but I'm lacking the intuition in your explanation which I think is very important
hey neetcode solve potd 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
My doubt is cant we do majority element 1 also in this approach
If any one has any idea ,let me know
He already showed it in some other video. Same way, little simpler though
How to solve this with O(1) space?
have two hashmaps of size 3 and return vector of size 2. and follow algo on the viideo.
HashMaps are N space
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.
@@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
@@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
Why don't we need a **deep copy** of the dictionary of new_count here?
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
it definitely works on this example, I would dry run it to prove it to yourself
[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.
@@disenchanted_dove in the end he is checking again to verify if the element frequency is greater than n/3 using count function
solve unique binary trees II
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
I'm tired of skipping videos with Indian accents. You saved me bro
The guy is still an indian though, there's no escape
I guess knowledge is more important than accent....sorry we are smarter than wherever you're from.😅
@@shubham_bit2lol there is no escape 😂😂😂
@@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
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
extra space needed
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
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
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
@@shubhamraj25 How would his gabriel is sol be o(n) space?