Thank you striver for the intuition. I tried to implement the min stack using DLL where node represents (val,min,next,prev) all in O(1) optn push and pop represents addFirst remove first, and top will always hold min
class Data{ int val; int min; Data next; Data prev; Data(int val, int min){ this.val=val; this.min = min; this.prev=null; this.next=null; } } class MinStack { int min; Data head; Data tail; public MinStack() { this.min= Integer.MAX_VALUE; this.head = new Data(-1, min); this.tail = new Data(-1,min); this.head.next = this.tail; this.tail.prev = this.head; } public void push(int val) { // Data node = new Data(val, this.min); if(this.head.next == this.tail){ min = val; Data node = new Data(val,min); add(node); return; } min = Math.min(val, this.head.next.min);//-2, -3 Data node = new Data(val, min); add(node); } //(-3,-3),(0,-2),(-2,-2); //min = -3 public void pop() { remove(this.head.next); //min = this.head.next.min; } public int top() { return this.head.next.val; } public int getMin() { return this.head.next.min; } public void add(Data node){ Data next = this.head.next;// -1 ->20->-1 node.next= next; next.prev=node; node.prev=this.head; this.head.next=node; } public void remove(Data node){ //-1->10->20->-1 Data next= node.next; //20 this.head.next= next; next.prev = this.head; node.next=null; node.prev=null; } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
00:04 Design a minimum stack that includes get min operation 02:41 Implementing Min Stack by tracking current minimum value while pushing elements. 05:00 Implementing a min stack with push, pop, and getMin operations 07:30 Implementing Min Stack using a simple stack and integer max as placeholder. 09:57 Implementing Min Stack involves inserting modified values and updating the minimum. 12:26 Modify minimum value in Min Stack implementation 15:14 Designing a minimum stack by implementing push and pop operations 17:44 Implementing Min Stack in a Stack structure 19:58 Implementing Min Stack with optimized approach
we can just use a variable which stores minimum element ,before every push , we can compare and update accordingly and while popping if we are popping min element , then we can traverse to find the min element...
Thank you so much for this explaination. I am following your A-Z sheet . Can you please upload videos of left Question in A-Z sheet and Article as well .
at 4:35 if a interviewer ask us to design a stack we can design it using linked but after designing how we can use in this solution like out of class..
For the Second method consider this code as the TUF website's code is generating wrong output for A edge test case class MinStack { Stack st = new Stack(); Long min; public MinStack(){ min = Long.MAX_VALUE; }
public void push(int val) { Long value = Long.valueOf(val); if(st.isEmpty()){ min = value; st.push(value); } else{ if(value>min){ st.push(value); } else{ st.push(2*value-min); min=value; } } }
public void pop() { if(st.isEmpty()){ return; } Long val = st.pop(); if(val
Dangerous question with mind blowing explanation ❤
For the optimal approach
Use Long datatype for stack and min to pass edge cases as int may overflow when we multiply it by 2
need to use long long, and nice DP btw
@@studystuff51 thank you :)
Thank you striver for the intuition. I tried to implement the min stack using DLL where node represents (val,min,next,prev)
all in O(1) optn
push and pop represents addFirst remove first, and top will always hold min
class Data{
int val;
int min;
Data next;
Data prev;
Data(int val, int min){
this.val=val;
this.min = min;
this.prev=null;
this.next=null;
}
}
class MinStack {
int min;
Data head;
Data tail;
public MinStack() {
this.min= Integer.MAX_VALUE;
this.head = new Data(-1, min);
this.tail = new Data(-1,min);
this.head.next = this.tail;
this.tail.prev = this.head;
}
public void push(int val) {
// Data node = new Data(val, this.min);
if(this.head.next == this.tail){
min = val;
Data node = new Data(val,min);
add(node);
return;
}
min = Math.min(val, this.head.next.min);//-2, -3
Data node = new Data(val, min);
add(node);
}
//(-3,-3),(0,-2),(-2,-2);
//min = -3
public void pop() {
remove(this.head.next);
//min = this.head.next.min;
}
public int top() {
return this.head.next.val;
}
public int getMin() {
return this.head.next.min;
}
public void add(Data node){
Data next = this.head.next;// -1 ->20->-1
node.next= next;
next.prev=node;
node.prev=this.head;
this.head.next=node;
}
public void remove(Data node){
//-1->10->20->-1
Data next= node.next; //20
this.head.next= next;
next.prev = this.head;
node.next=null;
node.prev=null;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
took me 1 hour to understand this code. This is awesome. The equation is just 🔥🔥🔥🔥🔥🔥
for all those who failed at 28th test case
this worked for me use long instead of int and while returing do typecast
30% Completed till now ✅✅
timestamps
0:00 - Question Overview
1:45 - brute force solving Approach
4:34 - brute force pseudocode
6:50 - Brute force Time Complexity analysis
7:15 - Optimal solving approach
15:06 -Optimal pseudocode
19:38 - Time Complexity of Optimal
20:34 - Outro
Thankyou so much Striver for great explanation
watched for ig two or three times finally got it !!
it has given medium level LC but i think it is harder to understand until striver comes here to understand us
Thank you so much for amazing explanation
00:04 Design a minimum stack that includes get min operation
02:41 Implementing Min Stack by tracking current minimum value while pushing elements.
05:00 Implementing a min stack with push, pop, and getMin operations
07:30 Implementing Min Stack using a simple stack and integer max as placeholder.
09:57 Implementing Min Stack involves inserting modified values and updating the minimum.
12:26 Modify minimum value in Min Stack implementation
15:14 Designing a minimum stack by implementing push and pop operations
17:44 Implementing Min Stack in a Stack structure
19:58 Implementing Min Stack with optimized approach
we can just use a variable which stores minimum element ,before every push , we can compare and update accordingly and while popping if we are popping min element , then we can traverse to find the min element...
Since we are trying to achieve getMin in O(1), this approach would not work.
Thank you so much for this explaination. I am following your A-Z sheet . Can you please upload videos of left Question in A-Z sheet and Article as well .
at 4:35 if a interviewer ask us to design a stack we can design it using linked but after designing how we can use in this solution like out of class..
thank you bhaiya
couldnt understand intuition behind 2*val-min at all.
For the Second method consider this code as the TUF website's code is generating wrong output for A edge test case
class MinStack {
Stack st = new Stack();
Long min;
public MinStack(){
min = Long.MAX_VALUE;
}
public void push(int val) {
Long value = Long.valueOf(val);
if(st.isEmpty()){
min = value;
st.push(value);
}
else{
if(value>min){
st.push(value);
}
else{
st.push(2*value-min);
min=value;
}
}
}
public void pop() {
if(st.isEmpty()){
return;
}
Long val = st.pop();
if(val
When heap playlist will be launched on youtube?
understood ❤
Understood ❤
Understood!!
wow got lucky, thanks for uploading
op video and
explanation
tysm sir
Why multiplication with 2
Great!
UNDERSTOOD;
Nice
Understood
understood
His expressions at 12:56 😂😂😂😂
Hello Striver, We really want you to take rest. You have been working really hard lately.
Striver means hardwork
bro looks tired
Thanks alot Bhaiya!!
Understood
Very low energy #striver_79
❤❤❤
👍👍
lesgoogogogoog
btw now i got it why striver bhaya is not providing code in the video :) so that we check the website too 😄 damn 6 star coder
only 22 testcases passed using second method
How about in first method
@@Surya-teja2612 all text case will pass
use ll
#define ll long long
class MinStack {
public:
stack st;
ll min;
MinStack() {}
void push(int val) {
if(st.empty()) {
st.push(val);
min = val;
} else {
if(val < min) {
st.push(2ll * val - min);
min = val;
} else {
st.push(val);
}
}
}
void pop() {
ll top = st.top();
if(top < min) {
min = 2ll * min - top;
}
st.pop();
}
int top() {
ll top = st.top();
if(top < min) {
return min;
} else {
return top;
}
}
int getMin() {
return min;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
understood sirrrr
Nice