Implement LRU Cache | Leetcode

Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------------------------------- SDE sheet: bit.ly/takeUfor...
Code Implementation Video: • Implement LRU Cache | ...
✅Use coupon-code "TAKEUFORWARD" for getting 15% for all CN courses: aff.codingninj...
Watch at 1.25x for better experience ..
---------------------------------------------------------------------------------------------------------------------------
Problem Link: leetcode.com/p...
C++: github.com/str...
Java: github.com/str...
---------------------------------------------------------------------------------------------------------------------------
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgC...
✅Please Please SUBSKRIIIBEEEEE the new channel: / @striver_79
---------------------------------------------------------------------------------------------------------------------------
✅Placement Series: • Let's give back to the...
✅Placement Series (Arrays, Sorting..): • C++ and Java |Brute-Be...
✅Hashing Playlist: • Two Sum Problem | Leet...
✅Greedy Playlist: • N meetings In One Room...
✅Recursion Playlist: • L8. Combination Sum | ...
✅Graph Playlist: • 3 MAJOR ANNOUNCEMENTS ...
✅Two Pointer Playlist: • 3 SUM | Brute | Better...
✅Binary Search Playlist: • Nth Root of a Number U...
✅LinkedList Playlist: • Reverse a Linked List ...
✅Advanced DS playlist: • Fenwick Tree Tutorial ...
✅Stack&Queue Playlist: • Implementation of Stac...
✅Greedy Algorithms: • N meetings In One Room...
---------------------------------------------------------------------------------------------------------------------------
If you appreciate the channel's work, you can join the family: bit.ly/joinFam...
✅Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / ​
✅ Instagram: / ​
✅Connect with us: www.google.com... (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa​ #striver #leetcode

[@takeUforward]

DSA Playlists in the comment section ..

[@AdityaPrakashSinha]

Please make a video on BCA Students... Roadmap for off campus placement...

[@AmanKumarSinhaOfficial]

@@AdityaPrakashSinha yes....

[@gamingfingers4523]

@@AdityaPrakashSinha Bruh it's extremely difficult to get a SDE in a product based company by only having BCA try doing MCA yours odds will increase.

[@manaswitadatta]

Any chance of top interview question series from LC?

[@tulika2863]

For some questions even if I have solved the question previously, I do watch your video for crystal clear explanation. Such an amazing teacher you are bhaiya .

[@takeUforward]

Thankyou

[@Gear5-Luffy]

@@takeUforward thankyou ki kya baat ,ye to mera farj hai

[@ipizza9941]

@@Gear5-Luffy acha bkl

[@swaroopchakraborty3488]

One of the finest explanations of LRU Cache. God bless you Striver and more power to you. Such impeccable energy and knowledge of data structures is rarely seen at tandem.

[@aysams2]

+++

[@ankushrai3155]

This course have saved my life. thank you so much. i would have never built confidence in solving problems if it wasn't for u

[@anuraggoswami3534]

That "just is case" has saperate feeling 💻😂

[@binod3204]

That much energy you put, motivating me to stay awake and study. Thanks 💖

[@eldarzakirov5571]

Great explanation, the only note for (11:23) is that repositioning node in doubly linked list doesn't necessarily require deleting node and creating a new one, it may be enough to update the node (and its neighbors) pointers, thereby preserving address of the node unchanged.

[@devanshbhatt7609]

Yeah I was thit the same but still not sure if we can do that in all possible edge cases

[@aaaaz424]

That was my first thought as well. I just dont understand when to use DLL in a problem.

[@Anythiny]

@@aaaaz424 when u hv to do insertion or deletion in middle of the list. in O(1) time(provided we know where our node is)

[@sudhanshusingh-cy9wp]

I dont think, this is going to work, since if you just change the address, you will also need to shift all the next nodes from head, that will take O(n) time

[@saptarshidas488]

This video helped me clear 2nd technical round and eventually get placed at a dream company that came to our college 2 days ago. Thank you so much for making such quality content!

[@masterroyjones4228]

If take you forward was not created i would have been literally aiming for 3.5 pkg but because of take you forward i got my concepts cleared and ready to be at product based company with a lot of confidence💯Thanks Striver Bhai✌️🙏

[@utkarshsharma6650]

did you get placed?

[@namangupta414]

No reply it means it's fake😂

[@codingalley6229]

bhai sabko notification nahi jata, bc kitne negative ho@@namangupta414

[@ayanSaha13291]

Brother, I envy your enthusiasm while teaching. Great video. Thanks a lot.

[@yogeshedekar6078]

For maintaining the order can we not just change the links so that head.next becomes the node that is getting used and the next for that node and prev are adjusted accordingly ? Why to delete the node and add a new one ?

[@ayushbisht2689]

Your energy 💯.

[@sagnikmitra710]

Next level explanation dada

[@piyusht20]

Do we really need to update the address in Hashmap when moving the node to the front? I believe we could just re-adjust the pointers of the existing node. that way there is no need to update the map while updating the frequency. node address remains same.

[@bikrantjajware6062]

same doubt , i think its not necessary to delete the node

[@dhanesh.s]

It will take O(n) time to search the node Right?

[@adityabalodi1185]

@@dhanesh.s No, you already have the node in hashmap so it will be O(1). So you just use some temp variables and change the previous of the node being accessed(say, currenr) to next of current, and head's next pointer to current. Then you change curr.next to whatever head.next was previously. And obviously maintain the previous of all the nodes.

[@stith_pragya]

UNDERSTOOD.............Thank You So Much for this wonderful video................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@sanatbhalla8537]

Why are we deleting the nodes and creating new ones when they shift? We can just manipulate the pointers (prev & next) such that the same node in the memory is pointed to by the head (ie is the first element). Open to suggestions but I think that is a solid way to not modify the hashmap on get operations.

[@bookalicious9849]

Thank You for your explaination videos bhaiya !! Cannot find better explanation than yours in web !!

[@jeevan-23]

striver did you even thought that you would get so much love from students all over India , from working at google, to giving best content, reaching 500k subs, hatsoff man❤❤

[@sayanganguly4806]

if you are facing TLE, change the get function like below. int get(int _key) { if(ump.find(_key)!=ump.end()){ node* resnode=ump[_key]; int res=resnode->val; resnode->prev->next=resnode->next; resnode->next->prev=resnode->prev; addnode(new node(_key,res)); ump[_key]=head->next; delete(resnode); return res; } return -1; }

[@programming_with_niraj.]

delete(resnode) should be commented

[@nithishd6420]

The enthusiasm was on different level💯

[@ankursharma6084]

At first i thought whiteboard is too old school. It might be boring. But after seeing the whole video .I definitely can see your energy level is much higher and thus it becomes more lively and easy to understand. So in short it seems that this style od teaching turns out to be awesome.

[@sugun6875]

Great video! thanks. However, the address of the node wouldn't change after deletion. We are just changing the pointers of the nodes in the DLL.

[@rajeshg3570]

Nice video, I've a question here - For the operation . get(3), you are trying to delete the entry from the middle of the DLL and insert at the front if my understanding is correct. If that's true, my question is- the time complexity of deleting a node from the middle of a DLL is not 0(1), right?

[@Saurabh-lb1uv]

It is O(1) only. Using hashmap we know the address of the middle node, Say it's address is x Then all we have to do is: x -> prev -> next = x -> next; x -> next -> prev = x -> prev; delete x; This will remove the node from the DLL. That means it takes O(1) time for deletion.

[@rajeshg3570]

@@Saurabh-lb1uv thanks for the clarification

[@mousumikundu2680]

Your explanation is superb. How beautifully you explain each and every step. Thank you so much bhaiya,

[@viswanathank2551]

Love u 3000 man best content for programming in earth !

[@adityaathiratha6104]

bro ...Apart from DSA , one cute suggestion from ur Die hard fan....Besides lower beard , also grow mustache, Dont cut mustache , let it grow densely.. only then lower beard suits perfectly :-) Love u loads.

[@aakashyadav6228]

Congratulations on 100k bhaiya !!

[@shreyasingh542]

"This guy" Best explaination one could find over web!

[@webdesignersandip7469]

Really appreciate your passion you put in explaining....

[@original_gangsta_]

OP explanation and energy 👌👌👌🔥🔥🔥

[@jayeshsuthar5590]

Yesterday I was doing SDE sheet 2, completed stack part-1 & missed doing part 2. Today had interview in one of the best startubs in Bangalore & was asked to design LRUcache (couldn't do completely)

[@gauravm1253]

So much energy for teaching bro. Amazing

[@jayadubey_22]

Congratulations for 100K subscribers takeUforward truly deserve this and more 🙌

[@sagartaak4017]

best ever explanation as always !! even I who always try to skip this topic whenever cover up the queue this time watch only concep and implement it on leetcode and after one minor error it works fine BOOST MY CONFIDENCE

[@baap6382]

You are a saviour. You achieve all the success in the world

[@saurabhtrigunayat4071]

we can also solve this question easily using combination of (HashMap+LinkedHashMap) in java.

[@sukhpreetsingh5200]

Love the way u explain😍😍

[@विशालकुमार-छ7त]

from functools import lru_cache But well explained 👍👍

[@takeUforward]

Not allowed in interview

[@विशालकुमार-छ7त]

@@takeUforward ha bhaiya.

[@paragroy5359]

Nice explanation your videos are really good...please keep on making such videos.

[@jeet-smokey]

One of the finest of explanation. Kudos to you for your efforts.

[@adityajain1205]

great explanation as always....but cant we implement using a doubly ended queue(dequeue) ? it will be much easier and will take lesser space

[@TheAnandsingh111]

If you use a queue how will you get an element which is somewhere in between?...it will take more than O(1) time

[@mohdhammadsiddiqui7598]

@@TheAnandsingh111 i think using hashmap we can find , queue + hasmap will it work?

[@TheAnandsingh111]

@@mohdhammadsiddiqui7598 if you use another hashmap for storing addresses of elements in queue...then it can he done. But time complexity will become O(n) for deleting any element. Because queue does not supports removing an element from between.

[@mohdhammadsiddiqui7598]

@@TheAnandsingh111 ohh shit, u are right we can't delete in between elements , now i understood why we use link list because we can rearrange the nodes and their links

[@TheAnandsingh111]

@@mohdhammadsiddiqui7598 cool 🙌

[@vaibhavagarwal1479]

Why is this question marked as a stack/queue question in your sheet?? neither stack nor queue is used?

[@jayeshl5968]

perfect explanation broo...ur doing great

[@tusharnain6652]

Let's check out the C++ and Java Code, "Whenever your heart is broken"

[@wisdomkhan]

Why was this given in Stack and Queues section in SDE sheet?

[@anonymousvoid6356]

striver is on fire in this video. 🔥🔥🔥🔥

[@igaming_]

Thanks for your Efforts

[@darkstudio3170]

10:19 "it does" hit me hard

[@sakshamkapoor5905]

Thank you for this, beautifully explained ❤

[@shuvbhowmickbestin]

one question, if a node already exists and we are asked to update it, why are we updating the node address in the hashmap since if you observe carefully then only the links and the data of the nodes are changing, the address/reference of the nodes themselves are not changing.

[@deyanpetrov4447]

Best explanation I've seen yet, earned yourself a sub

[@kushwanthkapa2041]

We can directly store the value in hash map instead of DLL then also it is same right?

[@harshalgarg1149]

Amazing explanation.

[@kunalverma9777]

when we are performing get() operation and we are shifting that right after head as it is most recently used. But I am not getting the point of changing addresses of same node coz we are just connecting it at other place but in memory it will be saved at the previous address only. Please clear my doubt...

[@takeUforward]

Yes you can improve that point for sure.

[@takeUforward]

Yes you can improve that point for sure.

[@kunalverma9777]

@@takeUforward Thankyou bhaiya

[@ayushshukla2103]

Amazing explanation. Thank you.

[@divyam69]

One of the best explanation

[@akanshapanchal7107]

What a nice way of explanation! More power to you :)

[@susankamajumder9859]

at step 4 of the dry run (i.e put(3,3) ) shouldn't the least recently used value be {1,1} ? why are we replacing {2,2} then ?

[@takeUforward]

Get(1) was done na… before that..

[@susankamajumder9859]

@@takeUforward yes , now it got it. Thank you.

[@amitarya4894]

Great bhai..🙏🙏

[@nexonsensei3793]

Really great explanation👏

[@therealg9542]

I ended up solving the question by utilizing the dictionary (hashmap) and doubly linked list data structures. However, I did not know you could solve it easily using an ordered dictionary in Python. Nevertheless, great explanation!

[@karthiksharma8720]

such a great explanation bro

[@aryansinha1818]

*Thank You so much. Love & Respect always.*

[@vipsclassicalboy]

your energy is the awesome, keep it up bro..

[@dheerajmaurya3418]

Can I use queue data structure instead of DLL??

[@pankajarora8263]

Same doubt because in sde sheet also this question has been included in queue topic and in gfg also queue is included in topic tags.

[@SahilAhuja-hy9gg]

best explanation this ques could ever have

[@codespace747]

Your videos is awesome♥️

[@aakashtiwari9505]

Bahut time se koshish kr rha tha lru ko implement krne ki finnally aapne kra diya 1st like and comment

[@AbhinavSrivastava-xr5jz]

the finesse of a Google engineer 😍🤩

[@karma_kar9623]

This type of T shirts will get you bullied in school/college. Great video btw.

[@swapnanilgupta3046]

Such a great explanation

[@Anurag-kp6wc]

Thanks Bhaiya! You're the best :D

[@shivammehta9661]

Very Nice Explanation....Keep making videos

[@084abhigna_y8]

Data Structures & Algorithm ❌ Data STRIVERS & Algorithm✅

[@sarveshsawant7232]

Great video, one question can't we implement the same with singly linked list?

[@jatilyadav4000]

Thank you soo much Striver @Raj

[@shubhambhadra5370]

Awesome explanation ❤❤

[@deepikasahu1592]

Best explanation so far🙌

[@bhaveshkumar6842]

You explain soooo well!

[@raj_kundalia]

thanks for the explanation!

[@kbhargavi4400]

truly awesome explaination !! : ) Thank you bro !!

[@piyushkumar2437]

Why you have used Doubly LinkedList. Why not use singly linked list and maintain pointers pointing to start and rear. Please advise.

[@shimul6680]

You are a great genius....

[@bhaveshkumar6842]

You can explain anything. You are a legend!

[@aasthajha1051]

awesome...................

[@ManishaKumari-lp4kw]

Explanation and Energy !!!!💯🔥

[@NAVEENKUMAR-ch4gf]

amazing explanation!!!!!

[@noNameCapatin]

How we maintain the min freq in O(1). I mean how we find which is the current least frequency and how we change the Least frequency during get and put can you explain that logic as well ?

[@narendranarumugavadivelu8648]

You can always insert the latest node at front and LRU node at rear. So when wanted to remove LRU node just point the rear to previous of current rear node

[@muskangupta5873]

big thanks bhaiya.. such a nice explanation🤩

[@akashchaudhury3240]

Nice explanation 🔥

[@OMPRAKASH-is7fj]

best u r the best

[@amanmotghare7196]

excellent explanation

[@rohandsouza9147]

Cant be thankful enough man !!

[@shivam9048]

Very well understood

[@devanshmesson2777]

Thank you so much striver!

[@sauravkumargupta2594]

Woohoo most awaited ques 🔥

[@loveleshsharma5663]

Good Explanation!

[@howsusisthis]

LURVEEE THIS!

[@vishnugandlur3875]

searching in an unordered map takes o(N) worst case time right? But requirement was to do it in o(1).

[@a_05_himanshu_akula31]

Access by key ..dont search

[@willturner3440]

Bhaiya Next problem LFU cache, please...

[@takeUforward]

Ye smjh aaya ?

[@willturner3440]

@@takeUforward mast samajh aagya...

[@takeUforward]

@@willturner3440 thik h lfu cache lekar aate h tab next 🥱