Solution #1: A constant time minimum lookup can be achieved by using an extra stack. Let's call this stack 'min_stack'. This stack will always have the minimum value at the top.
Modify 'push' and 'pop' operations as follows:
push:
- If the element being pushed is less than the top element of 'min_stack' then push it on 'min_stack' as well.
- Else, push the top element of 'min_stack' again on 'min_stack'.
pop:
- Every time you pop an element from the original stack, pop from 'min_stack' as well.
Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2
original_stack min_stack
2 1
1 1
9 3
8 3
5 3
3 3
7 7
You can see that at any stage, the 'min_stack' can be queried for the minimum element in the stack.
Modify 'push' and 'pop' operations as follows:
push:
- If the element being pushed is less than the top element of 'min_stack' then push it on 'min_stack' as well.
- Else, push the top element of 'min_stack' again on 'min_stack'.
pop:
- Every time you pop an element from the original stack, pop from 'min_stack' as well.
Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2
original_stack min_stack
2 1
1 1
9 3
8 3
5 3
3 3
7 7
You can see that at any stage, the 'min_stack' can be queried for the minimum element in the stack.
2 comments:
I think the push and pop can be optimized further this way:
Push:
1. Compare element being pushed with the 'top' element of 'min_stack'
a) If new element is lesser than top of min_stack, then push this new element on both the stacks.
b) Else, push it only on the original stack.
Pop:
1. Pop the top element from original stack, and compare it with 'top' element of min_stack.
a) If they are equal, pop the 'top' of min_stack also.
This way, the size of our min_stack will not be same as that of the original stack, and thus lesser space requirement.
@Anonymous: You'r right. Thanks :)
Post a Comment