Baseball Game — Stack Simulation for Record Scoring

Problem Statement#

You are keeping score for a baseball game with strange rules. You are given a list of strings ops where each element is one of the following:

• 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 scores on the record after applying all operations.

Constraints:

• 1 <= ops.length <= 1000
• ops[i] is "C", "D", "+", or a string representing an integer in the range [-3 * 10^4, 3 * 10^4].
• For "+", there will always be at least two previous scores.
• For "D" and "C", there will always be at least one previous score.

Input:  ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5"  → record [5]
"2"  → record [5, 2]
"C"  → invalidate 2 → record [5]
"D"  → double 5 → record [5, 10]
"+"  → 5 + 10 = 15 → record [5, 10, 15]
Sum = 5 + 10 + 15 = 30

Input:  ops = ["5","-2","4","C","D","9","+","+"]
Output: 27

Input:  ops = ["1","C"]
Output: 0

Why This Problem Matters#

LC 682 is an excellent warm-up problem that tests whether you can naturally reach for a stack when "undo" or "most recent element" access is needed. The "C" operation (invalidate the last record) is a classic undo operation — the hallmark of stack-based thinking.

This simulation pattern — where you maintain a mutable history of records with possible reversals — appears in real-world systems: text editors with undo history, spreadsheet formula evaluation, transaction logs, and command queues.

Companies that ask this problem: Amazon, Facebook (Meta), and Bloomberg. It is typically a warm-up before harder stack problems like Daily Temperatures or Largest Rectangle in Histogram.

The Core Insight#

A stack is the perfect data structure here because:

• "+" needs the last two elements — stack[-1] and stack[-2].
• "D" needs the last one element — stack[-1].
• "C" removes the last element — stack.pop().
• An integer adds to the record — stack.append(x).

All operations are O(1) on a stack. The total sum is just sum(stack) at the end.

The LIFO property of a stack naturally captures "the most recent valid record" at all times.

Visual Dry Run#

Input: ops = ["5","2","C","D","+"]

Sum = 5 + 10 + 15 = 30

Input: ops = ["5","-2","4","C","D","9","+","+"]

Sum = 5 + (-2) + (-4) + 9 + 5 + 14 = 27

Solution (Optimal)#

# Python — stack simulation, O(n) time and space
def calPoints(ops: list[str]) -> int:
    stack = []  # valid score records
 
    for op in ops:
        if op == '+':
            # Sum of the last two scores
            # Guaranteed at least two elements exist
            stack.append(stack[-1] + stack[-2])
        elif op == 'D':
            # Double the last score
            stack.append(2 * stack[-1])
        elif op == 'C':
            # Invalidate (remove) the last score
            stack.pop()
        else:
            # Regular integer score
            stack.append(int(op))
 
    return sum(stack)

// JavaScript — stack simulation, O(n) time and space
function calPoints(ops) {
    const stack = [];
 
    for (const op of ops) {
        if (op === '+') {
            // Sum of the last two scores
            stack.push(stack[stack.length - 1] + stack[stack.length - 2]);
        } else if (op === 'D') {
            // Double the last score
            stack.push(2 * stack[stack.length - 1]);
        } else if (op === 'C') {
            // Invalidate (remove) the last score
            stack.pop();
        } else {
            // Regular integer score — parse string to number
            stack.push(parseInt(op, 10));
        }
    }
 
    return stack.reduce((sum, val) => sum + val, 0);
}

Complexity:

Common Mistakes#

1. Using op == '+' before checking op == 'C' and op == 'D'. The order of conditions matters only if your implementation treats unknown ops differently. The cleanest pattern is to check each special character first and fall through to int(op) last.

2. Not parsing the integer for regular scores. Ops come as strings. Forgetting int(op) means you append the string "5" to the stack, and later stack[-1] + stack[-2] does string concatenation instead of addition.

3. Using stack[-1] and stack[-2] for "+" in the wrong order. The sum is stack[-1] + stack[-2] — both are symmetric for addition, but the conceptual meaning matters: last score plus second-to-last score.

4. For Java: not peeking before popping for "+". In Java, you need stack.peek() plus a temporary pop to access the second element: int a = stack.pop(); int b = stack.peek(); stack.push(a); stack.push(a + b);. Forgetting to re-push a destroys the record.

5. Calling sum() at every step instead of at the end. Only compute the sum once after all operations — computing it inside the loop is O(n^2) overall.

Interview Tips#

• Identify the undo pattern immediately: "The C operation removes the last valid record — that is stack.pop(). The D and + operations need the last one or two elements — that is stack[-1] and stack[-2]. A stack gives all of this in O(1)."
• Note that the problem guarantees valid operations — you do not need to guard for empty stack on C, D, or + calls. But mention it: "The constraints guarantee valid calls, but I would add guards in production."
• Discuss the space trade-off: "In the worst case, every operation is an integer or D, so the stack grows to n elements."

Follow-up Questions#

1. What if you need to support undo of the last k operations? Track a history of operations; on undo, replay the prefix without the last k.
2. What if scores are floating point? Same logic — just use float(op) instead of int(op).
3. What if C can appear multiple times in a row? Each C pops one element; multiple consecutive C operations pop multiple elements. The current solution already handles this correctly.
4. What if you need to track the maximum score ever recorded? Maintain a parallel max variable or max stack alongside the score stack.
5. Generalize: implement a calculator with undo. This is a superset — maintain an operation history and replay on undo. LC 1472 (Design Browser History) is a related problem.

Key Takeaways#

• A stack is ideal when you need access to the most recent element and undo (remove last) — both O(1) with a stack.
• The "C" operation is a textbook undo — stack.pop() — which is why this problem naturally maps to a stack.
• Parse strings to integers carefully: int(op) in Python, Integer.parseInt(op) in Java, parseInt(op, 10) in JavaScript.
• The Java "+" case requires a temporary pop-peek-re-push pattern to access the second-from-top element without a direct index.
• This problem is typically a FAANG warm-up; the interviewer is watching for fluency with stack operations and clean string parsing, not algorithmic complexity.
• Always compute the final sum() after all operations, not inside the loop, to maintain O(n) overall time.