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.
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 !!!🖤🖤
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]]
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 :)
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?
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
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
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 😍🤗
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
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?
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.
done for this weekend, looking forward to next. Thank you sir.
Good job 🔥
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 !!!🖤🖤
getting TLE now
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]]
so what u did?
Keep submitting, it will pass randomly xD (shorturl.at/AU157 )
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 :)
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?
finally S2 done...looking forward Bhaiya can't wait for upcoming season.
aaega aaega
Sir your videos are absolute gold.
Keep posting.
I am in final year.
Wished I was born 2-3 years later
Thanks a lot for watching
Well explained. Thank you so much 👍
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
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
Great Explanation 👌
u r best fraz bhaiya
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 😍🤗
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
Gate Smashers se jaake pdle bhai aur saath ke saath notes likhlio
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;
}
}
Can we use Stacks where the most recently used is the top and lru is at the bottom???
i was not expecting a stl solution
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
TC: O(log n) for both get and put function
SC: O(n)
Can you please explain how?
I guess TC will be O(n logn).
@@sudhanshuranjan4392 he has given amortized TC i mean avg one for all n ops.
Awesome content 🔥🔥
Is anyone getting TLE For this solution
Thnx bhaiya
In series m linked list complete ho jaega na overall I mean
A-Z khatam ho jaega
@@mohammadfraz yee thnx bhaiya
Faraz please share your submission or please do resubmit your code as it is giving TLE
use ordered_map instead of map it will pass all test case
ye code abhi runtime error de rha h leetcode pe 20/22 test cases.
use ordered_map instead of map it will pass all test case
@@bitrish34 not working
Please make videos using JAVA
It is very similar to c++ (.) Ki jaga (->) ko replace kar do
which whiteboard u are using?
Overall linked list ka kitne videos ayenge bhaiya?
Btw Awesome teaching 🔥🔥
About 30
I dont know why but I am getting tle.
use ordered_map instead of map it will pass all test case
@@bitrish34 i am using unordered map and it is still giving me tle
By when you will upload entire playlist
Jaldi hi
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?
bhaiya ye jo declarations globally kri h apne interviwer m aese krna thik rehta h ya as a paramter pass krein
U can also make them private within the class
Btw default in C++ they are Private
Sir STL full concept ka uper aap video kab upload karoge
Plzzzz
Bana denge
G phat gyi karte karte but excellent explanation!
zbrdst bhaiya
Thanks Nadeem
Bhai linked list k baad STL please ASAP.🙏🙏
yes
Thank you sir
Season 2 done bhaiya
Reach++ 🔥
bro its giving TLE
use ordered_map instead of map it will pass all test case
@@bitrish34 not working
🔥🔥🔥
❤️❤️
your solution is not accepted on gfg. Test cases are failing.
Please make videos using JAVA