L18. Implement LRU Cache

[@HMBDM1976]

Hi Striver, I just wanted to thank you for your incredible DSA tutorials. Your clear explanations and thorough examples have made a huge difference in my understanding and proficiency. Thanks to your videos, I've become very proficient in DSA, which has significantly boosted my confidence and performance in my coding Keep up the great work, you're making a big difference!

[@abhimanyus8757]

how it, am started today, did u make notes?

[@omkarshendge5438]

@@abhimanyus8757 notes is compulsory

[@harshitaninama5235]

Finally the stack playlist is here!!! thankyou so much!

[@yashsharma6108]

You are such a hardworking fellow .... seriously you inspire me everyday to work even harder to make myself better day by day...thanku striver😊

[@DevilJim-p1s]

Bro I'm just looking for a review I've just started are you good enough now at the end?

[@CodewithKing360]

Bhai kitna din lagega is karne me

[@karthik-varma-1579]

I Have Learned this Technique in my Operating Systems Subject in Page Replacement Algorithms using Stack And Now I am in My 3-1 Semester Again visiting to the LRU cache in Data Structures seems the main use of it and Striver Has Very Well Explained it. And Now I am able to Do My own for LFU Cache. Thank God!!!

[@akesh500]

Please consider doing a series on Strings.

[@_ankit_gupta_]

just going to start older stack playlist but got new playlist thanks you striver !!!

[@agrawalmitesh4395]

Gem , just saw your explanation of first 13 min how to do it , and was able to implement it myself , in very less time

[@THOSHI-cn6hg]

he has started taking yt channel for granted

[@prithvirathore7436]

Hello ,Raj sir I hope this comment finds you well,as String is the most important topic in the dsa when it comes to placements,so it's a humble request from you to please make videos on strings .as my placements are going on and arrays and strings are much asked questions

[@aryanbundela6031]

My goat grinding hard at night

[@user2k56]

@takeUforward We need a string series brother plz , as soon as possible.#A2Z DSA

[@omkarshendge5438]

currafterhead→prev = node; this step is missing in the insertafterhead function

[@AbhinavMohanParaverse]

Wanted to make a comment to point this out, but you got it!

[@Sumantashee-e3w]

Sir you are a good teacher in DSA.... I'm injoy this playlist full stack playlist please 🙏🙏

[@mohammedrayan2192]

Hello raj bhaiya. Thank very much for taking your valuable and effort to teach DSA. Please create a video on Java Collection Frameworks.

[@abhiroopmokshagnabheemineni]

Such a beautiful explanation!! Kudos!

[@HEMANTPORWAL-t7d]

thank you striver for all these interesting stuffs

[@swathigp3818]

Incredible explanation

[@kunal5077]

Very Nice explanation. Eagerly waiting for strings playlist

[@swaroopparida0429]

Hi striver please bring playlist on string

[@ishan9604]

Thank You Striver , you really help me in trees and graph series!

[@FarziWada-q3r]

The last video of a2z sheet was added 4 months ago. When will the next videos be uploaded?

[@ShivamGupta-ei2sv]

Bhaiyya I am eagerly waiting for string playlist

[@umeshkaushik710]

Hi Bhaiya, Please complete Strings list from the sheet, and I think Strings question might need some more addition. When we can except String Playlist out ?

[@harigs72]

Oh my goodness! I found the optimal solution of it by myself. I have just come here to see the most optimal solution of it..😅

[@HemangSinghal-op5ep]

Wonderful Explanation

[@madhupathak7772]

Hello sir!! Please upload the heaps playlist asap

[@updownftw]

Why is this in the Stack and queue playlist ?

[@KeigoEdits]

I respect you a lot striver literally but please take this suggestion into consideration, dont make videos for the topics you already made earlier We are eagerly waiting for strings series and recursion series

[@Jai_Shri_Krishna_Shri_radhe]

If you Reached 13:35 skip to 20:45 Again restarted writing pseudocode

[@akhilesh_ku]

No , firstly he just wrote pseudo code , for second time it's cpp code😅😂

[@omkarshendge5438]

yup exactly

[@omkarshendge5438]

@@akhilesh_ku the first time also it is cpp heavy only bro.

[@AbhijeetChouhanXD]

strings ke videos le aao bhai

[@Hy_there01]

This video lasts longer than my relationship 😂

[@souvikbasak4396]

Bhaiya could you tell beforehand if you going upload any chapter(specsilly graph and dp) playlist which is already available in older playlist , so that instead of the older playlist I could wait a few more days for the newer playlist , like are you going to upload new playlist of graphs and dp , else i will continue with the older one only.

[@arunbhagat8023]

Sir String and Heap Playlist Please....!!!

[@venumsingh]

Thanks for the video. Which software is used for recording the video?

[@AneeshPal-t7y]

I m just not able to get that when we change order of elements so that it becomes the most recently used , why we are not changing the reference i.e. new location in map as now nodes location is changed....

[@karthi2174]

Hello everyone, my placements are starting in March 2025. I have started learning DSA using the TakeUforward SDE sheet and have completed the first 10 problems. However, I was able to understand only 3 of them, and I am struggling to build logic on my own. I am unsure if I am on the right track or where to start. Could you please give me some advice on how to approach solving problems independently and where I should begin? I have programming knowledge but need guidance. I am not aiming to join a big MNC company, but I want to prepare effectively.

[@AbhinavTries]

youre doing just fine bro, you've just started, i've been there, im done with 50% of the sheet yet I struggle with intuition, dont worry just keep practicing comment your own notes in the code, it'll help in revising also whenever you approach a new approach, write it down somewhere

[@FarziWada-q3r]

When will be the next video uploaded?

[@atulwadhwa192]

Will there be any difference if we delete from front and insert at the back? In terms of complexity?

[@ShubhamKumar-vk8me]

Bhaiya String ka video kab tak aajaye, You said you will be uploding it before september

[@Panther_jf]

Bhaiya, would love to learn Binary Trees next, pls❤ And the stack playlist was amazing as always😍

[@KeigoEdits]

Binary trees playlist is already completed, go check out

[@Panther_jf]

@@KeigoEdits I was talking about the new version of binary trees playlist

[@curs3m4rk]

I was able to implement after watching approach of DLL and HashMap, Got stuck at the place where I was able to delete LRU from DLL, but could not find out how to remove that node from hashmap. Storing key, value pair in DLL Node is a great idea. Thanks :)

[@ParthDabhiOfficial]

UNDERSTOOD, Radha Radha

[@prashlovessamosa]

Sir can you please add the solutions in python too I have to visit the third party website to read the code. Very grateful to you for the series.

[@theultimatespo...4205]

Can it be done by using dequeue

[@shresthgupta2670]

legend is here

[@arl0817osho]

does it should be afterhead->prev = node in insert funciton also?

[@rameezalipacific]

I'm from Pakistan and currently pursuing a degree in software engineering. Alongside my studies, I'm dedicating significant time to mastering data structures and algorithms (DSA). However, I'm uncertain if excelling in DSA alone is enough to secure a job at top tech companies like the one you work for. Do I need to develop additional skills, such as web, app, or game development, to increase my chances of success? Also, could you share your experience on when you started focusing on DSA-was it during your degree or afterward?

[@deveshagarwal660]

You mentioned that you will be using a DLL for solving this, but never explained that how did you come to a conclusion of using a DLL. It is also important to explain your choice of using any particular data structure or algorithm when someone is solving problems in an interview.

[@AbhijeetChouhanXD]

Because we are (i) adding elements to front (ii) removing from the back and adding to front In say singly LL, to remove the last element, we would have to travel the list taking O(n) time. Similarly in something like an array, to add an element to the front we would have to shift all the elements, taking O(n) time.

[@MO-fg2cm]

Lru in processors done in maps ?? No way , is this some dsa course then ?

[@THOSHI-cn6hg]

upload next series cmmon bro

[@DrawwithNavi]

cant we just do the same thing using orderedDict, will take similar time and much shorter

[@abhishekagrawal3730]

Bhaiya please string dal do

[@astitvashukla6556]

Bhaiya I am following your DSA series ek baar Java collection kie video daal dijiye bahut help ho jaaegi and bhaiya meine kaafi se question practice kre solve kre but confidence and logic dono build nhi ho paa rha... Need some guidance

[@sanchitkaul5084]

Rather than "DeleteNode" a better name of the function would be "DetachNode" .

[@Leo-id4uh]

code 360 not showing some of the code in the solved list which i was done before, can anyone tell about this

[@KedarBhawthankar]

striver is legend

[@soumyadey4500]

can anyone help why should i use "m[key_] = head->next" under get function?

[@SanketPatil-gm7pb]

sir plz upload the next playlist of heap

[@yogeshwardayalagarwal4228]

Why is it not a part of linked list playlist?

[@akhilesh_ku]

It uses put and get

[@odorlessflavorless]

~ 17:54 'we have touched someone, ... least recently used' --- we have to put in front because it is the most recently used and not the least recently used.

[@adhiraj2964]

Striver bhaiya next topic string cover kariye pleaseee

[@NirajPatel-ug2ew]

my code: struct Node { int val; int key; struct Node* next; struct Node* prev; Node(int value, int x) { val = value; key = x; next = NULL; prev = NULL; } }; class LRUCache { public: unordered_map m; int size, currsize; struct Node* head; struct Node* tail; LRUCache(int capacity) { size = capacity; head = NULL; tail = NULL; currsize = 0; } int get(int key) { if (m[key] == NULL) return -1; struct Node* temp = m[key]; if (temp == head) { return temp->val; } if(temp == tail){ tail = temp->prev; } temp->prev->next = temp->next; if (temp->next != NULL) { temp->next->prev = temp->prev; } temp->next = head; head->prev = temp; head = temp; return head->val; } void put(int key, int value) { if (m[key] == NULL) { if (currsize < size) { struct Node *temp = new Node(value, key); m[key] = temp; currsize ++; if(head == NULL){ tail = temp; head = temp; return; } temp->next = head; head->prev = temp; head = temp; return ; } else { struct Node *temp = new Node(value, key); m[tail->key] = NULL; if(head == tail){ tail = temp; head = temp; m[key] = head; return ; } tail = tail->prev; temp->next = head; head->prev = temp; head = temp; head->val = value; m[key] = head; return ; } } else { struct Node* temp = m[key]; if (temp == head) { temp->val = value; return; } if(temp == tail){ tail = temp->prev; } temp->prev->next = temp->next; if (temp->next != NULL) { temp->next->prev = temp->prev; } temp->next = head; head->prev = temp; temp->val = value; head = temp; return ; } return ; } }; /** * 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); */

[@GuptaHarshHemant]

thanks striver

[@SoRandominfo]

U missed LFU cache video?

[@brokegod5871]

He solved it before in an older video, you can see in the playlist

[@akhilesh_ku]

See down 😅 , KZbin suggesting you

[@maverick_8707]

He has included in the playlist at last

[@kanishasiva6731]

Striver 💯🙏💗

[@iamnottech8918]

mojj krdi bhaiya

[@DeadPoolx1712]

UNDERSTOOD;

[@atulwadhwa192]

My approach using dummy node class Node{ public: int key,val; Node* next; Node* prev; Node(int key,int val){ this->key = key; this->val = val; next = NULL; prev = NULL; } }; class LRUCache { int size,capacity; Node* head; Node* tail; unordered_map mp; public: LRUCache(int capacity) { size =0; this->capacity = capacity; head = new Node(-1,-1); tail = new Node(-1,-1); head->next = tail; tail->prev = head; } void insertNodeAtEnd(Node* node){ // detachment of node Node* prevNode = node->prev; Node* nextNode = node->next; if(prevNode != NULL) prevNode->next = nextNode; // for new node prevNode would be null if(nextNode != NULL) nextNode->prev = prevNode; // for new node nextNode would be null // attachment of node at end Node* tailPrev = tail->prev; tailPrev->next = node; node->prev = tailPrev; node->next = tail; tail->prev = node; } int get(int key) { uj7i8if(mp.find(key) == mp.end()) return -1; Node* node = mp[key]; insertNodeAtEnd(node); return node->val; } void put(int key, int value) { if(mp.find(key)!=mp.end()){ Node* node = mp[key]; node->val = value; insertNodeAtEnd(node); } else{ Node* node = NULL; if(size == capacity){ node = head->next; mp.erase(node->key); node->key = key; node->val = value; // insertNodeAtEnd(node); } else{ size++; node = new Node(key,value); // insertNodeAtEnd(node); } insertNodeAtEnd(node); mp[key] = node; } } }; /** * 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); */

[@abhinavabhi3568]

Understood

[@AbhishekKumar-td5zu]

understood!!

[@mayanksaini4827]

kya haal h striver bhai k👀👀 ?

[@Aman-Gairola]

he forgot change afterhead->prev = node in insert funciton

[@sanchitdeepsingh9663]

thanks sir

[@shantipriya370]

can you pls give python code link..

[@ahmadrasheed2598]

C++ Implentation: class Node { public: int key; int val; Node* prev; Node* next; Node(int key, int val) : key(key), val(val), prev(nullptr), next(nullptr) {} }; class LRUCache { private: void deleteNode(Node* node){ if (node == nullptr) { return; } node->prev->next = node->next; node->next->prev = node->prev; } void insertAtHead(Node* node){ if (node == nullptr) { return; } node->next = head->next; head->next = node; node->prev = head; node->next->prev = node; } Node* head = new Node(-1, -1); Node* tail = new Node(-1, -1); public: int capacity = 0; unordered_map mp; LRUCache(int capacity) { head->next = tail; tail->prev = head; this->capacity = capacity; mp.clear(); } int get(int key) { if(mp.find(key) != mp.end()){ // key exists Node* node = mp[key]; deleteNode(node); insertAtHead(node); return node->val; } else{ // key doesnt exist return -1; } } void put(int key, int value) { if(mp.find(key) != mp.end()){ // key exists update Node* node = mp[key]; node->val = value; deleteNode(node); insertAtHead(node); } else{ Node* node = new Node(key, value); // key doesnt exist add if(mp.size() == capacity){ //remove least recent Node* lru = tail->prev; deleteNode(lru); mp.erase(lru->key); insertAtHead(node); mp[key] = head -> next; } else{ //add insertAtHead(node); mp[key] = head -> next; } } } };

[@FreeFire-f7e]

Hello sir I will go in IIT ropar what language which I do start?

[@siddhukanchumarthi961]

start with c and continue with c++

[@SwastikMohanty-rq6qn]

start with c++ itself

[@sarveshkanwar1300]

cpp

[@Akshay-c8g]

Hindi

[@FreeFire-f7e]

@@Akshay-c8g I am not understand what do you tell

[@user-zp1dv4yh5e]

Here, you didn't handle the case where the key could be same be value might be different.

[@impatientgaming9868]

niceee

[@UttamSingh-vn1yf]

string krwado

[@vineet1728]

The editor forgot something to clip

[@sandeepxt99]

❤

[@SajanKumar-ec2us]

please explain c++ written don't write suedo code

[@studystuff51]

Please learn how to write code by yourself instead

[@razorzeast4133]

I'm the first one

[@nikhil_squats]

curr_after_head->prev=node; in addAfterHead Func

[@chiragdusad2015]

Stiver where are your hairs going😢 Looks like our brother is getting older

[@ishan9604]

First Comment