Min Stack Leetcode | Get Min at pop | solution stack Hindi Explained | Data structure & Algorithms
Vložit
- čas přidán 27. 02. 2022
- 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/helloworldbyprince
complete DSA preparation: github.com/Prince-1501/Comple...
----------------------------------------------------------------------------------------
► 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/problems/min-stack/
►Get min at pop: practice.geeksforgeeks.org/pr...
► Code In this video: github.com/Prince-1501/Hello_...
----------------------------------------------------------------------------------------
*Follow me *
LinkedIn► / iamprince
Facebook► / helloworldofficials
Instagram► / helloworldbyprince
Twitter► / prince_king_
Telegram► telegram.me/helloworldbyprince
----------------------------------------------------------------------------------------
►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
the way you explain the question as well as the solution is really amazing. love to see your videos.☺
Dil jeet liya bhaiya thank you from bottom of my heart.
Top notch explanation bhaiya !!! Thank you
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 explainations of the problem was very good bring more of these explanation on DSA related topics series.
samaj aa gyapura thank sir ji
superb bro, thank you.
Really appreciated your effort bhaiya ❤ even a noob can understand very well from your video bhaiya 😊
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
Legendary explanation. Thank u bhaiya.
Thanks
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
great video bhiaya
The way you tell these small important things is really helpful. Really nice explanation !!!!
Glad to hear that!
Great explanation👍👌
very good explanation
Thanks a lot bhaiya! Very helpful
Always welcome
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
hn adha tak soch liya tha maine mja aagya bhaiyaji
Wahh buddy
Keep learning
Great explanation. May Thnaks
Thanks a ton
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
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..
Well explained!
Thanks a lot buddy please share this video so that others can also get benefits from this
Best and easy explanation...
Thank you so much 🙂
Great explanation sir
Keep watching
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
nice explaination
bhaiyaaaaaaaa bhot ache se ye bata diya apne.... thank youuuuuuuuuuuuuuuuuuuuuuuuuuuu
Thanks shivani ❤️ please share and support my channel
Thank u sir 🙌🏻
Welcome 👍
simple and clean
Thanks a lot
well explained !!
Thanks a lot
Amazing content
Bass consistent hokar mehnat karte hai
you are the best.......masum.
Hahah Thanks
Really very good logic and explanation ❤❤
Thanks a lot 😊
Awesome explanation
Thanks a lot please share my channel with your friends
Great Video
Thanks!
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)
really very helpful video for me
It's my pleasure
TQ very much bhaiya ❤, before this video i have wasted my 2 hours , but after this video i cracked the answer.😊😊
Most welcome 😊
great vid 👍
thanks suraj
Please, share this channel in your college, groups, or LinkedIn bcoz it's cost nothing to you 😀
Nice Explaination Bhai
Thank u
👍
I think Map approach won't work when we have duplicate elements pushed
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 .
Nice explaination
Thanks for liking
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 😀
Helpful
Glad it helped
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
but ye bhi O(N) ni hogya space mei as hum ek aur stack banare
great vid sir
Glad you liked it
@@HelloWorldbyprince always
🔥🔥🔥 please cover aditya verma remaining questions also
🤩🤩 sur e
gfg pr test case pass he nhi hue same code dala tha
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 😎
great
Thanks
👌❤️
🔥🤩
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???
Pop krne m agr minSt empty hua to
hashmap socha tha counter maintain karke par fir min find karne k liye loop chalana pada
Bhaiya aapne video bnana bnd krdi hai kya?
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
I made a pair {val,min} and updated min
Nice 👍
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
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
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
nice
Thanks
@@HelloWorldbyprince bhaiya ur awesome 🤞❣️
Best
Thanks anurag
@@HelloWorldbyprince thanks sir for fast and Simple Codes🙏🙏🙏
I think about priority_queue
Hmm
बकायदा चेक नहीं कर सकते। बकाएगा किया होता हैं, हा?
bhai dsa complete krne me avg ketna time lgta he
1-2 month
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
kisi ne try kiya kya gfg pr nhi chl rha
op
Keep sharing with your friends
background black kaise kiya?
Green screen effect
Bhahiya thode aur question karo stack pr 😁😁
Haan jivan sure
Bass ab videos aayega ....
main araay bna k kar rha tha
pair se socha tha
Good
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
I also took 2 stacks but got stuck
Oo, i hope now its cleared
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;
}
};
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
medium level ka hogaya yeh sawal
Are wahh party
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?
genuine feedback: please focus more on question rather than other commentary
This approach won't work for test case
["MinStack","push","push","push","push","pop","getMin","pop","getMin","pop","getMin"]
[[],[512],[-1024],[-1024],[512],[],[],[],[],[],[]]