Min Stack Leetcode | Get Min at pop | solution stack Hindi Explained | Data structure & Algorithms
ฝัง
- เผยแพร่เมื่อ 12 ก.ย. 2024
- This is the video under the series of DATA STRUCTURE & ALGORITHM in a STACK Playlist. Now we are going to solve a stack problem Min Stack or Get min at pop from GeeksForGeeks.
Join My Telegram channel for more Updates: telegram.me/he...
complete DSA preparation: github.com/Pri...
----------------------------------------------------------------------------------------
► 155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
►Min Stack: leetcode.com/p...
►Get min at pop: practice.geeks...
► Code In this video: github.com/Pri...
----------------------------------------------------------------------------------------
*Follow me *
LinkedIn► / iamprince
Facebook► / helloworldofficials
Instagram► / helloworldbyprince
Twitter► / prince_king_
Telegram► telegram.me/he...
----------------------------------------------------------------------------------------
►Our Playlists on:-
► Tree: • Tree Data Structure & ...
► Stack: • Stack & Queue Data Str...
► Hashing: • Hashing Data Structure...
► Graph: • Graph Data Structure &...
► Matrix: • Matrix (Multidimension...
► STL: • Standard Template Libr...
► Leetcode: • LeetCode Solutions And...
►Competitive Programming: • Full course in Competi...
►C++ Full Course : • C++ full Course in HINDI
►Algorithms: • L-01 || Prefix Sum Arr...
►Data Structure: • Data Structures with C...
------------------------------------------------------------------------
🌟 Please leave a LIKE ❤️ and SUBSCRIBE for more AMAZING content! 🌟
✨ Tags ✨
leetcode problems
leetcode problems java
leetcode problems python
leetcode problems that got me tired
leetcode problems c++
leetcode problems and solutions python
leetcode problems playlist
leetcode problems and solutions java
leetcode problems in Hindi
leetcode problems javascript
leetcode problems and solutions
leetcode problems of the day
leetcode problems for beginners
leetcode problems easy
leetcode problems js
Introduction to the graph data structure
stack practice problems
stack practice problems gfg
leetcode stack questions
leetcode stack queue
stack hello world
MIn stack leetcode solution
Get Min at pop gfg
remove consecutive duplicates from a string
question asked in Google
off-campus placement
number of closed islands
Practice stack data structure
Stack in a data structure in Hindi
Stack Full playlist for Beginners
algorithms
graph
data structure
sorting algorithms
algorithm analysis
gate computer science preparation
programming languages
#stack #Leetcode #DSA
Bohht achhe se explain kiya aapne
Koi aise nhi krata
Jo Aise hme btaye ke abhi ruko socho...
And apki language 👏🏻 ittni beginner friendly 🙏🏻🙏🏻
Aapki speed, video quality, sound quality, apke explain krne ka way 🔥🔥just splendid👌🏻👌🏻
Thanks a ton Abhay, thanks for supporting me
Please, share this channel in your college, groups, or LinkedIn bcoz it's cost nothing to you 😀
do this without using extra space@@HelloWorldbyprince
Glad you share this point at 12:30 as while doing Valid Parentheses i did the same mistake by reversing the order in condition ,later i realised that this actually make difference lol
great buddy
You explained it amazingly brother, but now this question has become a medium level question in leetcode and many more testcases are added where they are also testing multiple occurrences of possible min element. So an upgraded solution with same logic with a added frequency hashmap will look like this
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
self.min_freq_map = {}
def push(self, val: int) -> None:
self.stack.append(val)
if self.min_stack:
if val None:
x = self.stack.pop()
if self.min_stack[-1] == x:
if self.min_freq_map[x] > 1:
self.min_freq_map[x] -= 1
else:
self.min_freq_map.pop(x)
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
leetcode.com/problems/min-stack/solutions/4137761/python-stack-hashmap-solution/
Oo Really nice yaar
Your explanation was excellent. I had been stuck on this code for the past two days and watched numerous videos, but you covered everything in detail, including small points like void and int.😊😊Thank you so much.
The way you tell these small important things is really helpful. Really nice explanation !!!!
Glad to hear that!
i got this in first attempt because you said to attempt , it really helped , i have completed this question without any help .
nice work brother
the way you explain the question as well as the solution is really amazing. love to see your videos.☺
hn adha tak soch liya tha maine mja aagya bhaiyaji
Wahh buddy
Keep learning
My Approach :
stack stack;
map mpp;
MinStack() {
int c=0;
}
void push(int val) {
stack.push(val);
mpp[val]++;
}
void pop() {
mpp[stack.top()]--;
if(mpp[stack.top()]==0)
mpp.erase(stack.top());
stack.pop();
}
int top() {
return stack.top();
}
int getMin() {
return mpp.begin()->first;
}
};
good work
bhaiyaaaaaaaa bhot ache se ye bata diya apne.... thank youuuuuuuuuuuuuuuuuuuuuuuuuuuu
Thanks shivani ❤️ please share and support my channel
TQ very much bhaiya ❤, before this video i have wasted my 2 hours , but after this video i cracked the answer.😊😊
Most welcome 😊
Really very good logic and explanation ❤❤
Thanks a lot 😊
Dil jeet liya bhaiya thank you from bottom of my heart.
bhaiya badi badhiya smjhaye ek baar m dimag m dhuk gya.Thank you bhaiya
😂😂😂 thanks yaar
Please, if possible then share this channel in your college, groups, or LinkedIn bcoz it's cost nothing to you 😀
@@HelloWorldbyprince theek h bhaiya 😊 bs aap issi trh se amazing content bnayee .
Can someone explain🚩🚩📗 When I'm writing the same code in JAVA, it's not working. But When I'm changing the pop() method to:
public void pop() {
if(st.peek() == getMin()) min_st.pop(); // *Using getMin() instead of min_st.peek() works* ???
st.pop();
}
//Please explain why writing min_st.peek() doesn't work?
same problem bhai.Agar aapko solution smjh aaya iska to btana meko..
the explainations of the problem was very good bring more of these explanation on DSA related topics series.
Legendary explanation. Thank u bhaiya.
Thanks
Next level ❤
i have maintain double ended queue and time complexity of getting min element is O(1)
Nice way to solve this question
Please, share this channel in your college, groups, or LinkedIn bcoz it's cost nothing to you 😀
8:22 what if we popped 18 then 18 will pop out of stack but will remain in min_stack and then after that we pop 15 then that 15 will get removed from both stack and min_stack and now if we ask for min_element then now in min_stack there is 18 reamining but it was already popped out of main stack so how does this work?
or what if we pop 15 then pop 18 then ask for get_Minvalue then what min value will be retuerend?? since min_Stack is empty?
Am i being dumb or what i wrote do makes sense?
how to fix this?? i think to fix this the min_stack should be as same size as the main_stack so that min_stack(as in use sorted version of stack in descending order) is empty case won't occur and when you pop from main_stack it should be popped from min_stack as well i guess. but this can never be O(1)
Great explanation👍👌
you are the best.......masum.
Hahah Thanks
Really appreciated your effort bhaiya ❤ even a noob can understand very well from your video bhaiya 😊
samaj aa gyapura thank sir ji
Top notch explanation bhaiya !!! Thank you
maine doubly LL banayi thi minimum elements ki and jab pop krha tha tab agar top element mid node ke barabar tha to min pointer ko shift krdiya
Great explanation sir
Keep watching
great video bhiaya
Bhaiya aap pehle jo map pe implement kiye uspe to multiple same values mein dikkat nahi hoga? like 1 3 3 2 1 aise mei?
okayyyyy
let's do one thing
just take an dummy example which was on your mind
and see that your exmplae is valid according to the question then
follow my solutions
@@HelloWorldbyprince Samajh gaya bhaiya 😎
we have to make second another stack upto this I realised but how to maintain that to get a minimum element that I did not get from my thought side so upto half solution I reached
superb bro, thank you.
Thank u sir 🙌🏻
Welcome 👍
Great explanation. May Thnaks
Thanks a ton
I think Map approach won't work when we have duplicate elements pushed
Best and easy explanation...
Thank you so much 🙂
well explained !!
Thanks a lot
Thanks a lot bhaiya! Very helpful
Always welcome
Great Video
Thanks!
Nice Explaination Bhai
Thank u
i maintained a minHeap instead of minStack but that was (ologn) for pop :(
What abt O(1) space approach?
not possible sir!
@@supriyamanna715 it is possible to have o(1) if instead of pushing the value use push 2*val - minval
ye o(1) space complexity ka nhi hai solution, jisko O(1) space complexity and O(1) time complexity ka chaiye ye rha
class MinStack {
private:
std::stack stack;
int min_value;
public:
MinStack() : min_value(INT_MAX) {}
void push(int val) {
if (stack.empty()) {
stack.push(val);
min_value = val;
} else {
if (val < min_value) {
stack.push(2 * val - min_value);
min_value = val;
} else {
stack.push(val);
}
}
}
void pop() {
if (stack.empty()) {
return;
}
int val = stack.top();
stack.pop();
if (val < min_value) {
min_value = 2 * min_value - val;
}
}
int top() {
if (stack.empty()) {
return INT_MAX;
}
int val = stack.top();
if (val < min_value) {
return min_value;
} else {
return val;
}
}
int getMin() {
return min_value;
}
};
@@psinity 2 * val - min_value isse stack ki original value change jorahi pr push krte vkt. i do not know why we using this regardless of this???
very good explanation
But what about duplicate elements bhaiyaa
usse kya hi farak padd jayega bro, aap ek baar khud se dry run kariye pen and paper pe aako clear ho jayega
Nice explaination
Thanks for liking
🔥🔥🔥 please cover aditya verma remaining questions also
🤩🤩 sur e
but ye bhi O(N) ni hogya space mei as hum ek aur stack banare
Amazing content
Bass consistent hokar mehnat karte hai
👍
bad approach
// class MinStack {
// public:
// vectorv;
// MinStack() { // constructor
// }
// void push(int val) {
// v.push_back(val);
// }
// void pop() {
// v.pop_back();
// }
// int top() {
// return v[v.size()-1];
// }
// int getMin() {
// int mn = v[0];
// for(int i = 1;i
Thanks
ye o(1) space complexity ka nhi hai solution, jisko O(1) space complexity and O(1) time complexity ka chaiye ye rha
class MinStack {
private:
std::stack stack;
int min_value;
public:
MinStack() : min_value(INT_MAX) {}
void push(int val) {
if (stack.empty()) {
stack.push(val);
min_value = val;
} else {
if (val < min_value) {
stack.push(2 * val - min_value);
min_value = val;
} else {
stack.push(val);
}
}
}
void pop() {
if (stack.empty()) {
return;
}
int val = stack.top();
stack.pop();
if (val < min_value) {
min_value = 2 * min_value - val;
}
}
int top() {
if (stack.empty()) {
return INT_MAX;
}
int val = stack.top();
if (val < min_value) {
return min_value;
} else {
return val;
}
}
int getMin() {
return min_value;
}
};
Awesome explanation
Thanks a lot please share my channel with your friends
Well explained!
Thanks a lot buddy please share this video so that others can also get benefits from this
बकायदा चेक नहीं कर सकते। बकाएगा किया होता हैं, हा?
Bhaiya aapne video bnana bnd krdi hai kya?
simple and clean
Thanks a lot
great vid sir
Glad you liked it
@@HelloWorldbyprince always
really very helpful video for me
It's my pleasure
gfg pr test case pass he nhi hue same code dala tha
Best
Thanks anurag
@@HelloWorldbyprince thanks sir for fast and Simple Codes🙏🙏🙏
Pop krne m agr minSt empty hua to
amazing thanks
I think about priority_queue
Hmm
bhai yr frk itna hai mena min variable return kr diya but pne pure corner case check kiya
koy nehi its my bad baki question mast hai
this solution uis showing emty stack expection in the getMin method
yaar pls check my code once, if u still face this issue, then let me know
hashmap socha tha counter maintain karke par fir min find karne k liye loop chalana pada
bhai dsa complete krne me avg ketna time lgta he
1-2 month
i tried same approach but it does not work in java
Just cast peek element to int, it works
Bhaiya user se input kaise lenge
Yaar wo leetcode ka platform khud kar raha hai ...
I think bro u should watch me leetcode playlist ...first ...uske 3-4 questions starting ke dekh jao ..sab samjh me aa jayega
I made a pair {val,min} and updated min
Nice 👍
I though using a binary try and always storing the root node as the minimum element , its a bit over engineered i think ; p
u can check ur solution by applying it
Helpful
Glad it helped
I have used a very brute force solution .Like O(N) and why did'nt I was not able to think about it.FF to me
background black kaise kiya?
Green screen effect
class MinStack {
Stackst, s2; //here s2 is the minStack
public MinStack() {
}
public void push(int val) {
if( s2.isEmpty() || val
yesss
It maybe because you havent allocated memory to the stack i.e.
Stack st=new Stack():
'new' is the keyword which does memmory allocation in java...
Did you solve it ? If you have solved it pls can you share the code?
nice
Thanks
@@HelloWorldbyprince bhaiya ur awesome 🤞❣️
Bhahiya thode aur question karo stack pr 😁😁
Haan jivan sure
Bass ab videos aayega ....
genuine feedback: please focus more on question rather than other commentary
👌❤️
🔥🤩
kisi ne try kiya kya gfg pr nhi chl rha
pair se socha tha
Good
main araay bna k kar rha tha
ye to sc me 0(2n) ho gaya
op
Keep sharing with your friends
I also took 2 stacks but got stuck
Oo, i hope now its cleared
medium level ka hogaya yeh sawal
Are wahh party
This approach won't work for test case
["MinStack","push","push","push","push","pop","getMin","pop","getMin","pop","getMin"]
[[],[512],[-1024],[-1024],[512],[],[],[],[],[],[]]
nice explaination
great vid 👍
thanks suraj
Please, share this channel in your college, groups, or LinkedIn bcoz it's cost nothing to you 😀