Design special stack with getmin in O(1) time time and O(1) space
Vložit
- čas přidán 18. 03. 2020
- This video explains a very frequently asked important programming interview question from stack and queue topic which is to design a special stack which supports getmin operation in just O(1) time and O(1) space. This video explains the most optimized approach to find minimum from a stack. The previous video explained it in O(1) time but took O(N) space. The previous approach was much more simple as compared to the current approach but this one is more efficient. LINK to the previous video and CODE LINK for current video is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
PREVIOUS VIDEO: • Design special stack w...
If suppose this was a company listed in IPO i would have invested everything cause this channel is going to be soo much bigger.There is no match. This is absolute brilliance.
Thank you TECH DOSE :3
Thanks for your motivation :3
Agreed!!
I accidentally came across your channel, great content. Keep posting such problems...
Thanks :)
Same with me:)..
@@meenabisht6640 good for you
hye bro don't think about views, after point of time u will get more views..
keep Post such type problem...
thanks
Thanks for your motivation :)
Hey thanks for the explanation! Just 2 changes I think is necessary :
In getMin() fn : if empty stack return -1;
In pop() fn when curr
The *very* best explanation of this approach. Thanks!
Welcome :)
BEST VIDEO ON O(1), never understood why we do 2*curr - min but your diagram made is crystal cear 😮
Nice :)
Great technique, but I don't understand why interviewer would ask these kind of 'tricky' questions where you can only solve it if you know the solution! :/ Then it's just testing your knowledge, not your ability to solve
Chances are low but you may think it as a puzzle rather than proper DSA question. A DSA puzzle
Seriously buddy, totally agree with you here. Some (in fact majority of them) problems are more on knowing the specific trick in each of those problems, so until and unless someone hasn't solved it before, it's literally impossible to do that within a given time constraint. That's the sad thing I don't like about this.
haha this question just came in my interview of DP world, the interviewer asked me for this and I didnt know so didnt clear the round
I was asked about this in my Leminsk interview. I gave him another stack approach. and then when he wanted to further optimise I said I can do some mathematical operations which let me keep two values at the same place.
I was trying multiplication modulo and division and try to come up with something. didn't know I had to use multiplication and subtraction.
i am beinge watching your all tutorials
Great stuff bro
Thanks :)
if we want to push INT_MIN or INT_MAX then ??? int data type won't allow 2 * INT_MIN. this will be out of range and cause int overflow ?? so anything abt this ??
This is gem of a channel
if we are maintaining the min value then whats the point of doing complex push pop things can be sorted very easily
What if the first value you want to pop is equal to the minimum value?
but we aren't storing the values we want to store in the stack right?
that means this stack in which we are applying the formula isn't much of our use except finding min value so for other operations we will have to create another stack, which makes our space complexity O(1) again, please enlighten me if im wrong.
What if we do not add elements which bigger than s.top() because I think that they're doing nothing
Very very informative sir this is just a trciky if we have to do it with O(1) great explanation I have waste a lot of time in figuring it out thanks for you explanation sir ☺
Welcome
This will cause integer overflow for large number example : 2*LARGENUM - min.
Simpler solution is to save the minimum element at each push along with the element like an Object or c++ pair.
It takes more memory than your solution but solves the overflow issue.
But that will be taking extra space 😅 Better to know the constraints first before solving and take decision accordingly.
how to get the actual top element from the stack?
very well explained the formula part, keep growing
Thanks :)
Congrats Surya on 100k Subscribers!!!
Thanks to our community 🙏🏼
Which software you used for making these videos??
Bro in this explation when u popped 2 element then 0 will be popped but actually u have inserted 3 then why u r popping out 0 why 3 is popping out?
This is really great approach👏
Thanks :)
Good explanation :)
Great content bro♥️.Thank you
Welcome :)
There is chance that (2*curr_min -min )will go so minimum that it go out of range that int data type support.
If you want to get the actual value back when you call the pop() function, then if the top element is less than or equal to the min element then the return value will be the min element. Also, this approach only works within the range of Integer which is -2,147,483,648 to 2,147,483,647
thank you senpai
-CS undergrad from India
not working for me,
suppose min is 3, new item comes 1, so (2*1-3) = -1 is pushed, and 1 becomes the min.
now while popping, (2*1-(-1))= 3 is popped.
@@amitavamozumder73 your last line is wrong , 3 is not popped, 3 is the new min after popping...
you are at min = 1 and element in stack top is -1 . Now , for top(), check if min is >= stack top , if yes , then answer is min (1) , which is the correct answer for the top of element of stack as stack contains (3,1)
@@KaranKumar-hw2bq ooh, so the popped items are changed just to maintain the min item? i thought we're managing both.
Some more explanation:
when x>=min: push x directly and no updation of min(Pushed element >= min)
when x
Thanks bro!!
Can we do it in this way !
Insert the element and the min at that point into the same stack. And once pop() is to be done, do it twice.
Push () {
Min = +inf
For i in arr
Stack.push(I)
min= Math.min(min,I)
Stack.push(min)
}
And while popping elements we do the pop twice. This approach is also O(1) in TC. And (2n) ~O(n) in SC !!
a much simpler formula can be (new min - old min) and check if the value is negative while poping
Sir why we using 2x-y = c, x-y = c relation
nice explained ...need more such content
Thanks. Sure 🙂
Bro please make another video of why this trick works
super explanation thank you bro
Welcome :)
wow, awesome explanation!
Thanks
Very good videos sir... Keep it up , never stop... you are doing a noble job !!
Thanks bro :)
while poping we should pop 3 instead of zero same for the 6, ie when we find the min value we should replace it and pop it
Yes, I was thinking the same.
Thanks for the great contents.
Can we also push the values as (current_value - min) and pop (min - current)?
I think something like this would fail for negative integers.
How you come to think of this formula (2x-min).. if anyone not seen the problem earlier .. how they can think of such formula
you cant think this formulla without brainstorming atleast 100s ways to solve this question and devoting sweet time of your life. it requires so many hit and trials tht if interwier asked such question, only person who knows the formulae can do it.
And commenting this to increase your engagement
Thanks
perfect explanation
Thanks
How is this O(1) space? Since we are using an array to store elements, it should be O(n).
simply liked it
👍
If you want to retrieve data as you call pop(). How would you do that?
jst return stack.pop(); compiler will handle it automaticalyy.
or you can store stack.top() in another variable.
You deserve more view!!
Thanks
In push function
May I can use following arithmetic operations
if(curr
Awesome content
Thanks
working for negative numbers also?
I did not try. Try it once and let me know.
But if we use this there is no way we get the actual popped elements it will just get popped and size decrease but the element we can not get.
Excuse the late reply. We can get the actual popped elements. The elements are either stored in the min variable (which we update using 2*min-curr to get overwritten ones) or on the stack as original element (which we can just pop).
Will it work for duplicate elements?
Don't remeber 😅
it should
Great
Thanks :)
I dont understand this why are we taking 2*(element) why only 2, we can also atke 3 or 4 or 5 if we just have to get the difference.
like even if we replace 2 with any other number(it can be 1 as well) we will get the previous element applying the algorithm....
why 2? can some give me a proof why not 1 or any other number..
it cant be 1 coz it will not work if stack had negative elements
I think any number more than 1 will work
@@Draxper thanks got it.... There is a great explanation why 2 is optimum, search for Aditya Verma getmin stack and the 1st comment is the explanation.
a better explanation of arithmetic for maintianing stack and min variable:
suppose -
stack s->... (maintain stack of elements)
and min -> ... (maintain a min variable)
lets, suppose
s -> ...(elements)...
min = m1
if new element, x < m1 , then
stack element, y = 2*x - m1 ...... eq(1)
so,
s -> ...(elements)...y (y = 2*x - m1)
min = m2 (here m2 = x, just another name for new min)
now when, popping, if y < m2 ( or if y < x, since m2 = x), then
from eq (1),
since, y = 2*x - m1,
so, prev min, m1 = 2*x - y , whic is therefore the eq for prev min.
Sir mehnat krni chalu krdi h poori 100 sawaal lg chuke h leetcode pe aur Aage bhi phle khud se baaki aap to hohi.... Please comment ka reply dedejiye ki Agar main sirf leetcode kru aur competetive na kru... to koi dikkat to nhi hogi sir?
Koi dikkat nhi
Nicu :)
this does not work for negative number
I think x-y will also work
first like the video then watch the video............
😁
Alternate solution using a list of hash maps
class MinStack {
public:
private:
vector minMaxStack;
vector Stack;
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
unordered_map newMinMax;
newMinMax["min"] = x;
newMinMax["max"] = x;
if(minMaxStack.size()){
unordered_map lastMinMax;
lastMinMax["min"] = minMaxStack[minMaxStack.size()-1]["min"];
lastMinMax["max"] = minMaxStack[minMaxStack.size()-1]["max"];
newMinMax["min"] = min(lastMinMax["min"],x);
newMinMax["max"] = max(lastMinMax["max"],x);
}
minMaxStack.push_back(newMinMax);
Stack.push_back(x);
}
void pop() {
minMaxStack.pop_back();
Stack.pop_back();
}
int top() {
return Stack[Stack.size()-1];
}
int getMin() {
return minMaxStack[minMaxStack.size()-1]["min"];
}
int getMax(){
return minMaxStack[minMaxStack.size()-1]["max"];
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
👍
very simple approach is to make stackst for val and min
How is this O(1) space ? You are actually using the stack for every push.
Excuse the late reply, but it is O(1) auxiliary space. Because from beginning to end we're only using the one stack that we designed to get the minimum. It may seem like we're pushing numbers from one stack to the modified stack in the video, but they're just a list of numbers that we are pushing onto the modified stack, they're not in a stack originally.
why 2*cur -min , cur -min could also work.
Try your idea. Submit and see if it gets accepted.
@@techdose4u ok
Would fail for negative integers, I guess. Please check once though
I don't know why you are making this complex. A much simpler solution is- get the top of the element and compare it with input. If input is smaller than top element then push the input, else push stack.peek or top element again. In pop operation just pop no logic required.
Meh, this explanation is too complicated. When you have the first 2*curr - min explanation, you should have used the values in the stack and not a standalone example.
what in the sorcery is this 🥸