Skip to main content
CodePeetCodePeet
CodePeet 250

Baseball Game

EASYProblemSolveExternal Links

Description

You are keeping score for a baseball game with unusual rules. You start with an empty score record.

You are given a list of strings called operations, where each operations[i] is one of the following four types:

  • An integer x: Record a new score of x.
  • "+": Record a new score that equals the sum of the two most recent scores.
  • "D": Record a new score that equals double the most recent score.
  • "C": Invalidate and remove the most recent score from the record.

After processing all operations, return the sum of every score remaining in the record.

The problem guarantees that every operation is valid — meaning "C" and "D" will always have at least one previous score available, and "+" will always have at least two.

Examples

Example 1

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

Output: 30

Explanation:

  • "5" → Record 5. Record: [5]
  • "2" → Record 2. Record: [5, 2]
  • "C" → Remove last score (2). Record: [5]
  • "D" → Double the last score: 2 × 5 = 10. Record: [5, 10]
  • "+" → Sum of last two: 5 + 10 = 15. Record: [5, 10, 15]

Total = 5 + 10 + 15 = 30.

Example 2

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

Output: 27

Explanation:

  • "5" → Record: [5]
  • "-2" → Record: [5, -2]
  • "4" → Record: [5, -2, 4]
  • "C" → Remove 4. Record: [5, -2]
  • "D" → Double -2: 2 × (-2) = -4. Record: [5, -2, -4]
  • "9" → Record: [5, -2, -4, 9]
  • "+" → Sum of last two: -4 + 9 = 5. Record: [5, -2, -4, 9, 5]
  • "+" → Sum of last two: 9 + 5 = 14. Record: [5, -2, -4, 9, 5, 14]

Total = 5 + (-2) + (-4) + 9 + 5 + 14 = 27.

Example 3

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

Output: 0

Explanation:

  • "1" → Record: [1]
  • "C" → Remove 1. Record: []

The record is empty, so the total sum is 0.

Constraints

  • 1 ≤ operations.length ≤ 1000
  • operations[i] is "C", "D", "+", or a string representing an integer in the range [-3 × 10^4, 3 × 10^4]
  • For operation "+", there will always be at least two previous scores on the record
  • For operations "C" and "D", there will always be at least one previous score on the record
  • The answer and all intermediate calculations fit in a 32-bit integer

Editorial

Brute Force

Intuition

This problem is a direct simulation: we process a list of commands that modify a running score record. The most natural first approach is to use a plain list (dynamic array) and apply each operation literally.

We walk through the operations one by one. If the operation is a number, we convert it to an integer and append it to our list. If it is "C", we remove the last element. If it is "D", we compute double the last element and append the result. If it is "+", we take the sum of the last two elements and append it.

Think of it like keeping a notepad. You write down each score. If someone says "cancel the last one", you erase it. If they say "double", you look at the last number and write its double as a new entry. If they say "plus", you look at the last two numbers, add them, and write the total as a new entry. At the end, you sum everything left on the notepad.

Using a list works fine, but the conceptual model is really that of a stack: we only ever care about the top one or two elements, and "C" is just a pop operation. Let us first see the list-based approach, then refine it with an explicit stack.

Step-by-Step Explanation

Let's trace through with ops = ["5", "2", "C", "D", "+"]:

Step 1: Operation "5" — this is an integer. Append 5 to the record. Record: [5].

Step 2: Operation "2" — this is an integer. Append 2 to the record. Record: [5, 2].

Step 3: Operation "C" — cancel the last score. Remove 2 from the record. Record: [5].

Step 4: Operation "D" — double the last score. Last score is 5, so double = 10. Append 10. Record: [5, 10].

Step 5: Operation "+" — sum the last two scores. Last two are 10 and 5, sum = 15. Append 15. Record: [5, 10, 15].

Step 6: All operations processed. Sum the record: 5 + 10 + 15 = 30. Return 30.

Baseball Game — Processing Operations with a List — Watch how each operation modifies the score record. Numbers are appended, 'C' removes the top, 'D' doubles the top and appends, '+' sums the top two and appends.

Algorithm

  1. Initialize an empty list called record
  2. For each operation in the operations list:
    • If the operation is "C": remove the last element from record
    • If the operation is "D": compute 2 × (last element of record), append the result
    • If the operation is "+": compute (last element) + (second-to-last element), append the result
    • Otherwise: convert the string to an integer and append it to record
  3. Return the sum of all elements in record

Code

class Solution {
public:
    int calPoints(vector<string>& operations) {
        vector<int> record;
        
        for (const string& op : operations) {
            if (op == "C") {
                record.pop_back();
            } else if (op == "D") {
                record.push_back(2 * record.back());
            } else if (op == "+") {
                int n = record.size();
                record.push_back(record[n - 1] + record[n - 2]);
            } else {
                record.push_back(stoi(op));
            }
        }
        
        int total = 0;
        for (int score : record) {
            total += score;
        }
        return total;
    }
};
class Solution:
    def calPoints(self, operations: list[str]) -> int:
        record = []
        
        for op in operations:
            if op == "C":
                record.pop()
            elif op == "D":
                record.append(2 * record[-1])
            elif op == "+":
                record.append(record[-1] + record[-2])
            else:
                record.append(int(op))
        
        return sum(record)
class Solution {
    public int calPoints(String[] operations) {
        List<Integer> record = new ArrayList<>();
        
        for (String op : operations) {
            if (op.equals("C")) {
                record.remove(record.size() - 1);
            } else if (op.equals("D")) {
                record.add(2 * record.get(record.size() - 1));
            } else if (op.equals("+")) {
                int n = record.size();
                record.add(record.get(n - 1) + record.get(n - 2));
            } else {
                record.add(Integer.parseInt(op));
            }
        }
        
        int total = 0;
        for (int score : record) {
            total += score;
        }
        return total;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the operations list once (n operations). Each operation — push, pop, peek, or arithmetic — takes O(1) time. At the end, summing all scores takes O(n) in the worst case. Total: O(n).

Space Complexity: O(n)

In the worst case (all operations are integers, no "C" cancellations), the record grows to hold all n values. The list/array storing the record uses O(n) space.

Why This Approach Is Not Efficient

The list-based simulation above already runs in O(n) time and O(n) space, which is the best we can achieve for this problem — we must read every operation and potentially store every score. So there is no asymptotic improvement possible.

However, the list-based approach uses a dynamic array which conceptually allows random access to any index. For this particular problem, we only ever interact with the end of the record: we push to the end, pop from the end, and peek at the last one or two elements. This is exactly the pattern a stack data structure is designed for.

Using a stack explicitly makes the code's intent clearer and signals to anyone reading it that only LIFO (last-in, first-out) access is needed. While the time and space complexity remain the same, the stack-based solution is more idiomatic, self-documenting, and aligns with the conceptual model of the problem. In languages like Java, using a Deque (ArrayDeque) as a stack is also slightly more efficient than ArrayList.remove() for pop operations.

Optimal Approach - Stack Simulation

Intuition

Every operation in this problem interacts only with the top of the score record:

  • Integer: Push a new score on top
  • "C": Pop the top score (remove it)
  • "D": Peek at the top score, double it, push the result
  • "+": Peek at the top two scores, sum them, push the result

This is the textbook definition of a stack. Push, pop, and peek are all O(1) operations on a stack, making it the perfect data structure for this problem.

Imagine a stack of cards face-up on a table. Each card shows a score. When you get a new number, you place a new card on top. When you hear "cancel", you discard the top card. When you hear "double", you peek at the top card, write twice its value on a new card, and place that on top. When you hear "plus", you peek at the top two cards, write their sum on a new card, and place it on top. At the end, you flip through all remaining cards and add up their values.

Step-by-Step Explanation

Let's trace through a longer example: ops = ["5", "-2", "4", "C", "D", "9", "+", "+"]:

Step 1: "5" → integer. Push 5. Stack: [5].

Step 2: "-2" → integer. Push -2. Stack: [5, -2].

Step 3: "4" → integer. Push 4. Stack: [5, -2, 4].

Step 4: "C" → cancel. Pop 4. Stack: [5, -2].

Step 5: "D" → double. Top is -2, double = -4. Push -4. Stack: [5, -2, -4].

Step 6: "9" → integer. Push 9. Stack: [5, -2, -4, 9].

Step 7: "+" → sum last two. Top two are 9 and -4, sum = 5. Push 5. Stack: [5, -2, -4, 9, 5].

Step 8: "+" → sum last two. Top two are 5 and 9, sum = 14. Push 14. Stack: [5, -2, -4, 9, 5, 14].

Step 9: Sum all: 5 + (-2) + (-4) + 9 + 5 + 14 = 27. Return 27.

Stack Simulation — Full Example Trace — Watch how each operation interacts with the top of the stack. Push for numbers, pop for 'C', peek-and-push for 'D' and '+'.

Algorithm

  1. Initialize an empty stack
  2. For each operation in the operations list:
    • If "C": pop the top element from the stack
    • If "D": peek at the top element, push (2 × top) onto the stack
    • If "+": peek at the top two elements, push (top + second) onto the stack
    • Otherwise: parse the string as an integer and push it onto the stack
  3. Pop all elements from the stack, summing them up (or iterate through and sum)
  4. Return the total sum

Code

class Solution {
public:
    int calPoints(vector<string>& operations) {
        stack<int> stk;
        
        for (const string& op : operations) {
            if (op == "C") {
                stk.pop();
            } else if (op == "D") {
                stk.push(2 * stk.top());
            } else if (op == "+") {
                int top = stk.top(); stk.pop();
                int second = stk.top();
                stk.push(top);
                stk.push(top + second);
            } else {
                stk.push(stoi(op));
            }
        }
        
        int total = 0;
        while (!stk.empty()) {
            total += stk.top();
            stk.pop();
        }
        return total;
    }
};
class Solution:
    def calPoints(self, 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)
class Solution {
    public int calPoints(String[] operations) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (String op : operations) {
            if (op.equals("C")) {
                stack.pop();
            } else if (op.equals("D")) {
                stack.push(2 * stack.peek());
            } else if (op.equals("+")) {
                int top = stack.pop();
                int second = stack.peek();
                stack.push(top);
                stack.push(top + second);
            } else {
                stack.push(Integer.parseInt(op));
            }
        }
        
        int total = 0;
        for (int score : stack) {
            total += score;
        }
        return total;
    }
}

Complexity Analysis

Time Complexity: O(n)

We process each of the n operations exactly once. Every individual operation (push, pop, peek, or arithmetic) runs in O(1) time. The final summation traverses all remaining elements, which is at most n. Total: O(n).

Space Complexity: O(n)

In the worst case, all operations are integers and the stack grows to hold n elements. No cancellations means every score stays. This is inherent to the problem — we must remember all valid scores to compute the final sum.

This is optimal for this problem. We cannot do better than O(n) time because we must read every operation, and we cannot do better than O(n) space because we may need to retain all scores.