Amazon Interview Question: Find the maximum value in a stack, with constant complexity

Notifications

Amazon

Find the maximum value in a stack, with constant complexity

Anonymous

12 Jun 2012

It's easy to keep track of the highest value when you do push. But it gets tricky when you do pop. You may need two stacks to keep track of it.

Anonymous

9 Jul 2012

@Jun: Where is the constant complexity?? You gonna push and pop every element or do you have any specific algo :P

Anonymous

1 Jun 2012

keep track of the highest value when you do a pop and push into the stack. simple.