LRU cache | EP 22

[@facttecher3039]

Finally i understand the logic behind this problem. I really like your way of explaination . This type of explaination I don't get anywhere. Keep it up sir ji.

[@desihiphop4998]

Bhiaya poori playlist ka sabse accha question laga pehle bhe kr rakha tha but ni kr paaya is baar but ab acche se smjh gya !!!!! Hero ho bhaiya aap !!!🖤🖤

[@dp-ev5me]

done for this weekend, looking forward to next. Thank you sir.

[@mohammadfraz]

Good job 🔥

[@ece116pranaykumar4]

getting TLE now

[@Wanna_be_01]

1. BRUTE FORCE APPROACH(Using Queue + HashMap):- ------------------------------------------------------------------------------------------ class LRUCache { public: unordered_map m, cnt; queue q; int n; LRUCache(int capacity){ n = capacity; } int get(int key) { if (cnt.find(key) == cnt.end()) return -1; q.push(key); cnt[key]++; return m[key]; } void put(int key, int value) { q.push(key); cnt[key]++; m[key] = value; while (cnt.size() > n) { int cur = q.front(); q.pop(); if (cnt[cur]-- == 1) cnt.erase(cur); } } }; // Time Complexity = O(n+m) // Space Complexity = O(n+m) 2. OPTIMIZED APPROACH(Using DLL + HashMap) - By Fraz Bhaiya (from this lecture):- ---------------------------------------------------------------------------------------------------------- class LRUCache { public: unordered_map m; unordered_map address; list l; int cap; int siz; LRUCache(int capacity) { cap = capacity; siz = 0; } int get(int key) { if(m.find(key) == m.end()) return -1; auto it = address[key]; l.erase(it); address.erase(key); l.push_front(key); address[key] = l.begin(); return m[key]; } void put(int key, int value) { if(m.find(key) != m.end()){ auto it = address[key]; l.erase(it); address.erase(key); m.erase(key); siz--; } if(siz == cap){ int del = l.back(); l.pop_back(); address.erase(del); m.erase(del); siz--; } siz++; l.push_front(key); address[key] = l.begin(); m[key] = value; } }; // Time Complexity = O(1) // Space Complexity = O(Capacity) ----------------------------------------------------------------------------------------------------------------- Enjoy Guys !!! ❤😉 I wrote here for revision purpose in future but you can use too for revision :) And Thank to Fraz Bhaiya 🙏🥰❣🔥for whole content :)

[@ayushbhagwat3440]

It's giving TLE 21/22 Test cases passed. I even tried using unordered_map but still no effect. Last executed input: ["LRUCache","get","get","put","get","put","put","put","put","get","put"] [[1],[6],[8],[12,1],[2],[15,11],[5,2],[1,15],[4,2],[5],[15,15]]

[@balakrishnanr648]

so what u did?

[@gantayat]

Keep submitting, it will pass randomly xD (shorturl.at/AU157 )

[@mgdesire9255]

finally S2 done...looking forward Bhaiya can't wait for upcoming season.

[@mohammadfraz]

aaega aaega

[@mohdsaadalikhan7209]

time: o(1) average case , o(n) worst case (as in unordered map , collisions may increase the time for search or insert to o(n) ) space: o(n) correct me if i am wrong?

[@abhayrai1724]

Bhaiya aab aap ese ese educational videos kyu nhi dal rhe missing those days jb ache ache ques solve krwate the aap kafi easily .... Plz laut aao purane wale bhaiya 😍🤗

[@_inspireverse___]

Well explained. Thank you so much 👍

[@baap6382]

Sir your videos are absolute gold. Keep posting. I am in final year. Wished I was born 2-3 years later

[@mohammadfraz]

Thanks a lot for watching

[@vikassinghbisht7305]

u r best fraz bhaiya

[@ritulraj6119]

Great Explanation 👌

[@shashankpandey4387]

Both get() and put() will have time complexity of O(n) , because you are using erase() which take O(n) time Random Access is not allowed in list try to implement in O(1) as asked in question @frazmohammad Thanks

[@mdnadeem6343]

TC: O(log n) for both get and put function SC: O(n)

[@sudhanshuranjan4392]

Can you please explain how? I guess TC will be O(n logn).

[@balakrishnanr648]

@@sudhanshuranjan4392 he has given amortized TC i mean avg one for all n ops.

[@louistomlinson3367]

if anybody is wondering how will be the java code, here it is class LRUCache { HashMap map; Node head; Node tail; int capacity; public LRUCache(int capacity) { head = new Node(0, 0); tail = new Node(0, 0); this.capacity = capacity; map = new HashMap(); head.next = tail; tail.prev = head; } public int get(int key) { if (map.containsKey(key)) { Node node = map.get(key); delete(node); insert(node); return node.value; } else { return -1; } } public void put(int key, int value) { if (map.containsKey(key)) { Node node = map.get(key); node.value = value; map.put(key, node); delete(node); insert(node); } else if (map.size() < capacity) { Node newNode = new Node(key, value); map.put(key, newNode); insert(newNode); } else { Node newNode = new Node(key, value); Node toDelete = tail.prev; map.remove(toDelete.key); delete(toDelete); insert(newNode); map.put(key, newNode); } } private void delete(Node node) { Node prev = node.prev; Node next = node.next; prev.next = next; next.prev = prev; } private void insert(Node node) { Node headNext = head.next; head.next = node; node.prev = head; node.next = headNext; headNext.prev = node; } } class Node { int key; int value; Node next; Node prev; public Node(int key, int value) { this.key = key; this.value = value; next = prev = null; } }

[@devendrabhuarya4917]

class LRUCache { public: unordered_map values; unordered_mapm; list l; int capacity,size; LRUCache(int capacity) { this->capacity=capacity; size=0; } int get(int key) { if(m.find(key)==m.end()) return -1; auto it=m[key]; l.erase(it); l.push_front(key); m[key]=l.begin(); return values[key]; } void put(int key, int value) { if(m.find(key)!=m.end()) { auto it=m[key]; l.erase(it); l.push_front(key); m[key]=l.begin(); values[key]=value; return; } if(size

[@HarshRaj-kp7gk]

sir, please make a video on (computer network) preparation in 3 days for placement sir , "you forgot it this subject to make a video " its humble request sir please make a video as soon as possible

[@RitikGupta-uo2te]

Gate Smashers se jaake pdle bhai aur saath ke saath notes likhlio

[@lalit-singh-bisht]

i was not expecting a stl solution

[@manishvijay6794]

Awesome content 🔥🔥

[@anupambiswas6148]

Thank you sir

[@krishnaradhey2814]

fraz bhaiya if i am implementing this question in the opposite of this approach means that for least recently used i am putting nodes on right side end and for most recently used (to be pop) on the left side end IT IS GIVING TLE BY THIS REVERSE APPROACH ???CAN ANYONE EXPLAIN WHY

[@mdnadeem6343]

zbrdst bhaiya

[@mohammadfraz]

Thanks Nadeem

[@utkarshsingh5390]

Season 2 done bhaiya

[@guptashashwat]

G phat gyi karte karte but excellent explanation!

[@Sai-fp3tu]

Overall linked list ka kitne videos ayenge bhaiya? Btw Awesome teaching 🔥🔥

[@mohammadfraz]

About 30

[@SunnyGupta00]

Reach++ 🔥

[@vivekmahindrakar2996]

Can we use Stacks where the most recently used is the top and lru is at the bottom???

[@editorera239]

Thnx bhaiya In series m linked list complete ho jaega na overall I mean

[@mohammadfraz]

A-Z khatam ho jaega

[@editorera239]

@@mohammadfraz yee thnx bhaiya

[@souravkumar5120]

I dont know why but I am getting tle.

[@bitrish34]

use ordered_map instead of map it will pass all test case

[@shivanshgupta4342]

@@bitrish34 i am using unordered map and it is still giving me tle

[@vasuoberoi1810]

which whiteboard u are using?

[@rishupatel7285]

Is anyone getting TLE For this solution

[@deepakprajapat3897]

Sir STL full concept ka uper aap video kab upload karoge Plzzzz

[@mohammadfraz]

Bana denge

[@amit0sunny]

if u talk about thinking from scratch then start with a basic solution, its easy to remember a solution and then explain it in here. I don't see how u started with a basic concept, in fact the first thing u said was LinkedList and hashmap , do u think we all should gobble up the solution to each problem?

[@tech_wizard9315]

By when you will upload entire playlist

[@mohammadfraz]

Jaldi hi

[@madhabkafle8072]

🔥🔥🔥

[@mohammadfraz]

❤️❤️

[@TekaneChaitanya]

Please make videos using JAVA

[@SunnyGupta00]

It is very similar to c++ (.) Ki jaga (->) ko replace kar do

[@MdFaisal-kj1ck]

Bhai linked list k baad STL please ASAP.🙏🙏

[@mohammadfraz]

yes

[@code7434]

Faraz please share your submission or please do resubmit your code as it is giving TLE

[@bitrish34]

use ordered_map instead of map it will pass all test case

[@yajatdhawan1865]

bro its giving TLE

[@bitrish34]

use ordered_map instead of map it will pass all test case

[@shubhangverma4478]

@@bitrish34 not working

[@rishabhbatra3022]

bhaiya ye jo declarations globally kri h apne interviwer m aese krna thik rehta h ya as a paramter pass krein

[@nitunsingh6986]

U can also make them private within the class

[@nitunsingh6986]

Btw default in C++ they are Private

[@harendrameghwal1120]

ye code abhi runtime error de rha h leetcode pe 20/22 test cases.

[@bitrish34]

use ordered_map instead of map it will pass all test case

[@sarimkhan9897]

@@bitrish34 not working

[@helloUser12373]

your solution is not accepted on gfg. Test cases are failing.

[@Sonu-tg6tg]

Please make videos using JAVA