Apply One Stack Reduction

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement reduce_adjacent_pairs(tokens). Scan left to right and remove adjacent equal pairs repeatedly: when the current token equals the stack top, pop it; otherwise push it. Return the remaining tokens in order.

Starter code

def reduce_adjacent_pairs(tokens):
    pass

Test cases

cascade

{
  "args": [
    [
      "a",
      "b",
      "b",
      "a",
      "c"
    ]
  ]
}

Expected: ["c"]

no-pairs

{
  "args": [
    [
      1,
      2,
      3
    ]
  ]
}

Expected: [1,2,3]

Wizard outline

Step 1: Create the survivor stack
Return an empty stack for an empty token stream. The output container is also the state that later comparisons and cancellations will maintain.
Step 2: Cancel one adjacent pair
Push distinct tokens and pop when the next token equals the current top. One cancellation demonstrates why only the latest unmatched survivor can pair with the next token.
Step 3: Continue cascading cancellations
Process every token so each pop exposes the correct survivor for the next comparison. Removing the teaching stop lets local adjacent decisions produce the complete cascading reduction.

Footguns and prerequisites

Comparing with the original previous token misses pairs created by an earlier pop.
Pushing the current token after a successful pop prevents the pair from being removed.
python specific rapid fire

Reviewed references

Python More on Lists

Prepared Interview Problems

Evaluate Reverse Polish Notation(opens in a new tab)
Apply One Stack Reduction isolates the stack is the fully reduced form of the processed prefix and contains no adjacent equal pair. That focused state discipline is required when implementing evaluate reverse polish notation as a complete Interview Problem.
Implement Stack Using Queues(opens in a new tab)
Apply One Stack Reduction isolates the stack is the fully reduced form of the processed prefix and contains no adjacent equal pair. That focused state discipline is required when implementing implement stack using queues as a complete Interview Problem.
Min Stack(opens in a new tab)
Apply One Stack Reduction isolates the stack is the fully reduced form of the processed prefix and contains no adjacent equal pair. That focused state discipline is required when implementing min stack as a complete Interview Problem.

Recommended approach and implementation

When each new item can combine only with the most recent unresolved item, a stack represents exactly the pending state. The stack is the fully reduced form of the processed prefix and contains no adjacent equal pair.

Why it works: For each token, an equal stack top forms the only new adjacent pair and both are removed; otherwise pushing creates no reducible pair. Induction over the input proves the final stack is exactly the complete reduction.

def reduce_adjacent_pairs(tokens):
    stack = []
    for token in tokens:
        if stack and stack[-1] == token:
            stack.pop()
        else:
            stack.append(token)
    return stack