Interview Question

Interview Redwood City, CA

How to maintain a stack such that the minimum element of

  all the elements seen so far can be retrieved in constant time? O(1)
Tags:
problem solving
Answer

Interview Answer

1 Answer

0

The answer is better explained on stackoverflow.com, here's the link http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1 based on that I did write a code, but haven't checked it for extreme cases import java.util.Arrays; import java.util.Stack; public class test2 { static Stack stack=new Stack(); static Stack min_stack=new Stack(); public static void main(String args[]) { push(5); push(1); push(3); push(2); push(1); push(0); push(3); System.out.println("Min in start ="+ getmin()); System.out.println("Popped "+pop()); System.out.println("Popped "+pop()); System.out.println("Popped "+pop()); System.out.println("Popped "+pop()); System.out.println("Popped "+pop()); System.out.println("Popped "+pop()); System.out.println("Min now ="+ getmin()); } public static int getmin() { return min_stack.peek(); } public static void push(int item) { if(min_stack.empty() || item<=min_stack.peek()) { stack.push(item); min_stack.push(item); } else stack.push(item); } public static int pop() { if(stack.peek()==min_stack.peek()) { min_stack.pop(); //return stack.pop(); } return stack.pop(); } }

Jaskaran Khalsa on Mar 24, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.