Amazon Interview Question Software Engineer / Developers
3of 3 votesImplement a stack with O(1) push, pop, and min
Country: United States
Interview Type: In-Person
No, after pop() the new head node already has the min value for that level in the stack.
I was asked this recently, and it all boiled down to "how would a human do it?"
You can sort of reason that O(1) space is impossible. That is, a "max" variable augmented on the stack is insufficient.
Think of two extreme cases.
{As a human}
Pushing these in this order: 7 6 5 4 3 2 1 <=== O(1) unchanging max variable would work only (fluke)
Pushing these in this order: 1 2 3 4 5 6 7 <=== Ouch, after every pop we need to recalculated the max "below" the thing we popped.
So take the 2nd extreme case... after every pop, what "would" you need to recalculate the new_max in O(1) time?
After I pop the 7, I kind of need the max "below the 7" for any further min queries.
After I pop the 6, I kind of need the max "below the 6" for any further min. queries.
So it would seem on every push() we should push with it the new max "at that point in time (I use time loosely here)."
That is, push: < new_elem, new_max>
What is new_max ? It would seem to be, MAXVAL( new_elem, max_stored_with_old_top )
Try it on paper.
public class Stack<T> {
private class Item {
public T Value;
public Item Next;
}
private Item First;
private Stack MinStack;
public Stack<T>() {
Stack = new Stack<T>();
}
public T Peek() {
return First.Value;
}
public void Push(T value) {
Item item = new Item();
item.Value = value;
item.Next = First;
if (Value < MinStack.Peek()) {
MinStack.Push(Value);
} else {
MinStack.Push(MinStack.Peek());
}
First = item;
}
public T Pop() {
Item item = First;
First = First.Next;
MinStack.Pop();
return item.Value;
}
public T Min() {
return MinStack.Peek();
}
}
public class Stack<T> {
private class Item {
public T Value;
public Item Next;
}
private Item First;
private Stack MinStack;
public Stack<T>() {
Stack = new Stack<T>();
}
public T Peek() {
return First.Value;
}
public void Push(T value) {
Item item = new Item();
item.Value = value;
item.Next = First;
if (Value < MinStack.Peek()) {
MinStack.Push(Value);
} else {
MinStack.Push(MinStack.Peek());
}
First = item;
}
public T Pop() {
Item item = First;
First = First.Next;
MinStack.Pop();
return item.Value;
}
public T Min() {
return MinStack.Peek();
}
}
import java.util.Iterator;
import java.util.NoSuchElementException;
class MinStack<T> {
private int size;
private Node top;
private class Node {
T item;
Node next;
}
public void push(T item) {
Node prev=top;
top=new Node();
top.item=item;
top.next=prev;
}
public T pop() {
if(isEmpty()) throw new RuntimeException("Stack underflow");
T item=top.item;
top=top.next;
size--;
return item;
}
public T peek() {
if(isEmpty()) throw new RuntimeException("Stack underflow");
T item=top.item;
return item;
}
public boolean isEmpty() {
return top==null;
}
}
public class Stack<T extends Comparable<T>> implements Iterable<T>{
private int size;
private Node top;
private MinStack<T> minStack=null;
private class Node {
T item;
Node next;
}
public Stack() {
top=null;
size=0;
minStack=new MinStack<T>();
}
public boolean isEmpty() {
return top==null;
}
public int size() {
return size;
}
public void push(T item) {
Node prev=top;
top=new Node();
top.item=item;
top.next=prev;
if(minStack.isEmpty()) {
minStack.push(item);
}
else {
T min=minStack.peek();
while(min.compareTo(item)>0) {
minStack.pop();
minStack.push(item);
min=minStack.peek();
}
}
size++;
}
public T min() {
if(minStack.isEmpty())throw new RuntimeException("Stack underflow");
return minStack.peek();
}
public T pop() {
if(isEmpty()) throw new RuntimeException("Stack underflow");
T item=top.item;
top=top.next;
size--;
if(item==minStack.peek())
minStack.pop();
return item;
}
public T peek() {
if(isEmpty()) throw new RuntimeException("Stack underflow");
T item=top.item;
return item;
}
public String toString() {
StringBuilder s = new StringBuilder();
for (T item : this)
s.append(item + " ");
s.append("\n"+"Min:"+min());
return s.toString();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack<String> s = new Stack<String>();
s.push("abc");
s.pop();
s.push("cde");
s.push("de");
s.pop();
s.push("zeb");
System.out.println(s);
}
@Override
public Iterator<T> iterator() {
// TODO Auto-generated method stub
return new StackIterator();
}
private class StackIterator implements Iterator<T> {
private Node current=top;
public boolean hasNext() { return current!=null; }
public void remove() { throw new UnsupportedOperationException(); }
public T next() {
if (!hasNext()) throw new NoSuchElementException();
T item = current.item;
current = current.next;
return item;
}
}
}
Keep a increase queue and record the number of items who is larger then each item.
#include <queue>
#include <stdio.h>
using namespace std;
class SpecialStack{
deque<int> Q;
deque<int> cntQ;
public:
SpecialStack() {
Q.clear();
cntQ.clear();
}
void push(int x){
int cnt = 1;
while(Q.size()>0&&Q.back()>=x){
Q.pop_back();
cnt+=cntQ.back();
cntQ.pop_back();
}
Q.push_back(x);
cntQ.push_back(cnt);
}
void pop(){
if (Q.size()==0) return ;
int cnt = cntQ.front();
cntQ.pop_front();
cnt--;
if (cnt==0){
Q.pop_front();
}else {
cntQ.push_front(cnt);
}
}
int getMin(){
if (Q.size()>0)
return Q.front();
else return -1;
}
};
push() and pop() are already O(1). To implement a Stack to ensure O(1) getMin(), one would need to have two stacks: 1. mainStack, 2. minimumStack and push, pop and getminimum needs to be implemented as below:
public void push(int data){
mainStack.push(data);
if(minimumStack.isEmpty() || minimumStack.top() >= data){
minimumStack.push(data);
}
}
public int pop(){
if(mainSTack.isEmpty())
return -1;
int minTop = minimumStack.top();
int mainTop = mainStack.top();
if(mainTop == minTop)
minimumStack.pop();
return mainStack.pop();
}
public int getMinimum(){
return minimumStack.top()
}
public class Stack<Item extends Comparable<Item>> {
Node first;
Node minimum;
private class Node {
Item value;
Node next;
Node nextMin;
Node(Item value, Node next) {
this.value=value;
this.next=next;
}
Node(Item value) {
this.value=value;
}
}
public Stack() {
super();
}
public void push(Item value) {
if(first==null) {
first=new Node(value);
minimum=first;
}
else {
first=new Node(value,first);
if(value.compareTo(minimum.value)<=0) {
Node temp=minimum;
minimum=first;
minimum.nextMin=temp;
}
}
}
public Item pop() {
if(first==null)
return null;
else {
Item returnValue=first.value;
if(first==minimum)
minimum=minimum.nextMin;
first=first.next;
return returnValue;
}
}
public Item min() {
if(minimum==null)
return null;
else
return minimum.value;
}
}
Non-constant-space solution
Keep a "duplicate" stack of "minimum of all values lower in the stack". When you pop the main stack, pop the min stack too. When you push the main stack, push either the new element or the current min, whichever is lower. getMinimum() is then implemented as just minStack.peek().
So using your example, we'd have:
Real stack Min stack
5 --> TOP 1
1 1
4 2
6 2
2 2
After popping twice you get:
Real stack Min stack
4 2
6 2
2 2
Please let me know if this isn't enough information. It's simple when you grok it, but it might take a bit of head-scratching at first :)
(The downside of course is that it doubles the space requirement. Execution time doesn't suffer significantly though - i.e. it's still the same complexity.)
EDIT: There's a variation which is slightly more fiddly, but has better space in general. We still have the min stack, but we only pop from it when the value we pop from the main stack is equal to the one on the min stack. We only push to the min stack when the value being pushed onto the main stack is less than or equal to the current min value. This allows duplicate min values. getMinimum() is still just a peek operation. For example, taking the original version and pushing 1 again, we'd get:
Real stack Min stack
1 --> TOP 1
5 1
1 2
4
6
2
Popping from the above pops from both stacks because 1 == 1, leaving:
Real stack Min stack
5 --> TOP 1
1 2
4
6
2
Popping again only pops from the main stack, because 5 > 1:
Real stack Min stack
1 1
4 2
6
2
Popping again pops both stacks because 1 == 1:
Real stack Min stack
4 2
6
2
This ends up with the same worst case space complexity (double the original stack) but much better space usage if we rarely get a "new minimum or equal".
This wouldn't work if you popped numbers off the stack.
Ex. 2,4,5,3,1. After you pop 1 off, what is your minimum?
The solution is to keep a stack of minimums, not just a single value. If you encounter a value that is less than equal to the current minimum, you need to push it onto the min-stack.
private static class MinStack
{
private static class Node
{
public int x;
public Node next;
public Node min;
public Node(int x, Node next, Node prevMin)
{
this.x = x;
this.next = next;
this.min = prevMin;
}
}
Node head;
public MinStack()
{
head = null;
}
public void push(int x)
{
if (head == null)
{
head = new Node(x, null, null);
head.min = head;
}
else
{
Node n = new Node(x, head, null);
n.min = head.min.x < x ? head.min : n;
head = n;
}
}
public int pop()
{
int x = head.x;
if (head.next != null)
{
head = head.next;
}
else
{
head = null;
}
return x;
}
public boolean isEmpty()
{
return head == null;
}
public int min()
{
return head.min.x;
}
}
public static void main(String[] args) {
MinStack s = new MinStack();
s.push(2);
s.push(1);
s.push(10);
while (!s.isEmpty())
{
System.out.println("min: " + s.min() + " pop: " + s.pop());
}
}
//We will maintain one auxiliary stack which will store
//only the minimum value from the main stack.
//Also, the element from top of the auxiliary stack will
//be removed when we do pop operation and the top element
//from both the stacks are same.
public class Stack {
private int size;
private int[] arr;
private int[] minArr;
private int top;
private int topMin;
public Stack(int size){
this.size=size;
top=-1;
topMin=-1;
arr=new int[size];
minArr=new int[size];
}
public void push(int val){
if(top==size-1){
System.out.println("Stack full !! Cannot do PUSH operation.");
return;
}
arr[top++]=val;
if(topMin!=-1){
if(minArr[topMin]<=val){
minArr[topMin++]=val;
}
}
else{
minArr[topMin++]=val;
}
}
public int pop(){
if(top==-1){
System.out.println("Stack empty !! Cannot do POP operation.");
return 0;
}
if(arr[top]==minArr[topMin]){
topMin--;
}
return arr[top--];
}
public int min(){
return minArr[topMin];
}
}
Pseudo code
Each element of stack keeps a track of the minimum element below it. To retrieve the minimum element of the stack return the minimum element of top element.
#define max 100;
int Stack[max], minStack[max];
int top = -1;
void push(int elm, int *stack){
Stack[++top]=elm;
if ( top==0 ){
minStack[top]=elm;
}
else{
if(minStack[top-1]<elm){
minStack[top] = minStack[top-1];
}
else{
minStack[top]=elm;
}
}
void pop(){
top--;
}
int min(){
return minStack[top];
}
We can do this using an ensemble of three data structures, namely, two stacks and one hash table.
1. Insert : O(1)
s1.push(val);
table[val]++;
if(s2.top()>val)
s2.push(val);
2. On min: O(1)
return s2.top();
3. On delete: O(1)
val=s1.top();
table[val]--;
if(table[val]==0 && s2.top()==val)
s2.pop();
return val;
However, it requires 3 times as much space as an ordinary stack!
SortAndAdd(struct ** ref , int element)
{
if(IsEmpty(*ref)) {
push(ref , element);
return;
}
if (element > (*ref)->data) {
int temp = pop(ref);
SortAndAdd(ref , element);
push(ref , element);
}
else {
push(ref , element);
}
}
The above code is slightly incorrect . Below is the modified code snippet
SortAndAdd(struct ** ref , int element)
{
if(IsEmpty(*ref)) {
push(ref , element);
return;
}
if (element > (*ref)->data) {
int temp = pop(ref);
SortAndAdd(ref , element);
push(ref , temp);
}
else {
push(ref , element);
}
}
Use two stacks;
//Implement a stack with O(1) push pop and min
//Using NSMutableArray
#import<Foundation/Foundation.h>
#import<UIKIt/UIKit.h>
@interface Stacks
@property(nonatomic)NSMutableArray *stacks
@property(nonatomic)NSMutableArray *minStacks
-(void)push:(int)value;
-(int)pop;
-(int)min;
@end
@implementation Stacks
-(NSMutableArray*) minStacks
{
if(!_minStacks)
{
_minStacks = [[NSMutableArray alloc]init];
}
return _minStacks;
}
-(NSMutableArray*)stacks
{
if(!_stacks)
{
_stacks = [[NSMutableArray alloc]init];
}
return _stacks;
}
-(void)push:(int)value
{
[self.stacks addObject:[NSNumber numberFromInt:value]];
if([minStacks length]>0)
{
if(value<[[minStacks lastObject]intValue])
{
[minStacks removeLastObject];
[minStacks addObject:[NSNumber numberFromInt:value]];
}
}else
{
[minStacks addObject:[NSNumber numberFromInt:value]];
}
}
-(int)pop
{
if([self.stacks length]>0)
{
if([[self.stacks lastObject]intValue]<[[self.minStacks lastObject]intValue])
{
[minStacks removeLastObject];
}
return [self.stacks lastObject];
}else
{
return;
}
}
-(int)min
{
if([self.minStacks length]>0)
{
return [self.minStacks lastObject];
}else
return 0;
}
@end
A few people missed this -- when testing if the value currently being pushed onto the stack is less than the minimum, you should also test if it is equal to the current minimum. This will cause you to have duplicates in your min stack, but if you think about it this is exactly what you want if you push duplicate minimum values in your original stack.
Try your solution with alternating equivalent minimums eg. 1 3 1 4 1 5
Stack: 5->1->4->1->3->1
Min stack: 1->1->1
This way, if the value you're currently popping is equal to the current min, you just pop the min from the min stack as well.
- Michael.J.Keating October 14, 2013public class MinStack { private Node _head; public void push(int value) { Node node = new Node(); node.value = value; if (_head == null) { node.minValue = node.value; _head = node; } else { node.minValue = node.value < _head.minValue ? node.value : _head.minValue; node.next = _head; _head = node; } } public int pop() { if (_head == null) return -1; Node node = _head; _head = node.next; return node.value; } public int min() { if (_head == null) return -1; return _head.minValue; } private class Node { int value; int minValue; Node next; } }