you can just use a frequency array with the total size and fill all the numbers with -1 and then just update the values with put/remove, the only drawback is that this will have a space of O(N), but it's much less code and it's like a Hashmap anyway
It was because on the problem it didn't actually required chaining, if you see on the put method the problem described it asked to just update the value if the key already exists. But the way NeetCode implemented he used chaining and that what's made it harder, but it's a great explanation
I just used an array before, as the key and value is also integer. That is correct, we should use hashed indexes as general has maps intented to store any kind of type. But in our case it does not necessary, we can just get 1000 rooms of array and store every element as a value. This is just my opinion. By the way, untill watching this video I did not comprehend how actually hash map works. Thanks Navdeep
we're simply giving it a default value as the 'dummy' node to avoid edge cases where self.map[self.hash(key)] is None. also, the constraint shows that key and value are in this range: 0
Do we really need to check `while *cur* and cur.next` for remove operation? Can't we just use `while cur.next' ? I think it's redundant because if there is cur.next then `cur` is definitely not None and we modify the 'next' node anyway for the actual removal process
Yeah it does. The solution is still fine though since keys > 1000 get modded to an index between 0-999, and it's better for memory compared to initializing 10,000 nodes (maybe not for time complexity, performing get operations)
@@felixsla21 yeah youre right. I also thought [List()]*1000 would make 1000 objects but it wont. It just make one object and then stores its reference in all indexes
you can just use a frequency array with the total size and fill all the numbers with -1 and then just update the values with put/remove, the only drawback is that this will have a space of O(N), but it's much less code and it's like a Hashmap anyway
I think this is not an easy problem!!
easy )
yes, only if you don't know how hashtable works
It was because on the problem it didn't actually required chaining, if you see on the put method the problem described it asked to just update the value if the key already exists. But the way NeetCode implemented he used chaining and that what's made it harder, but it's a great explanation
@@felipeklahn988 chaining is being done for the index itself not the value
me too
I just used an array before, as the key and value is also integer. That is correct, we should use hashed indexes as general has maps intented to store any kind of type. But in our case it does not necessary, we can just get 1000 rooms of array and store every element as a value. This is just my opinion. By the way, untill watching this video I did not comprehend how actually hash map works. Thanks Navdeep
I've stared to love DUMMY NODES!
I am struggling to understand why we chose specifically 1000 for the size. I know it works, but why exactly? Would appreciate any help 🙏
Why is the first node's key and value equal to -1 in the ListNode?
Where are we defining it to be -1?
we're simply giving it a default value as the 'dummy' node to avoid edge cases where self.map[self.hash(key)] is None. also, the constraint shows that key and value are in this range: 0
Do we really need to check `while *cur* and cur.next` for remove operation? Can't we just use `while cur.next' ? I think it's redundant because if there is cur.next then `cur` is definitely not None and we modify the 'next' node anyway for the actual removal process
Same thought! Just try with cur.next and it works cool
Cur has to exist before you check cur.next none type can't have next.
So we don't need to initialize a dummy node?
He made the dummy nodes when he did:
self.hashmap = [LinkNode() for _ in range(MAX)]
I thought the question said that there would be at most 10,000 operations done on the map ?
Yeah it does. The solution is still fine though since keys > 1000 get modded to an index between 0-999, and it's better for memory compared to initializing 10,000 nodes (maybe not for time complexity, performing get operations)
Why is the key and value equal to -1 when init the ListNode?
you are great
anyone here from october 4?
Me!
Me too.
Me too
Yep
meeeeee
you should arrays and its indices instead of map
was stuck on that edge case
why cant me just use an array instead of an array of ListNodes?
Because insertion and deletion won't be constant time in an array, you will have to shift values. That won't be a problem if you use a linked list.
still not sure
why you have ussed 1000
why can't we use list?
0
Why 1000?
Why do we want a value between 0-999?
Hey, have been watching your videos and following.
I want to be good in DSA to crack interviews, what path should i follow?
Why can't we just use a dictinary rather than an array?
because isnt a dictionary essentially a hashmap already so there would be no point 😂
why use linked list when we can use simple list
I think remove in a list takes O(n) TC where as in LL it takes O(1).That may be the reason
Why not [List()] * 1000?
Yeah, that would've been more concise
But wouldn't this copy the same ListNode reference 1000 times?
@@felixsla21 yeah youre right. I also thought [List()]*1000 would make 1000 objects but it wont. It just make one object and then stores its reference in all indexes
@NeetCodeIO i think you should initialize with 10000 instead 1000 since question say there 10**4 calls
،amazing
Im so cooked
kinda awful hashmap but hey it meets the api requirements i guess. sad to see no dyanmic array, solving collisions with list and not a tree and so on