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 😇🙏

[@Auto_Enthusiast]

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

[@codestorywithMIK]

Means a lot 😇🙏

[@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 ❤️❤️❤️

[@beenasatyendrapal6405]

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

[@codestorywithMIK]

❤️❤️🙏🙏

[@wearevacationuncoverers]

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

[@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 ❣

[@Sanjeev.Network]

your approach is best over any KZbin video. one KZbin say hope you are extremely well and directly become parrot, they only say... but you r best.

[@codestorywithMIK]

Thank you for the kind words 🙏😇

[@hameedmulani21]

Mind Blowing

[@AlishaKhan-ww3io]

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

[@saurabhnishad9631]

one of the best tutor ever got ❤

[@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

[@gulshankumar5552]

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

[@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

[@gui-codes]

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

[@aryanmishra199]

The build up was great bhai cinema

[@keertilata20]

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

[@codestorywithMIK]

Thank you so much 😇🙏

[@danishsinghjamwal627]

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

[@codestorywithMIK]

Thanks a lot Danish ❤️❤️❤️

[@project_eth]

18:59 what a brilliant build up bro. crazy

[@souravjoshi2293]

Dude this was 🔥. Now, waiting for LFU cache

[@sal_diaz5964]

THANK YOU , understood clearly please keep making such videos

[@codestorywithMIK]

I'm glad it helped! 🙌

[@EB-ot8uu]

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

[@shabananoor9423]

Perfect explanation. Thanks for the brute force

[@floatingpoint7629]

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

[@codestorywithMIK]

Awesome 😇

[@informative180]

bhai u r exceptional , tysm😍

[@codestorywithMIK]

Thank you so much 🙏❤️😇

[@ankitachaturvedi2822]

Great explanation! Thank you so much..💫💫

[@codestorywithMIK]

You are so welcome 😊

[@souravjoshi2293]

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

[@gulshanmathur3738]

very welled explain man god bless you...

[@monjuralam7346]

Unbelievable explanation. Hats off!!

[@codestorywithMIK]

Thank you so much ❣

[@dilshadalam4546]

You are doing great plz keep doing this .

[@aizad786iqbal]

This is what I used in java, not the best approach, but it worked :) this is today's GFG POTD class LRUCache { Map cache; int limit; public LRUCache(int capacity) { limit = capacity; cache = new LinkedHashMap(capacity){ @Override protected boolean removeEldestEntry(Map.Entry eldest){ return size() > limit; } }; } public int get(int key) { int x = -1; if(cache.containsKey(key)){ x = cache.get(key); cache.remove(key); cache.put(key, x); } return x; } public void put(int key, int value) { if(cache.containsKey(key)){ cache.remove(key); } cache.put(key, value); } }

[@snehagoyal4978]

Thanks for the video sir, loving your content.

[@codestorywithMIK]

Thanks Sneha. Welcome to my channel

[@abhishekkarn8918]

Amazing explanation.Way to go brother.

[@sourabhsharma2511]

keep uploading such beautiful videos bhaiya

[@codestorywithMIK]

❤️😇🙏

[@DeadCode_Debugs]

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

[@UECAshutoshKumar]

Thank you 🙏

[@RajSingh-te1uo]

Bhai bhai bhai Kya samjhaya hai 💯

[@codestorywithMIK]

Thanks a lot 😇🙏

[@Rterusjwhhsjsus]

Awesome explanation, loved it !!

[@codestorywithMIK]

Thank you so much ❣

[@sakshamsharma648]

woaaahhhh explanation!! superb

[@codestorywithMIK]

Thank you so much ❣

[@sukritiguin5637]

You deserve 100k subs.

[@codestorywithMIK]

Means a lot ❤️

[@souravjoshi2293]

Soon this guy will reach 100k I am pretty sure

[@sauravchandra10]

Python code, with implementation of each and every function. class LRUCache: class Node: def __init__(self, key: int, val: int): self.key = key self.val = val self.next: 'Node' = None self.prev: 'Node' = None def __init__(self, capacity: int): self.capacity = capacity self.head = self.Node(-1, -1) self.tail = self.Node(-1, -1) self.map = {} # head MRU .... .... LRU tail self.head.next = self.tail self.tail.prev = self.head def get(self, key: int) -> int: # key found, delete it, and add it to head.next if key in self.map: cur = self.map[key] val = cur.val # delete and add self.deleteNode(cur) self.addNode(cur) # update the map self.map[key] = self.head.next return val return -1 def put(self, key: int, value: int) -> None: if key in self.map: # delete toRemove = self.map[key] self.deleteNode(toRemove) # add self.addNode(self.Node(key, value)) # update self.map[key] = self.head.next return # remove LRU if cache size exceeds if len(self.map) == self.capacity: del self.map[self.tail.prev.key] self.deleteNode(self.tail.prev) self.addNode(self.Node(key, value)) self.map[key] = self.head.next def deleteNode(self, node: Node): prev, next = node.prev, node.next prev.next = next next.prev = prev def addNode(self, node: Node): temp = self.head.next node.next, node.prev = temp, self.head self.head.next, temp.prev = node, node # Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value)

[@Akashkumar_12]

Crystal clear explanation 😊❤

[@codestorywithMIK]

Thanks for the kind words! ❤️

[@sreejasree7427]

Thankyou sir , best explanation

[@closer9689]

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

[@SachinKumar-cd1sg]

The Best Explanation Possible

[@codestorywithMIK]

Thank you so much Sachin ❤️🙏

[@pulastyadas3351]

really awesome explanation

[@codestorywithMIK]

Thank you ❤️😇

[@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 🤞

[@harikeshsingh93]

amazing explanation.keep it up

[@codestorywithMIK]

Thank you so much Harikesh ❤️❤️❤️

[@StudyChannel-zq4bw]

Amazing brother ❤

[@codestorywithMIK]

Thank you so much 😇❤️

[@shreyasrivastava368]

Hey please continue the graph concept series.. thankyou

[@shabananoor9423]

++

[@nagmakhan672]

Amazing. Thanks a lot Need java code if possible

[@DR-mq1le]

great explanation! thanks!

[@codestorywithMIK]

Glad it was helpful! 😇

[@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 ❤️❤️

[@RishabhDhiman-zf5wd]

Great content❤

[@sharibsaifi-vw4or]

Excellent explanation understood it very well 👍

[@codestorywithMIK]

Thanks a lot Sharib ❤️

[@yt_goluyadav]

sir jab interview mein dsa ke questions aatey hai to humko bas logic likhna hota hai ya fir main ke andr ka code jo hota hai c++ mein woh bhi likhna hota hai?

[@shikharpandya4927]

Thanks a lot sir

[@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

[@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

[@Saryupareen]

goat..tecahing

[@k-CE-OmkarPathak]

Awesome bhaiya op

[@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 ❤️

[@mayur_madhwani03]

Small correction push_back in dll is O(1)

[@GeneralistDev]

Wow daily challenge already avalaible

[@codestorywithMIK]

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

[@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

[@NiteshYadavnitw]

wonderful

[@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!!

[@GirishJain]

🔥

[@GirishJain]

awesome explanation

[@codestorywithMIK]

Thanks a lot Girish ❤️

[@sachinmohanty4577]

nice ❣

[@codestorywithMIK]

Thank you so much Sachin.

[@animesh414]

Please make video on comparator function in C++.

[@codestorywithMIK]

Sure soon.

[@ayushdhoot9784]

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

[@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 🤩

[@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.

[@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 🙏🙏🙏

[@ShivamMishra-fo1wx]

what 's the explanation bro great !

[@codestorywithMIK]

Thank you so much Shivam ❤️❤️

[@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) ??

[@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 😇🙏❤️

[@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?

[@niteshk0487]

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

[@adarshkhetan9424]

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

[@vibhavgupta1989]

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).

[@ridj41]

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

[@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 ❤️

[@sahilbit6301]

bhaiya notes kaise banaye in sabke taki baad me revision karne me aasani rehe plz tell....

[@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..

[@rev_krakken70]

Cant i use hashmap + queue here?

[@oqant0424]

U made it a "Halwa" seriously

[@nikhilsatyam4815]

kindly add timelines in videos bhaiya.

[@nit8826]

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

[@codestorywithMIK]

LFU video uploaded in this playlist 🙏😇❤️

[@nikhilsatyam4815]

why don't we use deque for this problem ?

[@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 😂😂😂👍🏻

[@aniketsinhaju]

Why can't we use only map here ?

[@pkm754]

cache[key] undeclare hai na??

[@raftywate]

🙇‍♂🙏

[@yogeshagarwal403]

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

[@animesh414]

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

[@codestorywithMIK]

Sure Animesh. Soon

[@adhikari669]

Bhaya apni leetcodeprofile share kroo 🙏

[@codestorywithMIK]

Hey Sourav, Find all here github.com/MAZHARMIK

[@shabananoor9423]

Come soon

[@siddhantswarupmallick6710]

Boball !!!!!!!