Skip to content

Instantly share code, notes, and snippets.

@KodeSeeker
Last active April 12, 2020 20:02
Show Gist options
  • Save KodeSeeker/9849433 to your computer and use it in GitHub Desktop.
Save KodeSeeker/9849433 to your computer and use it in GitHub Desktop.
Stack that Support Push, Pop, and GetMin in Constant Time
/*
Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?
Solution:
Keep a stack of minimums: Extra memory
*/
public class StackWithMin{
private Stack<Integer> normalstk=new Stack<Integer>();
private Stack<Integer> minstk=new Stack<Integer>();
// while pushing into
//Push into minstk if inserted element is smaller than smallest input element or if minstk is empty
//
public void push(int input)
{
if(minstk.isEmpty()|| (x<minstk.top() )
minstk.push(input);
//push into normal stk anyways
normalstk.push(input);
}
//while popping if element is =minstk.top then pop from minstk too
public int pop()
{
if normalstk.isEmpty()
return -1; //stk is empty
int ret=normalstk.pop();
if(ret==minstk.top())
minstk.pop();//pop from minstk as well!
return ret;
}
//get the minimum at any point
public int getMin()
{
if(minstk.isEmpty())
return -1;
return minstk.pop();
}
}
@mhamzawey
Copy link

I think if(minstk.isEmpty()|| (x<minstk.top() ) needs to be if(minstk.isEmpty()|| (x<=minstk.top() ), What do you think?

following test case fails:

["push","push","push","getMin","pop","getMin"]
[[0],[1],[0],[],[],[]]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment