LRU Cache | Brute Force | Optimal | Detailed | Leetcode 146

This is the 2nd Video on our Design Data Structure Playlist.
In this video we will try to solve a very good and famous and interesting Problem "LRU Cache" (Leetcode 146)
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : LRU Cache
Company Tags : Adobe, Microsoft, Amazon, Citygroup, Twitch and many more shown in video
My solutions on Github : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#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

[@bhartipatel7833]

Plz keep uploading such videos It really helps 🙏

[@souradeep.23]

true 🔥

[@codestorywithMIK]

Guys, let’s do LRU Cache first. This will help us to solve LFU Cache Next video will be on LFU Cache Thank you all for watching ❤❤❤

[@souravjoshi2293]

Aaay Sir 🔥

[@AbhijeetKumarAJ]

yeh pre-requisite hai for LFU cache?

[@niteshk0487]

@@AbhijeetKumarAJ No bro pre-requisite is LRU

[@AbhijeetKumarAJ]

@@niteshk0487 I AM ASKING is LRU pre-requisite for LFU

[@codestorywithMIK]

Yea this qn should be solved before LFU It will make it easy for all of us to understand LFU Cache

[@singerpranavmodi]

I hope I would have got this channel before. You are really awesome bro!!!

[@codestorywithMIK]

It means a lot to me. Thank you so much 😇🙏

[@vineetkumarmotwani474]

Went through the comments and disappointed to see that not even a single soul came up with the queue solution. Anyways, here is my implementation for the same: class LRUCache { int size; queue q; map mp, cnt; public: LRUCache(int capacity) { size = capacity; mp.clear(); } int get(int key) { if (cnt.find(key) == cnt.end()) return -1; q.push(key); cnt[key]++; if(mp.find(key) != mp.end()) return mp[key]; return -1; } void put(int key, int value) { q.push(key); cnt[key]++; mp[key] = value; while (cnt.size() > size) { int cur = q.front(); q.pop(); if (cnt[cur]-- == 1) cnt.erase(cur); } } }; /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */

[@codestorywithMIK]

Thank you so much for sharing ❤️❤️

[@AnandKumar-kz3ls]

Brilliant explanation as always Instead of adding to the front you can also add to the back only problem is dll.end() return the iterator just after last element we need to subtract the iterator by 1 example: auto itr=dll.end(); itr--; map[key].first=itr; i think erase time complexity of unorderded map is O(N) in worst case which can be avoided by assigning dll.end() and just need to add one check if(map.find(key)!=map.end() && map[key].first!=dll.end() ); and should use unordered_map instead of ordered map

[@codestorywithMIK]

Indeed . Feels great you mentioned this one ❤️❤️❤️

[@nikhil_1852]

i know how to solve this problem but badee din dimag mai confusion tha ki bhai singly linked list bhi use kr sakta tha mai ..now i got know why i used dll here

[@AbhijeetKumarAJ]

so the optimal solution time complexity is O(1)? and space complexity is O(n) as we are storing data in doubly linked list?

[@codestorywithMIK]

Absolutely correct Abhijeet ❤️

[@meoww-c3b]

Java Solution using DLL and map to store Key and address created addNode and delNode function class LRUCache { class Node{ int key; int val; Node prev; Node next; Node(int key, int val){ this.key = key; this.val = val; } } Node head = new Node(-1, -1); Node tail = new Node(-1, -1); int cap; HashMap m = new HashMap(); public LRUCache(int capacity) { cap = capacity; head.next = tail; tail.prev = head; } // function to add a new node private void addNode(Node newnode){ Node temp = head.next; newnode.next = temp; newnode.prev = head; head.next = newnode; temp.prev = newnode; } // function to delete a node private void deleteNode(Node delnode){ Node prevv = delnode.prev; Node nextt = delnode.next; // join previous and next to remove node prevv.next = nextt; nextt.prev = prevv; } public int get(int key) { // if present in map if(m.containsKey(key)){ Node resnode = m.get(key); // stores value int ans = resnode.val; // makes it most frequently used // remove from map m.remove(key); // remove from node deleteNode(resnode); // add to node addNode(resnode); // add to map m.put(key,head.next); return ans; } // is not present in map and LL return -1; } public void put(int key, int value) { // if it already contains key so we can later readd if (m.containsKey(key)){ Node curr = m.get(key); m.remove(key); deleteNode(curr); } // if it is of filled size if (m.size() == cap){ m.remove(tail.prev.key); deleteNode(tail.prev); } // simply add it at head addNode(new Node(key, value)); // put key and new address in map m.put(key, head.next); } }

[@vladimirprotein9693]

Thanks brother!!

[@closer9689]

Awesome👏👏👏👏....................I was using a Deque😦

[@sreejasree7427]

Thankyou sir , best explanation

[@hameedmulani21]

Mind Blowing

[@nagmakhan672]

Amazing. Thanks a lot Need java code if possible

[@Auto_Enthusiast]

awesome explanation , bhai appke smjhane ka kya hi jawaab hai , mtlb shbd km pd jayenge!!!

[@codestorywithMIK]

Means a lot 😇🙏

[@invinciblearmyvlogsshorts7911]

bhaiya , i don't know , but the way you build intution in a problem is something which make you unique....pls make videos on recursion and DP.. we will always support you

[@codestorywithMIK]

Thank you so much Sure thing

[@kunal4710]

BHAIYA ONE DOUBT IF THIS QUESTION WILL BE ASKED IN A INTERVIEW AND THE INTERVIEWER DIDNT ALLOW US TO USE STL LIST THEN WHAT WILL WE DO I DONT THINK I CAN MAKE MY OWN DOUBLY LINKED LIST CLASSS AND TGEN EVERYTIME CHANGE LINKS FOR EVERY OPERATION?

[@codestorywithMIK]

Hi Kunal, It actually depends. There can be many scenarios : 1) If you are a fresher then they will expect you to know about Data Structure and would want you to implement dll 2) Since this qn is intself a lengthy, and implementing dll separate might take a lot of time because of which interviewer might not be interested in the dll implementation 3) Interviewer might only ask how will you implement dll and then let you continue with stl . 4) When I had cracked Microsoft, there was a qn which was short and it required min heap. Since the qn was short, i was asked to implement min heap on my own.

[@kunal4710]

@@codestorywithMIK Got it bhaiya thanks for the reply 🤩

[@MounikaEMB]

I have a confusion, why we need to remove [2,2] in the beginning, as per algo we need to remove [1,1] which is added before [2,2].. Can you explain it clearly??

[@codestorywithMIK]

Because [1,1] was just recently used. Hence it’s fresh. [2,2] was not recently used that’s why it’s not fresh. NOTE : Qn does not say to remove those which added before, qn is saying to remove those which was LEAST recently used . See 3:33 of this video. Hope that will help 😇🙏❤️

[@abhishekkarn8918]

Amazing explanation.Way to go brother.

[@JJ-tp2dd]

Thanks, bhai. Below are both the Java solution: Brute Force: class LRUCache { List cache; int n; public LRUCache(int capacity) { n = capacity; cache = new ArrayList(); } public int get(int key) { for(int i = 0 ; i < cache.size(); i++){ if(cache.get(i).key == key){ int val = cache.get(i).value; Pair temp = new Pair(key, val); cache.remove(i); cache.add(temp); return val; } } return -1; } public void put(int key, int value) { for(int i = 0 ; i < cache.size(); i++){ if(cache.get(i).key == key){ cache.remove(i); cache.add(new Pair(key, value)); return; } } if(cache.size() == n){ cache.remove(0); cache.add(new Pair(key, value)); } else { cache.add(new Pair(key, value)); } } } class Pair { int key; int value; Pair(int _key, int _value){ this.key = _key; this.value = _value; } } Optimal: class LRUCache { Node head = new Node(0, 0), tail = new Node(0, 0); Map < Integer, Node > map = new HashMap(); int capacity; public LRUCache(int _capacity) { capacity = _capacity; head.next = tail; tail.prev = head; } public int get(int key) { if (map.containsKey(key)) { Node node = map.get(key); remove(node); insert(node); return node.value; } return -1; } public void put(int key, int value) { if (map.containsKey(key)) { remove(map.get(key)); } if (map.size() == capacity) { remove(tail.prev); } insert(new Node(key, value)); } private void remove(Node node) { map.remove(node.key); node.prev.next = node.next; node.next.prev = node.prev; } private void insert(Node node) { map.put(node.key, node); Node headNext = head.next; head.next = node; node.prev = head; headNext.prev = node; node.next = headNext; } class Node { Node prev, next; int key, value; Node(int _key, int _value) { key = _key; value = _value; } } }

[@codestorywithMIK]

You are a Life saviour.

[@nagmakhan672]

Wow. tysm

[@JJ-tp2dd]

thank you bhai and Nagma

[@nit8826]

Sir,Issi ke sath LFU ka bhi dekh lete toh kaam ho jata

[@codestorywithMIK]

LFU video uploaded in this playlist 🙏😇❤️

[@shikharpandya4927]

Thanks a lot sir

[@gui-codes]

This is far far better than any other guy on youtube explaining this.

[@xyz19891]

Shouldn't you be using unordered_map instead of map? Because time complexity of find() in map is O(logn) whereas in unordered_map is O(1).

[@UECAshutoshKumar]

Thank you 🙏

[@ayushdhoot9784]

@codestorywithMIK dequeue se push and pop o(1) mai hota hai so y we had used DLL rather than dequeue

[@floatingpoint7629]

thanks for the explanation. i have done this question before. revisiting it for revision

[@codestorywithMIK]

Awesome 😇

[@DurgaShiva7574]

won't the list.pop_back() becomes equivalent to traversing the whole list and deleting the last element, which makes the time complexity of this operation as O(n), so it doesn't make difference if we insert the newest element at first, or at last, because either the insertion , or deletion will be still o(n) ??

[@adhikari669]

Bhaya dll.pop_back() constant complexity h ? Ya o(n)

[@codestorywithMIK]

Thanks for asking this Qn. It’s O(1) i.e. CONSTANT You can read more here : cplusplus.com/reference/list/list/pop_back/

[@adhikari669]

Bhaya ye function constant time m kaise kaam kr lete h jaise ki vector.size () h ,Bina traverse krre kaise ?

[@twi4458]

@@adhikari669 kyuki iski internal implementation class se hui hai, to bas apn uska method call kar rhe getsize() type to vo O(1) me return karta

[@adhikari669]

@@twi4458Ha ye to m smjha ki class m ek member function h iss naam ka to call kro or answer return krega pr ye Bina traverse kree size kaise pta kr leta h , ye puchna tha..

[@souravjoshi2293]

Dude this was 🔥. Now, waiting for LFU cache

[@wearevacationuncoverers]

LEGENDARY explanation I had watched other channels as well, this is by far the best explanation

[@dilshadalam4546]

You are doing great plz keep doing this .

[@sukritiguin5637]

You deserve 100k subs.

[@codestorywithMIK]

Means a lot ❤️

[@souravjoshi2293]

Soon this guy will reach 100k I am pretty sure

[@Saryupareen]

goat..tecahing

[@shreyasrivastava368]

Hey please continue the graph concept series.. thankyou

[@shabananoor9423]

++

[@khanakpatwari2587]

why are we specifically pushing the recent ones in the front of the list? Can't we push them at the back instead if we want to?

[@souravjoshi2293]

Relieved that taj ka POTD ka already video hai is channel ka 🥳🥳🥳🥳

[@adhikari669]

Bhaya apni leetcodeprofile share kroo 🙏

[@codestorywithMIK]

Hey Sourav, Find all here github.com/MAZHARMIK

[@rahulmaurya6451]

bhaiya.., i think it's time to take one step forward and go for GFG's POTD also.. what's your thought ?? ,, GFG coders don't get are Quality Explanation on entire KZbin ,, no one explains questions like you,,

[@codestorywithMIK]

Totally agree. Just need to crunch more time to cover gfg potd. Will soon start this also

[@rahulmaurya6451]

@@codestorywithMIK Yaa.. i know you already working hard and had a very busy schedule and still uploading video's consistently... your dedication is so much appreciable 🙏🙏

[@codestorywithMIK]

@rahulmaurya6451 Means a lot 🙏🙏🙏

[@shabananoor9423]

Perfect explanation. Thanks for the brute force

[@abhishekverma7604]

bhya tell me onre thing , thoda awckward question h but dekh lena ek vector m n elements hai to uski run time complexity O(n) hai, but agar hm vector of pair store kr rhe hn to uski complexity O(n^2) honi chahiye naa, because single index store two values in that data structure.

[@ShivamMishra-fo1wx]

what 's the explanation bro great !

[@codestorywithMIK]

Thank you so much Shivam ❤️❤️

[@GeneralistDev]

Wow daily challenge already avalaible

[@codestorywithMIK]

Yes 😇🙏👍🏻 Thank you so much for seeing my video 🙏

[@gocrazy6177]

Why can't we use only map here ?

[@nikhilsatyam4815]

why don't we use deque for this problem ?

[@yogeshagarwal403]

in first approach get method is not quadratic, it is linear.

[@gulshankumar5552]

bro keep uploading because your way of understanding is very good and communication also, very helpful for me ,

[@mayur_madhwani03]

Small correction push_back in dll is O(1)

[@informative180]

first I was watching striver's video then i saw u also have uploaded on it , automatically finger went there and clicked on your video.🤗

[@codestorywithMIK]

Thank you so much for trusting my channel and explanation 😇🙏❤️

[@souravjoshi2293]

lol same

[@wearevacationuncoverers]

same 2 same

[@ridj41]

bhai thoda chotti video banaya karo,warna thummbnail se hi bhagna padta hai

[@nikhilsatyam4815]

kindly add timelines in videos bhaiya.

[@ankitachaturvedi2822]

Great explanation! Thank you so much..💫💫

[@codestorywithMIK]

You are so welcome 😊

[@pkm754]

cache[key] undeclare hai na??

[@animesh414]

Please make video on comparator function in C++.

[@codestorywithMIK]

Sure soon.

[@adarshkhetan9424]

Can we use queue or dequeue ( stl c++) ??

[@keertilata20]

finally ye question ab jake meko clear ho gya is video se... thank you so much bhaiya 🥺🥺🥺

[@codestorywithMIK]

Thank you so much 😇🙏

[@RishabhDhiman-zf5wd]

Great content❤

[@adhikari669]

Bhaya kvi aisa hua h ki aapko kisi daily problem m doubt ho or aap discussion section m gye ho. 😅

[@codestorywithMIK]

Indeed Yes Sourav. But sometimes i hate the solutions provided there because most people don’t explain in detail. So i just try to simplify and produce my own simplified explanation ❤️

[@rev_krakken70]

Cant i use hashmap + queue here?

[@shivsakthi37]

U r damn good in explaining things bro 🙏 please could you guide us further on how to improve dsa it would be great help 🍀

[@codestorywithMIK]

Thanks a lot Harsh ❤️❤️ I will soon make a video on guide also. Hope that will help

[@shivsakthi37]

@@codestorywithMIK it will definitely help me a lot bro thanks looking forward to watch it 🤞

[@beenasatyendrapal6405]

You skillfully simplify complex ideas, making learning enjoyable. love from this side....

[@codestorywithMIK]

❤️❤️🙏🙏

[@informative180]

bhai u r exceptional , tysm😍

[@codestorywithMIK]

Thank you so much 🙏❤️😇

[@pritishpattnaik4674]

Absolutely mindblowing , how u constructed the problem by taking it step by step , line by line , BEST of all

[@codestorywithMIK]

Thank you so much Pritish ❣

[@NiteshYadavnitw]

wonderful

[@sachinmohanty4577]

nice ❣

[@codestorywithMIK]

Thank you so much Sachin.

[@k-CE-OmkarPathak]

Awesome bhaiya op

[@sidharthdhiman4522]

one of the best explanation for this question but sir one doubt will interviewer would ask us about the internal implementation of this doubly linked list ?

[@codestorywithMIK]

Thanks a lot Sidharth. Actually it totally depends if you are a fresher they ask for implementation. But for questions like these, they dont ask internal implementation because this question itself is lengthy

[@danishsinghjamwal627]

Thankss. Your channel will definitely grow. You have a way with explaining.

[@codestorywithMIK]

Thanks a lot Danish ❤️❤️❤️

[@shabananoor9423]

Come soon

[@animesh414]

1584. Min Cost to Connect All Points, Make Video on it.

[@codestorywithMIK]

Sure Animesh. Soon

[@niteshk0487]

class LRUCache { public: class node { public: int key; int val; node *next; node *prev; node(int k, int v) { key = k; val = v; } }; node *head = new node(0,0); node *tail = new node(0,0); int cap =0; unordered_map mp; LRUCache(int capacity) { cap = capacity; head->next = tail; tail->prev = head; } void deleteNode(node *root) { mp.erase(root->key); node *nextNode = root->next; node *prevNode = root->prev; prevNode->next = nextNode; nextNode->prev = prevNode; } void addNode(node *root) { mp[root->key] = root; node *temp = head->next; head->next = root; root->next = temp; temp->prev = root; root->prev = head; } int get(int key) { if(mp.find(key) != mp.end()) { node *curr = mp[key]; int ans = curr->val; deleteNode(curr); addNode(curr); return ans; } return -1; } void put(int key, int value) { node *temp = new node(key, value); if(mp.find(key) != mp.end()) { node *curr = mp[key]; deleteNode(curr); mp.erase(key); } if(mp.size() == cap) { mp.erase(tail->prev->key); deleteNode(tail->prev); } addNode(temp); mp[key] = temp; } };

[@niteshk0487]

@Devender Verma 😂😂😂👍🏻

[@EB-ot8uu]

I think this is the only video which helped me understand the approach clearly. thank you so much

[@HarshMishra-pu1rn]

6k Soon Bhhaiya Love You

[@codestorywithMIK]

Hope so 🥹 Thank you so much Harsh ❤️🙏🙏

[@codestorywithMIK]

It’s 6k now - kzbin.infoXxYKzdIp1rI?feature=share Thank you for your well wishes Harsh 😇🙏❤️

[@HarshMishra-pu1rn]

@@codestorywithMIK Welcome Now It will be 10K as your way of teaching is excellent

[@raftywate]

🙇‍♂🙏

[@snehagoyal4978]

Thanks for the video sir, loving your content.

[@codestorywithMIK]

Thanks Sneha. Welcome to my channel

[@SachinKumar-cd1sg]

The Best Explanation Possible

[@codestorywithMIK]

Thank you so much Sachin ❤️🙏

[@monjuralam7346]

Unbelievable explanation. Hats off!!

[@codestorywithMIK]

Thank you so much ❣

[@Rterusjwhhsjsus]

Awesome explanation, loved it !!

[@codestorywithMIK]

Thank you so much ❣

[@niteshk0487]

dll create krke fir btana next if possible kyuki stl wala thoda confusion h

[@sakshamsharma648]

woaaahhhh explanation!! superb

[@codestorywithMIK]

Thank you so much ❣

[@divyangdheer7292]

mera kyo accept nhi ho rha?? ye test case galat hai ["LFUCache","put","put","get","get","get","put","put","get","get","get","get"] [[3],[2,2],[1,1],[2],[1],[2],[3,3],[4,4],[3],[2],[1],[4]] Correct ans: [null,null,null,2,1,2,null,null,3,2,-1,4] Wrong ans by leetcode: [null,null,null,2,1,2,null,null,-1,2,1,4]

[@codestorywithMIK]

Please share your code

[@harikeshsingh93]

amazing explanation.keep it up

[@codestorywithMIK]

Thank you so much Harikesh ❤️❤️❤️

[@DR-mq1le]

great explanation! thanks!

[@codestorywithMIK]

Glad it was helpful! 😇

[@AlishaKhan-ww3io]

This is one of the finest explanations I have encountered for this problem. Not even famous other youtubers made it this easy

[@StudyChannel-zq4bw]

Amazing brother ❤

[@codestorywithMIK]

Thank you so much 😇❤️

[@pulastyadas3351]

really awesome explanation

[@codestorywithMIK]

Thank you ❤️😇

[@RajSingh-te1uo]

Bhai bhai bhai Kya samjhaya hai 💯

[@codestorywithMIK]

Thanks a lot 😇🙏

[@GirishJain]

🔥

[@GirishJain]

awesome explanation

[@codestorywithMIK]

Thanks a lot Girish ❤️

[@akki8534]

why did't you use unordered_map?

[@codestorywithMIK]

unordered_map in C++ doesn’t allow keeping pair inside it.

[@akki8534]

@@codestorywithMIK i used unorderd_map and it passed all test cases. unordered_map does't allow pair as key but it allow as value

[@codestorywithMIK]

@akki8534 Yes yes. You are right ❤️

[@Raj10185]

Good explanation but I found and coded up A better and easy solution using the same DLL and map but i am using a inbuilt STL splice mathod which makes life very easy for transfering of node in linked list to begin code for the same :- class LRUCache { public: // optimal approach +. use an map and doubly linkedlist use STL // use an STL splice function to esy transfer of node in DLL unordered_map mp; // {key , value == iterator of list} list dll; //{key,value} int cap; LRUCache(int capacity) { cap = capacity; } int get(int key) { int value = -1; // first check if is present in map or not if( mp.find(key) == mp.end() ) return -1; else //key exists { auto it = mp.find(key) ; value = it->second->second; //this we need to return // lets place it at front dll.splice(dll.begin(),dll,it->second); } return value; } void put(int key, int value) { // // first check if is present in map or not if( mp.find(key) != mp.end() ) //update its value and move to front { auto it = mp.find(key); //value updation it->second->second = value ; // move to front dll.splice(dll.begin(),dll,it->second); return ; } if(cap==mp.size()) //map size == list size use any one but mp.size is better tc { //need to delete from back //lets store the key to delete we have to delete from map also int key_to_delete = dll.back().first; dll.pop_back(); mp.erase(key_to_delete); } // insert at begin in list and insert in map dll.emplace_front(key,value); //emplace front or push_front but emplace front have better TC mp[key] = dll.begin(); } };```

[@sharibsaifi-vw4or]

Excellent explanation understood it very well 👍

[@codestorywithMIK]

Thanks a lot Sharib ❤️