Implementation Removing adjacent numbers of a stack, how many remaining?

user_10658747 0
Viewed 44

Assume we have a stack with n numbers and if 3 or more adjacent numbers are equal then these numbers can be removed (the numbers are removed from top to bottom). Since this is a stack we have the normal push(), pop(), top() operations and we know n. Moreover I have an empty stack and O(1) extra memory space. Is there a linear algorithm for finding the quantity of the remaining number? If yes, what would that be?

time-complexity algorithm
2 Answers

The idea is pretty simple. We simply move the entries to the other stack and count how many we would remove. For this, we keep track of the last element and how many times we have seen it:

lastElement = ∅      //no last element
lastElementSeen = 0  //how many times did the last element occur in succession
totalRemoved = 0     //how many elements would we remove?
while(!stack.empty)
    element = stack.top
    stack.pop()
    otherStack.push(element)
    if element == lastElement
        lastElementSeen++
    else
        if lastElementSeen >= 3
            totalRemoved += lastElementSeen
        lastElement = element
        lastElementSeen = 1

You can also choose to actually remove the elements from the other stacks instead of just counting them. You could also choose to not put them in the other stack if you don't need them anymore.

user_12100530

If the constant memory space is at least N, then the naive approach is already linear :)

That is, given P = previous value (initialized to Infinity) and C = counter (initialized to 0):

  1. Pop element E off stack
  2. If E = P, increment C, else set C to 1.
  3. If C >= 3, keep popping elements, overwriting E, off second stack until E =/= P
  4. Push E onto second stack.
  5. Repeat from 1 until first stack is empty, then pop-and-push all values from temp stack back onto original, incrementing a counter for each number as you do.
user_24442100
Related