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
After seeing the equation, i derived the mathematical proof and the complete reasoning of why from scratch myself, so dont bound yourself even on seemingly complex problems guys always give it a try!
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
class MinStack { private Stack stack; private Stack minStack; public MinStack() { stack = new Stack(); minStack = new Stack(); } public void push(int val) { stack.push(val); if (minStack.isEmpty() || 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 :)
took me 1 hour to understand this code. This is awesome. The equation is just 🔥🔥🔥🔥🔥🔥
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
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 ✅✅
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
Supreme Lord for a reason 🔥🔥🔥🔥
After seeing the equation, i derived the mathematical proof and the complete reasoning of why from scratch myself, so dont bound yourself even on seemingly complex problems guys always give it a try!
it has given medium level LC but i think it is harder to understand until striver comes here to understand us
Thankyou so much Striver for great explanation
watched for ig two or three times finally got it !!
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..
When heap playlist will be launched on youtube?
Thank you so much for amazing explanation
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
couldnt understand intuition behind 2*val-min at all.
thank you bhaiya
Understood ❤
understood ❤
wow got lucky, thanks for uploading
His expressions at 12:56 😂😂😂😂
Understood!!
tysm sir
class MinStack {
public:
stack st;
int min;
MinStack() {
}
void push(int val) {
if(st.empty())
{
st.push({val,val});
min=val;
}
else
{
if(st.top().second < val)
min=st.top().second;
else
min=val;
st.push({val,min});
}
}
void pop() {
st.pop();
}
int top() {
int val=st.top().first;
return val;
}
int getMin() {
int min=st.top().second;
return min;
}
};
op video and
explanation
Great!
Hello Striver, We really want you to take rest. You have been working really hard lately.
Striver means hardwork
you look for yourself first. nothing's gonna happen with flattering.
bro looks tired
Thanks alot Bhaiya!!
Understood
understood
Nice
UNDERSTOOD;
Understood
Why multiplication with 2
❤❤❤
Very low energy #striver_79
JAVA SOLUTION Commenting for the people at 28th case:
class MinStack {
Stack st;
long Mini;
public MinStack() {
st=new Stack();
Mini=Long.MAX_VALUE;
}
public void push(int val) {
if(st.isEmpty()){
st.push((long)val);
Mini=val;
}
else if(val>Mini) st.push((long)val);
else{
st.push((long)2*val-Mini);
Mini=val;
}
}
public void pop() {
long top=st.pop();
if(topMini) return (int)top;
return (int)Mini;
}
public int getMin() {
return (int)Mini;
}
}
👍👍
lesgoogogogoog
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();
*/
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
understood sirrrr
class MinStack {
private Stack stack;
private Stack minStack;
public MinStack() {
stack = new Stack();
minStack = new Stack();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val
Understood ❤
Understood
Nice