Baseball Game: Stack-Based Score Tracking

LeetCode's Baseball Game (problem 682) is a great warm-up for stack-based thinking. It is rated easy, and the solution is a clean single-pass algorithm. The problem gives you a list of operations and asks you to simulate a scoring system where you can add, remove, double, and sum scores. Every one of those actions maps naturally to a stack operation.

The problem

You are keeping score for a baseball game with strange rules. At the start, you have an empty record. You are given a list of strings operations, where each operation is one of:

• An integer x: record a new score of x
• "+": record a new score that is the sum of the previous two scores
• "D": record a new score that is double the previous score
• "C": invalidate the previous score, removing it from the record

Return the sum of all the scores on the record after applying all the operations.

Input:  ["5", "2", "C", "D", "+"]
Output: 30

The operation "5" records 5. Then "2" records 2. Then "C" removes the 2. Then "D" doubles the top score (5), recording 10. Then "+" sums the top two scores (5 + 10), recording 15. The final record is [5, 10, 15], and their sum is 30.

Why a stack is the right tool

Every operation in this problem cares about the most recent scores. "C" removes the last score. "D" doubles the last score. "+" sums the last two scores. That "most recent" access pattern is last-in-first-out, which is exactly what a stack gives you.

You could use a plain list, but a stack makes the intent clear: you only ever look at or modify the top. Push numbers, peek at the top for "D" and "+", and pop for "C". The algorithm is a single pass through the operations list.

The approach

Walk through the operations left to right. For each operation:

1. If it is an integer, push it onto the stack.
2. If it is "C", pop the top element (invalidate the last score).
3. If it is "D", push 2 * stack[-1] (double the last score).
4. If it is "+", push stack[-1] + stack[-2] (sum the last two scores).

After processing all operations, return the sum of everything left on the stack.

That is it. No sorting, no searching, no nested loops. Just a stack and a single pass.

The code

Here is the Python solution for LeetCode 682, Baseball Game:

def cal_points(operations: list[str]) -> int:
    stack = []

    for op in operations:
        if op == "C":
            stack.pop()
        elif op == "D":
            stack.append(2 * stack[-1])
        elif op == "+":
            stack.append(stack[-1] + stack[-2])
        else:
            stack.append(int(op))

    return sum(stack)

Let's walk through the key details:

• Order of checks matters. We check for "C", "D", and "+" first, then fall through to the else for numbers. This works because the problem guarantees the input is valid, so anything that is not a special operation must be an integer string.
• No edge case guards needed. The problem guarantees that "C" is never called on an empty record, and "D" and "+" always have enough previous scores. So we do not need to check if stack before accessing elements.
• Converting strings to integers. The else branch handles both positive and negative numbers. int("-2") correctly gives -2 in Python.
• Final sum. After all operations, the stack holds every valid score. sum(stack) gives us the answer.

Step-by-step walkthrough

Let's trace through ops = ["5", "2", "C", "D", "+"]. Watch how each operation modifies the stack. The final answer is the sum of all remaining scores.

Notice how the stack acts as a living record. "C" erases history, "D" builds on the latest score, and "+" combines the two most recent scores. At the end, you just add up what is left.

Complexity analysis

Time: O(n). We process each operation exactly once. Each operation does at most one push and/or one pop, both O(1). The final sum(stack) is also O(n) in the worst case. Total work is O(n).

Space: O(n). In the worst case, every operation is a number (no "C" operations), so the stack grows to n elements.

This is optimal. You must read every operation at least once, so you cannot do better than O(n) time.

The building blocks

This problem is built on one core building block:

Stack-based simulation

The pattern of using a stack to simulate a sequence of actions where each action depends on the most recent state. You push data when recording new state, pop when undoing, and peek when computing values from recent history.

Baseball Game is one of the simplest examples, but the same idea powers harder problems:

• Min Stack: push with auxiliary tracking, maintaining O(1) access to the minimum
• Evaluate Reverse Polish Notation: push numbers, pop two when you hit an operator, push the result back
• Decode String: push state when entering nested brackets, pop and combine when closing

Whenever a problem asks you to process a sequence of commands where some commands reference or undo recent results, reach for a stack. The stack naturally maintains the "recent history" that these operations depend on.

Edge cases

Before submitting, verify your solution handles:

• All numbers. ["1", "2", "3"] with no special operations. The stack just holds all three values. Sum is 6.
• Negative numbers. ["-2", "4", "C", "D", "+"]. Push -2, push 4, pop 4, double -2 to get -4, sum -2 + (-4) = -6. Final stack: [-2, -4, -6]. Sum is -12.
• Consecutive C operations. ["5", "2", "C", "C"] removes 2 then removes 5. Stack is empty. Sum is 0.
• Large inputs. Up to 1000 operations. The O(n) solution handles this with no issues.
• D followed by D. ["3", "D", "D"] gives [3, 6, 12]. Each D doubles the current top.

The stack solution handles all of these without any special-case logic.

Reading about it is not enough

You have read through the stack simulation. The code is short, maybe 12 lines. But under interview pressure, small details trip people up. Do you check for "C" before "D"? Do you use stack[-1] or stack[0]? Do you convert with int(op) or forget and push a string?

These are not conceptual mistakes. They are recall mistakes. You understand the algorithm right now, but reproducing it from scratch three weeks later is a different skill.

Spaced repetition bridges that gap. You write the solution from memory at increasing intervals. Each repetition reinforces the operation checks, the peek/pop distinction, and the final sum. After a few cycles, the whole thing is automatic. You do not freeze on the details because you have already written this code a dozen times.

Related posts

• Min Stack - A design problem that extends the stack with O(1) minimum tracking, using synchronized auxiliary state
• Evaluate Reverse Polish Notation - Uses the same push-numbers, pop-on-operator stack pattern for expression evaluation
• Data Structure: Stacks - The full overview of how stacks work and when to use them

CodeBricks breaks stack problems into their reusable building blocks and drills them with spaced repetition. You type the solution from scratch each time, so when LeetCode 682 or any stack simulation problem shows up in an interview, the code flows without hesitation.