If data structure augmentation and designing algorithms give you a high and you wish to post in this forum email me(Inder) at inder.pall@gmail.com
DISCLAIMER : questions posted here could be from multiple source, i'll try my best to provide credit.
I think Rohan has posted this solution on my google BUZZ..putting it here.
Use two stacks 1. to put data and keep track of the current minimum and push it in a different stack 2. intent is that the other stack will hold minimums with respect to how data was loaded in stack at each index. 3. on pop operation do a pop from the other stack also to get the current minium on top w.r.t elements in the other stack
Stack should be implemented using the following Data Structure:
struct stack { int data; int min; stack* next; };
So, every node of the stack should store the min element till its position in the stack. This will enable GetMin() to operate in O(1) time.
Whenever a new element is inserted in the stack, its value should be compared with the min of "previous top element" of the stack. If lesser, the min for this node will be the same element, else min for this node will be previous top element's min.
4 comments:
I think Rohan has posted this solution on my google BUZZ..putting it here.
Use two stacks
1. to put data and keep track of the current minimum and push it in a different stack
2. intent is that the other stack will hold minimums with respect to how data was loaded in stack at each index.
3. on pop operation do a pop from the other stack also to get the current minium on top w.r.t elements in the other stack
Example:
Input - 5 10 2 8 1
1. initially both stacks empty
s1 = { }
s2 = { }
2. insert 5
s1 = { 5 }
s2 = { 5 }
3. insert 10
s1 = { 5, 10}
s2 = { 5, 5 }
4. insert 2
s1 = { 5, 10, 2}
s2 = { 5, 5, 2}
5. insert 8
s1 = { 5, 10, 2, 8}
s2 = { 5, 5, 2, 2}
6. insert 1
s1 = { 5, 10 , 2, 8, 1}
s2 = { 5, 5, 2, 2, 1}
PS: to populate s2 in O(1) do the following operation
if peep(s2) > currentelement
push(currentelement, s2)
else
push(peep(s2), s2)
The idea should be:
Stack should be implemented using the following Data Structure:
struct stack
{
int data;
int min;
stack* next;
};
So, every node of the stack should store the min element till its position in the stack. This will enable GetMin() to operate in O(1) time.
Whenever a new element is inserted in the stack, its value should be compared with the min of "previous top element" of the stack. If lesser, the min for this node will be the same element, else min for this node will be previous top element's min.
I guess we can do like this:
Example:
Input - 5 10 2 8 1
1. initially both stacks empty
s1 = { }
s2 = { }
2. insert 5
s1 = { 5 }
s2 = { 5 }
3. insert 10
s1 = { 5, 10}
s2 = { 5}
4. insert 2
s1 = { 5, 10, 2}
s2 = { 5, 2}
5. insert 8
s1 = { 5, 10, 2, 8}
s2 = { 5, 2}
6. insert 1
s1 = { 5, 10 , 2, 8, 1}
s2 = { 5, 2, 1}
on pop we must peep top of s2 if both s1.pop() and s2.peep(top) are equal pop() both s1 and s2 else pop s1 alone.
Post a Comment