Great explanation but 1 thing needs update. For "put", if key already exists, then value needs to be updated as well as the key's frequency also needs to be updated(+1)
If I am not mistaken, I think we can just use 2 Hashmaps instead of 3. 1) hashMap This would store frequency and value nodes (Node would have value and next and prev pointer to node) Node() { Int value; Node left; Node right; } Second, a hashMap which stores pointer (reference) to a Node n. Whenever we say get (xyz) I get the address from 2nd hashMap and get value by going to that address in hashMap1. Thanks
When you say get(xyz) and search it in Second HashMap, you get a Node, and directly go to the list in first Hashmap, and do your function. But you don't know the frequency of the xyz, where would you insert xyx after the get operation. I mean you have to increment the frequency by 1.
Good explanation. Would like to add the reason for using doubly linked list as it is not mentioned in the video. The reason for using DLL is while deleting a node it becomes easy to delete the node directly if we have the pointer to that node from the hasmap. Bcoz while deletion we need the previous node so that we can unlink the previous node from the node to be deleted. Hence DLL comes handy as we don't have to traverse through the whole list to get the prev node.
No. Freq to keys list is a map, so lookup is O(1) by freq. The erase is called on the doubly linked list object, and if you have the pointer - which you do, stored in key_iterator, erase is O(1). If you do not have access to the pointer, it is indeed O(N) as you need to use remove() not erase(). www.cplusplus.com/reference/list/list/erase/ Complexity: Linear in the number of elements erased (destructions). Note that unlike for vectors or other ordered data structures, removing an element from the list DOES NOT invalidate any of the iterators! If you think about a DLL that you implement yourself, you have struct Node { int val; Node* prev = nullptr; Node* next = nullptr; } deleteNode(Node* toDel) { toDel->prev->next = toDel->next; // remove reference in O(1), no need to iterate // delete toDel; // only if allocated using new }
Great explanation! everywhere else just went through code, but your visualisation helped alot
great explanation! hats off
Amazing!!
Thank you so much for the clear explanation
Loved the simple explanation !!
Great explanation but 1 thing needs update. For "put", if key already exists, then value needs to be updated as well as the key's frequency also needs to be updated(+1)
If I am not mistaken, I think we can just use 2 Hashmaps instead of 3.
1) hashMap
This would store frequency and value nodes (Node would have value and next and prev pointer to node)
Node()
{
Int value;
Node left;
Node right;
}
Second, a hashMap which stores pointer (reference) to a Node n.
Whenever we say get (xyz) I get the address from 2nd hashMap and get value by going to that address in hashMap1.
Thanks
When you say get(xyz) and search it in Second HashMap, you get a Node, and directly go to the list in first Hashmap, and do your function. But you don't know the frequency of the xyz, where would you insert xyx after the get operation. I mean you have to increment the frequency by 1.
Thank you , easily understandable to people like me 😁.
Good explanation. Would like to add the reason for using doubly linked list as it is not mentioned in the video. The reason for using DLL is while deleting a node it becomes easy to delete the node directly if we have the pointer to that node from the hasmap. Bcoz while deletion we need the previous node so that we can unlink the previous node from the node to be deleted. Hence DLL comes handy as we don't have to traverse through the whole list to get the prev node.
Isn't freq_keyslist[freq]erase() running in linear time?
No. Freq to keys list is a map, so lookup is O(1) by freq. The erase is called on the doubly linked list object, and if you have the pointer - which you do, stored in key_iterator, erase is O(1). If you do not have access to the pointer, it is indeed O(N) as you need to use remove() not erase().
www.cplusplus.com/reference/list/list/erase/ Complexity: Linear in the number of elements erased (destructions).
Note that unlike for vectors or other ordered data structures, removing an element from the list DOES NOT invalidate any of the iterators!
If you think about a DLL that you implement yourself, you have
struct Node
{
int val;
Node* prev = nullptr;
Node* next = nullptr;
}
deleteNode(Node* toDel)
{
toDel->prev->next = toDel->next; // remove reference in O(1), no need to iterate
// delete toDel; // only if allocated using new
}
can't you get the last pointer as rbegin() rather than --end() ?
very nice explaination sir
Nice explanation, but in the example you have taken there are only 9 keys in the freq map so putting key 11 won't remove any key.
Bhaiya how to get into mba in harvard or cornell with reduced fees( financial aid/scholarship) after btech in india. Bhaiya pls reply
beautifully explained!
you have explained very clearly. Thank you for easy approach.
Thank you so much. This was very clear.
Perfect
Neat and precise explanation!