Baseball Game

Problem Description

You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.

You are given a list of strings operations, where operations[i] is the i-th operation you must apply to the record and 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 the scores on the record after applying all the operations.

Examples

Constraints

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

LIFO Stack for Score History

Because the operations +, D, and C always refer to the most recently recorded scores, this history matches the Last-In, First-Out behavior of a stack. We iterate through the operations.

• If we see +, we pop the last score, read the second last, add them, and push both back followed by the sum.
• If we see D, we peek the top score, double it, and push the doubled value.
• If we see C, we pop and discard the top score.
• Otherwise, parse the string as an integer and push it onto the stack. Finally, sum all elements in the stack.

Solution 1: Stack History Recorder

Use a stack to track scores dynamically and calculate the final sum.

import java.util.Stack;

class Solution {
    public int calPoints(String[] operations) {
        Stack<Integer> stack = new Stack<>();
        for (String op : operations) {
            if (op.equals("+")) {
                int top = stack.pop();
                int newTop = top + stack.peek();
                stack.push(top); // push back the first popped value
                stack.push(newTop);
            } else if (op.equals("D")) {
                stack.push(2 * stack.peek());
            } else if (op.equals("C")) {
                stack.pop();
            } else {
                stack.push(Integer.parseInt(op));
            }
        }

        int total = 0;
        for (int score : stack) {
            total += score;
        }
        return total;
    }
}

class Solution:
    def calPoints(self, operations: list[str]) -> int:
        stack = []
        for op in operations:
            if op == "+":
                stack.append(stack[-1] + stack[-2])
            elif op == "D":
                stack.append(2 * stack[-1])
            elif op == "C":
                stack.pop()
            else:
                stack.append(int(op))
        return sum(stack)

#include <vector>
#include <string>
#include <numeric>

class Solution {
public:
    int calPoints(std::vector<std::string>& operations) {
        std::vector<int> stack;
        for (const std::string& op : operations) {
            if (op == "+") {
                stack.push_back(stack.back() + stack[stack.size() - 2]);
            } else if (op == "D") {
                stack.push_back(2 * stack.back());
            } else if (op == "C") {
                stack.pop_back();
            } else {
                stack.push_back(std::stoi(op));
            }
        }
        return std::accumulate(stack.begin(), stack.end(), 0);
    }
};

Complexity Analysis

• Time Complexity: O(n) since we iterate through the operations list once and push/pop elements in O(1) time.
• Space Complexity: O(n) auxiliary space to store elements in the stack.

Where It Breaks

If the operations history is very long and cannot fit in memory, we must track the sum on the fly. However, since the operations can remove items (C), storing history is required.

Common Mistakes

• Incorrect order on +: Forgetting to push the first popped element back onto the stack in Java/C++ before pushing the sum.
• Underflow checks: Running operations when the stack lacks enough elements (though prevented by constraints in this problem).

Frequently Asked Questions

Why use a vector in C++ instead of std::stack? A vector allows us to access elements at specific offsets (like stack[size - 2]) without having to pop and push elements back, making the code cleaner.

Can we calculate the sum dynamically during operations? Yes. You can add elements to a running sum during insertion and subtract them during removals, but you still need the stack to know which values to subtract or double.

← All Problems