anvol
BAN USERUsing two stacks. One for adding, second for removing items.
Befor add/remove check where are items and pop them if needed.
O(n) for enqueue, O(n) for dequeue in worst case. Sequential adding - O(1).
Sequential dequeue - O(1).
Worst case for switching from/to enqueue/dequeue
Stack<int> stackAdd = new Stack<int>();
Stack<int> stackRemove = new Stack<int>();
public void Enqueue(int item)
{
if (stackAdd.Count == 0) RevertStacks();
stackAdd.Push(item);
}
public int Dequeue()
{
if (stackRemove.Count == 0) RevertStacks();
return stackRemove.Pop();
}
private void RevertStacks()
{
if (stackAdd.Count > 0)
while(stackAdd.Count > 0) stackRemove.Push(stackAdd.Pop());
else if (stackRemove.Count > 0)
while(stackRemove.Count > 0) stackAdd.Push(stackRemove.Pop());
}
This is my version in C#.
public void NextGreatestElement(int[] inp)
{
Stack<int> stack = new Stack<int>();
stack.Push(inp[0]);
for (int i = 1; i < inp.Length; i++) {
while (stack.Count>0 && stack.Peek() < inp[i])
{
Console.WriteLine("{0} -> {1}", stack.Peek(), inp[i]);
stack.Pop();
}
stack.Push(inp[i]);
}
foreach(int i in stack) Console.WriteLine("{0} -> {1}", i, -1);
}
for your example there is an exception (mentioned in the hint) - sum 4 and your code will return true. Hinted case - case when element = half of sum.
- anvol April 05, 2013