All O`one Data Structure | Super Simple Explanation | Leetcode 432 | codestorywithMIK

This is the 17th Video of our Playlist "Design Data Struture : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve a good Design DSA Problem : All O`one Data Structure | Super Simple Explanation | Leetcode 432 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : All O`one Data Structure | Super Simple Explanation | Leetcode 432 | codestorywithMIK
Company Tags : Google

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Summary :
The AllOne data structure is designed to track the frequency of keys while efficiently retrieving the key with the highest and lowest counts. It uses a combination of a doubly linked list and a hash map:

Doubly Linked List: The list nodes store a frequency count and a set of keys that share that count. This allows us to maintain the order of counts and traverse between different frequency groups.

Hash Map: The map (keyCountMap) maps each key to its corresponding node in the linked list. This enables quick access and updates to the frequency of any given key.

Increment and Decrement:

When incrementing (inc), the key is moved to the node representing the next higher count. If it doesn't exist, a new node is created.
When decrementing (dec), the key is moved to the node with the next lower count or removed if its count becomes zero.
Efficient Max/Min Retrieval:

This design ensures O(1) complexity for insertion, deletion, and retrieving the max/min keys, making it suitable for scenarios requiring frequent updates and quick lookups.

✨ Timelines✨
00:00 - Introduction
0:26 - Problem Explanation
3:04 - Building Thought Process
8:10 - Why Double Linked List Is Best for this
18:25 - Complete Dry Run with Double Linked List + Map
26:32 - Line By Line Coding

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[codestorywithMIK]

NOTE : In the Node, We should have used unordered_set<string> instead. It will have Amortized O(1) time complexity for erase() function.
I have updated it in the comment of my github code

Thanks & Regards,
Tumhara MIK

[yashkalia]

Hello sirrr,
I recently got an oncampus placement of 6LPA
all thanks to youuuu,
all DSA rounds were cleared just because of your intuative teaching style which i always looked for in teachers!!
Your channel is GOLD please never stop 💌💌💌
If you start upsolving contest problems, the level of this content would become unmatched!

[tusharsingh]

Saw the first video for 18 minutes and was able to solve the problem on my own.

[jontrotter]

Hi! Got on campus placement of 22 LPA, your videos were instrumental in clearing the DSA rounds. Thanks a lot!

[cash]

Hey
I recently got Apple intern offer
I have been solving Potd for more than a year now
This is the go to channel when I get stuck and don't understand the articles!!
Thanks alot ❤❤❤

[Ankitkumar-fzkc]

Thanks @codestorywithMIK sir,
for making this problem this easy.

[Si_]

Bhaiya dimag ka ---- ho gaya pr maza aa gayaa explanation se😊

[vyrs]

Best explanation on the internet Thankyou bhaiya

[XS_]

Vector of set will use O(N) space if we don't delete empty indexes, and O(1) time,
But time complexity will incease when we have a jump of count ie; all drom 0 to a large number M are empty, so will take O(M) time to get minimum, similarly for maximum

[nagarajucharyvadla]

You are awesome bro, Great explanation ❤

[Abhay]

bhai aaj ke contest ka Count of Substrings Containing Every Vowel and K Consonants II ye question ki video daalo kaafi kuchh seekhne ko milegga insme sliding window + map ka concept h

[galepraveen]

Hey Mik Bhai, love the way you teach on ipad. Seeing you, I recently bought one. Which app do you use to write and explain? Also, is it free or paid?

[Divyansh-xn]

Bhaiya jab apne deletion O(1) m bola vahi se dimag m agya tha ki Doubly linked list is best for this situation. POV: apka video jo dekha tha 2.5 months phle LRU cache wala. <3

[aizadiqbal]

bhai...please ek video please bana do, how and in what order should a noob practice to become a pro
means pehle konsi playlist dekhen, roadmap etc...

[asmitamhetre]

I used same approach but just i took dummy node head and tail but its giving me TLE, I am not getting why it's giving TLE
class Node
{
public:
int cnt ;
unordered_set<string>st ;
Node* next ;
Node* prev ;

Node() {};
Node(int cnt)
{
this->cnt = cnt ;
st = {} ;
next = NULL ;
prev = NULL ;
}
};

class AllOne {
public:
Node* head ;
Node* tail ;
unordered_map<string, Node*>mp;

AllOne() {
head = new Node(0) ;
tail = new Node(1e4+1) ;
head->next = tail ;
tail->prev = head ;
}

Node* makenode(int cnt, string key)
{
Node* newnode;
newnode = new Node(cnt);
(newnode->st).insert(key);
return newnode ;
}

void addnode(Node* node, Node* newnode)
{
Node* temp ;
temp = node->next ;

newnode->next = node->next ;
node->next = newnode ;

temp->prev = newnode;
newnode->prev = node;
}

void deletenode(Node* node)
{
Node* prevnode ;
Node* nextnode ;

prevnode = node->prev ;
nextnode = node->next ;

prevnode->next = nextnode;
nextnode->prev = prevnode;
}

void inc(string key) {
if(mp.find(key) == mp.end())
{
Node* node;
node = head->next ;

if(node->cnt == 1)
{
(node->st).insert(key);
mp[key] = node ;
}
else
{
Node* newnode;
newnode = makenode(1, key);
addnode(head, newnode);
mp[key] = head->next;
}
}
else
{
Node* node ;
node = mp[key] ;

int cnt = node->cnt ;
(node->st).erase(key) ;
cnt++ ;

Node* nextnode ;
nextnode = node->next ;

if(nextnode->cnt == cnt)
{
(nextnode->st).insert(key);
mp[key] = nextnode ;
}
else
{
Node* newnode;
newnode = makenode(cnt, key);
addnode(node, newnode);
mp[key] = node->next ;
}

if((node->st).size() == 0)
{
deletenode(node);
}
}
}

void dec(string key) {
Node* node ;
node = mp[key] ;
int cnt = node->cnt ;
(node->st).erase(key) ;

cnt-- ;
if(cnt == 0)
{
mp.erase(key);
}
Node* prevnode ;
prevnode = node->prev ;

if(prevnode->cnt == cnt && cnt != 0)
{
(prevnode->st).insert(key);
mp[key] = prevnode ;
}
else if(cnt != 0)
{
Node* newnode;
newnode = makenode(cnt, key);
addnode(node->prev, newnode);
mp[key] = node->prev ;
}

if((node->st).size() == 0)
{
deletenode(node);
}
}

string getMaxKey() {
Node* node;
node = tail->prev ;
string s ="";
unordered_set<string>st = (node->st);

for(string it : st)
{
return it;
}
return s;
}

string getMinKey() {
Node* node;
node = head->next ;
string s ="";
unordered_set<string>st = (node->st);

for(string it : st)
{
return it;
}
return s;
}

};

[harjotanand]

13:20 pe ....what if agar hum ek aur map le len ....instead of linked list ... also in map we can store as { counter, vector<string> } as pair in map ...and when the vec is empty ..then we can remove that counter ...and if we again need that counter we can add it ...

Ahhh this is really a HARD question, doing DSA in JS, seem this question is more difficult. I have understand it, Thanks for your explanation. But need to see this question again and again. Any chance this question asked in any other interview except Google?

[aviralgoel]

bhaiya, daily motivation bhi dia karo videos mein...

[justanuhere]

bhaiya please make a video on Count of Substrings Containing Every Vowel and K Consonants II from today's weekly contest whenever you're free

[krishgupta]

why we use doubly linked list instead of singly linked list