Started my planned 3 months leetcode journey today using neetcode as guide. Hoping to come back to this comment sometime in December fully prepared for any coding interview 🙏
I got a simple one. Use set and check size of the set each time we insert an element and compare it to the size from the previous iteration. Pseudo Code: prevSize = 0; for (i=0; i
just starting on neetcode website now. Will probably try one problem at a time every few days or more often once i have most of my concepts and basic syntax refreshed :P Hopefully, I can get to the point where I solve few problems a day and just be comfortable at mid-hard level questions. Long way to go, but at least the goal is clear.
@@yashashav_dk3766 I got to solving around 20-25 questions [Did most or all of the Easy level questions] then stopped for now. Just enrolled in Networking Programs [Fast Track - 2 years], planning to see how I do in first semester and depending on that I will either get in co-op and work in IT field and hoping to make use of what I have learned [Programming from prev. degree] and continuing from there. Unfortunately, I tend to slack of when I try to learn by myself. So, this is just my way of forcing myself to discipline myself :P I hope others are doing better than me.
Thank you! I solved the problem with all these approaches on my own, but each time I couldn't achieve low consumption of both cpu and memory. Then I decided to look at the solutions, and was surprised that there is no ideal solution. Only compromises. Valuable lesson for me.
Hashmap has a key value association whereas hashset is only a key. In this case, we just need to know the existence of such a key in the array so hashset here is more appropriate because the value field would be useless to us. In short, if you need to map keys to values use hashmap; if you just need keys, use hashset.
Hmmm I'm not sure if I'm right about this but I think the "in" operator as in "if n in hashset" has a worst-case of O(n) which in your case since it is in a loop would be a total worst-case of O(n^2). I used the same idea you explained in the video (but implemented differently without the "in" operator) and got a faster time than you did 116ms average on 3 runs which apparently is faster than 86.62% of solutions. So, don't assume that checking for the existence of an element in a set is O(1). Instead, you can use a dictionary with a default value because rather than have to scan though all values (O(n) as in the "in" operator does) you simply hash your value (one way function) which is truly O(1). FULL CODE: class Solution: def containsDuplicate(self, nums: List[int]) -> bool: logged = {} for num in nums: logged[num] = logged.get(num,0) + 1 # returns 0 if key doesn't have a value yet and then we add 1 to indicate we've logged this value if logged[num] > 1: #value has showed up at least once before return True return False
no dude... checking if an item is in a hashset is O(1) time complexity. similarly checking if an item is in hashmap also has O(1) time complexity. your time running faster means nothing because they'd have a different of like 15ms, and at that point the difference is so small it's just computer error, you didn't make an any faster solution. and of course you wouldn't know that bc the concept that 115ms leetcode algo is same as 130ms leetcode algo is probably more advanced topic than O(1) hashset look up. Because you might assume the leetcode website and machine are infallible and perfect but the reality is, the computer just isn't that accurate time-wise when you talk about differences of 15ms. Anyways comparing algorithms not in time complexity but because of how leetcode ran it is pretty stupid. Only novices care a lot about leetcode time and %. They rly only care about time complexity. In this case it O(n), not O(n ^ 2). lol.
Why would the "in" operator be O(n) for sets when we know they support O(1) lookup? You went on a wild goose chase I'm afraid. If you run the exact same program several times on Leetcode, you'll often see large variations in execution time. You can't infer from such small differences that "x in set" lookups are O(n) in Python. If you really want to test that, change the set to a list and see what happens -- I just did it and the runtime and got 440ms with a set and a timeout (I think around 3 seconds) with a list. Remember, with big-O complexity we don't care about a slightly different wall clock time, but rather, how quickly the time requirement grows with the input size, so you can't conclude if your program runs slightly faster or slower (my set version is 3 times slower than in this video, even though it's the same program -- probably Leetcode is busier now and that slows things down).
dude, hashset are similar to dictionaries except that the latter permits a value and the set not. Both are O(n), a hashset is not a list so that you scan elements on it one by one to find what you need!! it is in its name, a HASHset, the values are hashed to get the index where they are in the set
Another approach would be to insert the array into the hashset, which would be O(logn) ... and compare the size of hashset with array, if they are equal return false else return true. This would be the fastest in terms of execution I suppose, but would require O(n) space more.
Can you please explain how your solution compares with the following: return set(len(nums)) < len(nums) Since python sets normalize duplicates, if a set length is less than the length of the array itself, it means there were duplicates inside it.
Thanks boss. Ended up writing solution 2 on my own, but knew there had to be something with hash sets. Of course the old addage of "when in doubt, hash it" rung true. Don't know how I didn't see it. Thanks.
By the way, space complexity of the sorting method in Python is O(n) if you use the built-in sort() method, because list.sort() uses timsort under the hood.
I understand that hash sets don't allow duplicates but for this problem why is it necessary to use it (not that it is better not to, just for my own understanding).If you had created an empty list and used the same method would it not have worked the same?
10 months late, but hashes have a much faster lookup time because the index isn't ordered, but instead based on a hashing function. Since lookups happen based on key, you don't need to search the whole hash for your input, you just hash the input (run it through the function) and check that one resulting index. If it's there, it's there. If it's not, it's not in the list. If you used an empty list/array, each lookup to check for a duplicate would take O(N) instead of O(1), since you have to check each list index for your item.
What if we do it like this? class Solution: def containsDuplicate(self, nums: List[int]) -> bool: countMap = {} for number in nums: try: countMap[number] = countMap[number] + 1 return True except KeyError: countMap[number] = 1 return False This way we can avoid the check "if n in hashset" which also takes some time right?
instead of a hashset, i tried using a simple list but that doesnt seem to work for this problem, it throws a Time limit exceeded error, trying to understand why that is. edit: is it because array searching takes more time than set searching?
I don't understand the time complexity in hashset approach. I get that iterating once over it in for loop causes O(n) time complexity. But we are also checking inside of "if", whether the element already exists inside hashset. doesn't it mean, that we have to iterate also over all hashset elements to check if the new element already exists inside?
When I answered this I thought I had a really bad solution since it was bottom 95% in terms of speed but then when I came to the video I had the exact same solution as him. Apparently Leetcode adds more tests over time and getting a high % becomes impossible even if you have the same solution. For anyone reading this its better to understand the time and space complexity than to focus on those mostly worthless numbers on the website. There could be other reasons but running the exact same code as him gives me 700-900ms when in the video it was 131ms.
There is a faster solution. You run 2 pointers, one from index 0 and second from index n-1 in a loop and they meet in the middle. While iterating, add values to the HashSet and check if they exist and return true. When looping in a single direction, the worst case you will get it O(n), with 2 pointers u get O(n/2).
STRANGE!!! for JAVA when you submit on leetcode by declaring HashSet as HashSet hs=new HashSet(nums.length); The runtime and space usage is better than 95 percent of submissions. but when you declare simply like HashSet hs=new HashSet(nums.length); its only better than 40 percent of submissions.. Can you explain that , please ?
Using dict. 25.8MB of memory usage class Solution: def containsDuplicate(self, nums: List[int]) -> bool: uniques = {} for num in nums: if uniques.get(num): return True else: uniques[num] = True return False
# This is little more faster than the provided solution? def containsDuplicate(nums): nums_set = set(nums) if len(nums_set) == len(nums): # Does not contain duplicates return False else: # Contains duplicates return True
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: if len(set(nums))==len(nums): return False return True is this a right way !? set is a set of unique elements so if the length is lesser than nums then we have duplicates otherwise return False.... i'm just learning so.... Can you plzz make dedicated videos on each chapters of DSA With a fast and your way of teaching.. I love how you teach.♥
soo 95 leetcode problems I solved helped hah, solved it in all the ways in 2 mins before hearing the same solution :D Though I'm going through your vids for detailed explanations on medium and hard ones, which can get tricky
I tried the brute force approach in C and it actually didn't work because it exceeded the time limit. Mi guess is that they wanted us to find a solution involving hashing
easier approach here is converting list to set: class Solution: def containsDuplicate(self, nums: list[int]) -> bool: noRepeated: set = set(nums) return True if len(nums) != len(noRepeated) else False and that's all
Its funny but this solution in Leetcode (TS) give me better rating: let bucket = new Set(nums); return (bucket.size !== nums.length ); Below is the approach similar to the python solution from above and is a little bit down in rating let bucket = new Set(); for (let n of nums) { if (bucket.has(n)) { return true; } bucket.add(n); } return false; Although the first approach loads all the numbers in the Set at once, it seems that its better optimized
If I just had like int duplicate_count, then instead of returning just did duplicate_count+=1 if there's a dup, would that effectively be a count duplicates function?
If you also find yourself stuck when coming up with a solution perhaps you could be making the mistake that I was: I was somewhat anxious to preserve the index of the duplicate element, or at least its value. Then, when I realised that you only had to return the status that is true or false I felt relieved coming up with the solution for the problem. So do pay attention if you are making this mistake.
While I tried your solution it didn't work for one case, so I added a condition here, which also reduced execution time and used less space hashset = set(nums) if len(hashset) < len(nums): for num in nums: if num in hashset: return True hashset.add(num) return False
If you are going to create a hashset like that, you can simple do this: hashset = set(nums)
return len(nums) != len(hash) This works because if there are any duplicates, the set will have a length that is less than the original array. If there aren't duplicates they will have the same length. NeetCode was just showing us the logic by doing it manually.
Yeah I think you're right, for some reason (even real interviewers) always assume it doesn't take space, but definitely something to mention to your interviewer just in case.
Dont know if someone else suggested this solution but i maneged to do it with a single line with the same complexity: return len(set(nums)) != len(nums)
True. This is a correct solution. But it is complicated and difficult to understand. As a dev, when you leave your job, your successor should be able to understand
I used a different approach. I converted the list into a set and then compared the length with the original list. If it was >=1 then dupe existed else no dupe
I wanted to ask. When I solved it (in C#). , I kinda had the same idea but instead of using a hashset, I used a List of integers (which I believe by using .Contains() my solution is technically brute force, but i'm not sure. The list was initialized to be the length of the nums array since I understand that if I called the add function without specifying the array length, it would create a new list each time a new number is added. I just wanted to know, what are the benefits of using a hashset alternate to a List? I'm really interested in learning how to optimize my code. Here's my code below: public bool ContainsDuplicate(int[] nums) { List unique = new List(nums.Length); foreach (int num in nums) { if(unique.Contains(num)) return true; unique.Add(num);
Because if you use a list to be converted from the nums array, all the elements are still the same. Meanwhile, HashSet eliminates the duplicated elements for you in order that you can compare the nums array with it.
Wouldn't the time complexity using the sorting option be 0(nlogn + n) because we're sorting the list then iterating through that sorted list to compare values?
Python sets cannot contain duplicate values, and values are hashed when they are added. The 'if x in y' does not iterate the whole set, it performs the hash and checks if that singular value is already present. No matter how many values are in the set, 'if x in set' will only check once for exactly that value.
How time and space complexity works in data type conversion. I converted the List to Set, next I compared length of list, set so it can give true or false I compared with these code I found no runtime difference. nums = [1,2,3,1] set1 = set(nums) if len(nums) == len(set1): return False else: return True
are putting them in set (which doesn't allow duplicates) then compare length of them , return true if it is true , else false is it something reasonable ?
What if we put all the values of the array in the set without checking anything, and compare its size with that of the array, if the size is different then we have some duplicate.
Thank you for the explanation. I have a question though. Wouldn't the worst-case time complexity of your solution be O(n^2) because of the "in" operator in the if statement" (i.e. if n in hashset: ). For example, when the list does not contain duplicates, the "in" operator will be used n times.
I don’t get why is brute force solution has complexity of n squared? If we have 4 elements then the worst case scenario is 3 + 2 + 1 = 6 not 16 What am I missing?
I tried a different approach and it worked fine. Here is the code. def isAnagram(self, s: str, t: str) -> bool: s = list(s) s.sort() t = list(t) t.sort() if (s == t): return(True) return(False)
What is the difference between using a set for a hash set and using a list? I tried 'hashset = set() -> hashset = list()' and 'hashset.add(n) -> hashset.append(n)', but It became Time Limit Exceeded,,. I don't know what is difference.. help me!
When you call "if n in list", it has to iterate through the list (O(n)) to check if n exists, whereas with a hashset, the search operation is O(1), hence why hashset is faster
wont "if n in hashset:" also take O(n) time in worst case and since "for n in nums:" already takes O(n) time in worst case , thus total time complexity would be O(n^2)?
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
@dev stuff There is a rule in calculating the big o which is drop non dominant , here the dominant is nlongn and non dominant is n so n is dropped
I utilized this course for MAANG prep and I could clear the Amazon interviews. Thank You !
How long did it take?
Another approach: convert the list to a set if the len(set)==len(list), return False else: return True
This is actually an amazing solution! return (len(set(nums)) != len(list(nums))) should work.
@@rohankamath794 codewise it is compact , but I think complexitywise it is same as the one explained in video
Yup, the to set conversion is O(n)
But to do this(converting to set) it would be iterating through all the list elements which is not the case for the approach shown in video
@@abhishekbhosale8820 but isnt the time and space complexity, same? If it is same, isn't this code more compact?
Started my planned 3 months leetcode journey today using neetcode as guide. Hoping to come back to this comment sometime in December fully prepared for any coding interview 🙏
how many problems are you doing a day?
I know you will make it
did you complete sir?
Thanks everyone, I got a job even before December. Though not at fang.
@@chigozie_jesse Congratulations.
I'm using this channel as my preparation kit. Thank you!
This is the last question right? Kudos for completing it for us, your channel is an awesome resource :)
Yes, we finally finished the list!!!
what list?
I got a simple one. Use set and check size of the set each time we insert an element and compare it to the size from the previous iteration.
Pseudo Code:
prevSize = 0;
for (i=0; i
My 1st neetcode problem. Hopefully I am going to acheive something big by the end of this journey I started today
How'd it go
just starting on neetcode website now. Will probably try one problem at a time every few days or more often once i have most of my concepts and basic syntax refreshed :P Hopefully, I can get to the point where I solve few problems a day and just be comfortable at mid-hard level questions. Long way to go, but at least the goal is clear.
Same here bruhh starting the grind
we in this together Brodie, we got this
How is it going? It's been couple of months
@@yashashav_dk3766 I got to solving around 20-25 questions [Did most or all of the Easy level questions] then stopped for now. Just enrolled in Networking Programs [Fast Track - 2 years], planning to see how I do in first semester and depending on that I will either get in co-op and work in IT field and hoping to make use of what I have learned [Programming from prev. degree] and continuing from there. Unfortunately, I tend to slack of when I try to learn by myself. So, this is just my way of forcing myself to discipline myself :P I hope others are doing better than me.
T: O(nlogn) & S: O(1) --->
nums = [1, 2, 3, 1]
sortN = sorted(nums)
l, r = 0, 1
def containsDuplicate(l, r, s):
while l < len(s) and r < len(s):
if s[l] == s[r]:
return True
l += 1
r += 1
return False
print(containsDuplicate(l, r, sortN))
Great
best approach ever : just two line of codes
bool containsDuplicate(vector& nums) {
set s {nums.begin() , nums.end()};
return s.size() == nums.size() ? false : true;
}
Thank you! I solved the problem with all these approaches on my own, but each time I couldn't achieve low consumption of both cpu and memory. Then I decided to look at the solutions, and was surprised that there is no ideal solution. Only compromises. Valuable lesson for me.
What's the difference between hashmap and hashset? In this case, which one should use?
Hashmap has a key value association whereas hashset is only a key. In this case, we just need to know the existence of such a key in the array so hashset here is more appropriate because the value field would be useless to us.
In short, if you need to map keys to values use hashmap; if you just need keys, use hashset.
@@zoriiginalx7544 The hashmap is faster than hashSet
after watching your tutorial everyday for almost a month, finally i have started building logic like the way you do, BIG THANKS TO YOU!
Bro but please continue more questions in python. Please Please
My first thought was to turn it into a set, compare len of set with len of original. Return true if lens are different
Hmmm I'm not sure if I'm right about this but I think the "in" operator as in "if n in hashset" has a worst-case of O(n) which in your case since it is in a loop would be a total worst-case of O(n^2). I used the same idea you explained in the video (but implemented differently without the "in" operator) and got a faster time than you did 116ms average on 3 runs which apparently is faster than 86.62% of solutions. So, don't assume that checking for the existence of an element in a set is O(1). Instead, you can use a dictionary with a default value because rather than have to scan though all values (O(n) as in the "in" operator does) you simply hash your value (one way function) which is truly O(1).
FULL CODE:
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
logged = {}
for num in nums:
logged[num] = logged.get(num,0) + 1 # returns 0 if key doesn't have a value yet and then we add 1 to indicate we've logged this value
if logged[num] > 1: #value has showed up at least once before
return True
return False
no dude... checking if an item is in a hashset is O(1) time complexity. similarly checking if an item is in hashmap also has O(1)
time complexity. your time running faster means nothing because they'd have a different of like 15ms, and at that point the difference is so small it's just computer error, you didn't make an any faster solution. and of course you wouldn't know that bc the concept that 115ms leetcode algo is same as 130ms leetcode algo is probably more advanced topic than O(1) hashset look up. Because you might assume the leetcode website and machine are infallible and perfect but the reality is, the computer just isn't
that accurate time-wise when you talk about differences of 15ms. Anyways comparing algorithms not in time complexity but because of how leetcode ran it is pretty stupid. Only novices care a lot about leetcode time and %. They rly only care about time complexity. In this case it O(n), not O(n ^ 2). lol.
Why would the "in" operator be O(n) for sets when we know they support O(1) lookup? You went on a wild goose chase I'm afraid. If you run the exact same program several times on Leetcode, you'll often see large variations in execution time. You can't infer from such small differences that "x in set" lookups are O(n) in Python. If you really want to test that, change the set to a list and see what happens -- I just did it and the runtime and got 440ms with a set and a timeout (I think around 3 seconds) with a list.
Remember, with big-O complexity we don't care about a slightly different wall clock time, but rather, how quickly the time requirement grows with the input size, so you can't conclude if your program runs slightly faster or slower (my set version is 3 times slower than in this video, even though it's the same program -- probably Leetcode is busier now and that slows things down).
dude, hashset are similar to dictionaries except that the latter permits a value and the set not. Both are O(n), a hashset is not a list so that you scan elements on it one by one to find what you need!! it is in its name, a HASHset, the values are hashed to get the index where they are in the set
I am sharing your videos and website with my 40 actively learning friends. Thank you for supporting us.
I think we can also do this question by creating a set....if set's length== given list then we can say false otherwise true.
Another approach would be to insert the array into the hashset, which would be O(logn) ... and compare the size of hashset with array, if they are equal return false else return true. This would be the fastest in terms of execution I suppose, but would require O(n) space more.
that's impossible, it needs to iterate over each item at least once so it is O(n) time
setList = set(nums)
if len(setList) == len(nums):
return False
else:
return True
#Your runtime beats 90.67 % of python3 submissions. :)
Can you please explain how your solution compares with the following: return set(len(nums)) < len(nums)
Since python sets normalize duplicates, if a set length is less than the length of the array itself, it means there were duplicates inside it.
1st day of Leetcode. Graduation in 11 months. Let's go!
Thanks boss. Ended up writing solution 2 on my own, but knew there had to be something with hash sets. Of course the old addage of "when in doubt, hash it" rung true. Don't know how I didn't see it. Thanks.
Hey neetcode fam, got a technical assessment with microsoft today. Wish me luck.
How did it go ?
By the way, space complexity of the sorting method in Python is O(n) if you use the built-in sort() method, because list.sort() uses timsort under the hood.
arr = [1, 2,3,2,3]
for I in range (0,len(arr) ) :
for j in range (I+1, len(arr)) :
if (arr[i] == arr[j]) :
Print (arr[j]).
Brute force
I understand that hash sets don't allow duplicates but for this problem why is it necessary to use it (not that it is better not to, just for my own understanding).If you had created an empty list and used the same method would it not have worked the same?
10 months late, but hashes have a much faster lookup time because the index isn't ordered, but instead based on a hashing function. Since lookups happen based on key, you don't need to search the whole hash for your input, you just hash the input (run it through the function) and check that one resulting index. If it's there, it's there. If it's not, it's not in the list.
If you used an empty list/array, each lookup to check for a duplicate would take O(N) instead of O(1), since you have to check each list index for your item.
Very nice explanation. I could user the 'set' idea and then solve like this: return len(set(nums)) != len(nums)
inefficient, but sort() -> unique(), compare size
Why? Why is solution with O(n) worse than the solution with sorting, O(n log n)? Tested in javascript
return len(nums) != len(set(nums))
What if we do it like this?
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
countMap = {}
for number in nums:
try:
countMap[number] = countMap[number] + 1
return True
except KeyError:
countMap[number] = 1
return False
This way we can avoid the check "if n in hashset" which also takes some time right?
optimized with checking first if array length is less than 2 (return false)
Shouldn't mix set and map (hashset and hashmap/hashtable) in the solution #3.
How does he mix them?
instead of a hashset, i tried using a simple list but that doesnt seem to work for this problem, it throws a Time limit exceeded error, trying to understand why that is.
edit: is it because array searching takes more time than set searching?
yup sets or dicts take o(1) search time while lists take o(n).
Awesome. You helped me solve my first leetcode question!!!
I don't understand the time complexity in hashset approach. I get that iterating once over it in for loop causes O(n) time complexity. But we are also checking inside of "if", whether the element already exists inside hashset. doesn't it mean, that we have to iterate also over all hashset elements to check if the new element already exists inside?
Watching your coding explaination first time and really loved your explaination, going to recommend to my friends and collegues.. Thank you!
can you make those tutorials again but for javascript?
Do we not have to consider the fact that it must traversing through the Hashset in the solution @NeetCode?
Thank you, this is the first video I watch in this playlist. There is 149 left. I hope I can watch all, because this is leetcode.
When I answered this I thought I had a really bad solution since it was bottom 95% in terms of speed but then when I came to the video I had the exact same solution as him. Apparently Leetcode adds more tests over time and getting a high % becomes impossible even if you have the same solution. For anyone reading this its better to understand the time and space complexity than to focus on those mostly worthless numbers on the website. There could be other reasons but running the exact same code as him gives me 700-900ms when in the video it was 131ms.
There is a faster solution.
You run 2 pointers, one from index 0 and second from index n-1 in a loop and they meet in the middle. While iterating, add values to the HashSet and check if they exist and return true.
When looping in a single direction, the worst case you will get it O(n), with 2 pointers u get O(n/2).
This is true. However, in our algorithms class, we learned to disregard the coefficient. In this case, O(n/2) = O(1/2 * n) = O(n)
"with 2 pointers u get O(n/2)." for each pointer, thus you multiply by 2, so 2xO(n/2) = O(n) , or am I wrong?
STRANGE!!! for JAVA
when you submit on leetcode by declaring HashSet as HashSet hs=new HashSet(nums.length);
The runtime and space usage is better than 95 percent of submissions.
but when you declare simply like
HashSet hs=new HashSet(nums.length);
its only better than 40 percent of submissions..
Can you explain that , please ?
He is so good that i watch in Python, do in Java
yeah same here
Using dict. 25.8MB of memory usage
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
uniques = {}
for num in nums:
if uniques.get(num):
return True
else:
uniques[num] = True
return False
# This is little more faster than the provided solution?
def containsDuplicate(nums):
nums_set = set(nums)
if len(nums_set) == len(nums):
# Does not contain duplicates
return False
else:
# Contains duplicates
return True
that was my solution as well!
this was my solution too
Same
Did you realize why it's slower? think: first two are duplicates and the list has millions of elements.
Thanks for sharing this amazing knowledge! Just discovered you. Keep up a great job!
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
if len(set(nums))==len(nums):
return False
return True
is this a right way !?
set is a set of unique elements so if the length is lesser than nums then we have duplicates otherwise return False....
i'm just learning so.... Can you plzz make dedicated videos on each chapters of DSA With a fast and your way of teaching.. I love how you teach.♥
I am glad you created some courses for system design on the website. I am going to join as lifetime member. Looking for more content.
This is awesome, I thought using awful nested loops, however this is better!
What is the time complexity for adding n items to the set in python like set([1,2,3,...n]), is it O(n) or O(1)
O(nl)
i was asked a very similar question to this from my fb phone interview earlier lol
Done thanks trivial Hashset or sorting solutions
70% more efficient
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
if len(set(nums)) != len(nums):
return True
else:
return False
try it with 1,2,3,4
return len(nums) != len(set(nums))
try this
soo 95 leetcode problems I solved helped hah, solved it in all the ways in 2 mins before hearing the same solution :D Though I'm going through your vids for detailed explanations on medium and hard ones, which can get tricky
Put an else for the if statement before adding to the hashset and this will use a bit of less memory
Could you explain why there will be less memory used?
I tried the brute force approach in C and it actually didn't work because it exceeded the time limit. Mi guess is that they wanted us to find a solution involving hashing
easier approach here is converting list to set:
class Solution:
def containsDuplicate(self, nums: list[int]) -> bool:
noRepeated: set = set(nums)
return True if len(nums) != len(noRepeated) else False
and that's all
JS oneliner: return (new Set(nums)).size < nums.length
I had the efficient solution from the start . feels good.
Thank you so much for your valuable help. I have watched every single video in your playlists. Keep it up!
just a quick question, why don't we count the space used by the sorting algo?
@NeetCode why not turn the list to a set check the set and list length. if same returns 0 else returns 1
Are we typically allowed to use a sort function in an interview environment?
Its funny but this solution in Leetcode (TS) give me better rating:
let bucket = new Set(nums);
return (bucket.size !== nums.length );
Below is the approach similar to the python solution from above and is a little bit down in rating
let bucket = new Set();
for (let n of nums) {
if (bucket.has(n)) {
return true;
}
bucket.add(n);
}
return false;
Although the first approach loads all the numbers in the Set at once, it seems that its better optimized
def containsDuplicate(arr):
newArr = list(set(arr))
if len(newArr) < len(arr):
return True
else:
return False
Starting to prepare this today (11/8/2023) . Plan to reply to this comment when I complete the list on or before 11/9/2023.
have you
This might be an even faster solution:
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(nums) != len(set(nums))
If I just had like int duplicate_count, then instead of returning just did duplicate_count+=1 if there's a dup, would that effectively be a count duplicates function?
If you also find yourself stuck when coming up with a solution perhaps you could be making the mistake that I was:
I was somewhat anxious to preserve the index of the duplicate element, or at least its value. Then, when I realised that you only had to return the status that is true or false I felt relieved coming up with the solution for the problem. So do pay attention if you are making this mistake.
While I tried your solution it didn't work for one case, so I added a condition here, which also reduced execution time and used less space
hashset = set(nums)
if len(hashset) < len(nums):
for num in nums:
if num in hashset:
return True
hashset.add(num)
return False
If you are going to create a hashset like that, you can simple do this:
hashset = set(nums)
return len(nums) != len(hash)
This works because if there are any duplicates, the set will have a length that is less than the original array. If there aren't duplicates they will have the same length. NeetCode was just showing us the logic by doing it manually.
Doesn't Python built-in sorting cost O(n) space complexity?
Yeah I think you're right, for some reason (even real interviewers) always assume it doesn't take space, but definitely something to mention to your interviewer just in case.
@@NeetCode isn't it O(nlog(n))
@@cosepeter2197 i believe sorting is O(n log (n)) time complexity as a heuristic
you can just return len(nums) > set(nums)
Hi, at 3:24 did you meant time complexity instead of memory complexity?
Yes, it was a slight mistake. He actually meant Time Complexity.
Nice Find!
The method shown using a hashmap is also known as memoization. Correct?
If you compare length of that list and set of that list its little better
Dont know if someone else suggested this solution but i maneged to do it with a single line with the same complexity:
return len(set(nums)) != len(nums)
same worst case time complexity, but if you have the first two be dups in a list of millions, his solution is far less than your O(n), is it O(2) ?
This also might be a solution:
nums = [1,2,3,1]
return True if Counter(nums).most_common(1)[0][1] > 1 else False
True. This is a correct solution. But it is complicated and difficult to understand. As a dev, when you leave your job, your successor should be able to understand
I used a different approach. I converted the list into a set and then compared the length with the original list. If it was >=1 then dupe existed else no dupe
Today i learned a hashset and hashmap aren't the same thing. Makes sense but somehow i haven't heard that term instead of just calling it a set
I wanted to ask. When I solved it (in C#). , I kinda had the same idea but instead of using a hashset, I used a List of integers (which I believe by using .Contains() my solution is technically brute force, but i'm not sure.
The list was initialized to be the length of the nums array since I understand that if I called the add function without specifying the array length, it would create a new list each time a new number is added. I just wanted to know, what are the benefits of using a hashset alternate to a List?
I'm really interested in learning how to optimize my code.
Here's my code below:
public bool ContainsDuplicate(int[] nums)
{
List unique = new List(nums.Length);
foreach (int num in nums)
{
if(unique.Contains(num))
return true;
unique.Add(num);
}
return false;
}
Because if you use a list to be converted from the nums array, all the elements are still the same. Meanwhile, HashSet eliminates the duplicated elements for you in order that you can compare the nums array with it.
List would be better in case you want to modify the array (insert, delete or whatsoever) instead of reading it only.
4:30 looping through all elements of hashmap will have time complexity O(n)
Why hashset? We could have added in new array also and then checked 'n' in the new array.
Wouldn't the time complexity using the sorting option be 0(nlogn + n) because we're sorting the list then iterating through that sorted list to compare values?
It would simplify to O(nlogn)
Just order and read the Last element of the array should be only O(logn) in time
Isn't complexity is still O(n^2)? Because `if x in y` also do a iteration to check if value exists or not.
Python sets cannot contain duplicate values, and values are hashed when they are added. The 'if x in y' does not iterate the whole set, it performs the hash and checks if that singular value is already present. No matter how many values are in the set, 'if x in set' will only check once for exactly that value.
@@MrPeckishPenguin Oh thanks, I don't know that 👍
How time and space complexity works in data type conversion. I converted the List to Set, next I compared length of list, set so it can give true or false I compared with these code I found no runtime difference.
nums = [1,2,3,1]
set1 = set(nums)
if len(nums) == len(set1):
return False
else:
return True
started doing blind 75 list #1
are putting them in set (which doesn't allow duplicates) then compare length of them , return true if it is true , else false
is it something reasonable ?
What if we put all the values of the array in the set without checking anything, and compare its size with that of the array, if the size is different then we have some duplicate.
Try this :
def containsDuplicate(self, nums: List[int]) -> bool:
if len(nums) == len(set(nums)):
return 0
else:
return 1
Can't we solve it bitwise, by using (&) operation. If numbers are same it will be 0 and return true.?
Thank you for the explanation. I have a question though. Wouldn't the worst-case time complexity of your solution be O(n^2) because of the "in" operator in the if statement" (i.e. if n in hashset: ). For example, when the list does not contain duplicates, the "in" operator will be used n times.
sets in python are constant lookup time.. *hash* set
I don’t get why is brute force solution has complexity of n squared? If we have 4 elements then the worst case scenario is
3 + 2 + 1 = 6 not 16
What am I missing?
Just to share a simpler and faster way of doing this
numset = set(nums)
if len(numset) == len(nums):
return False
else:
return True
I tried a different approach and it worked fine.
Here is the code.
def isAnagram(self, s: str, t: str) -> bool:
s = list(s)
s.sort()
t = list(t)
t.sort()
if (s == t):
return(True)
return(False)
What is the difference between using a set for a hash set and using a list? I tried 'hashset = set() -> hashset = list()' and 'hashset.add(n) -> hashset.append(n)', but It became Time Limit Exceeded,,. I don't know what is difference.. help me!
When you call "if n in list", it has to iterate through the list (O(n)) to check if n exists, whereas with a hashset, the search operation is O(1), hence why hashset is faster
wont "if n in hashset:" also take O(n) time in worst case and since "for n in nums:" already takes O(n) time in worst case , thus total time complexity would be O(n^2)?