682. Baseball Game - Leetcode Solution

LeetCode problem

Solution code

💡 Step-by-Step Thought Process

Understand the problem: Calculate the total score from a list of operations where each operation is a number, "+", "D", or "C".
Initialize an empty stack to store scores.
Iterate through each operation in the input list.
If the operation is "+", add the sum of the last two scores in the stack to the stack.
If the operation is "D", double the last score and add it to the stack.
If the operation is "C", remove the last score from the stack.
If the operation is a number, convert it to an integer and add it to the stack.
Sum all scores in the stack and return the total.

Code Solution

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        stk = []

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

        return sum(stk)

# Time Complexity: O(n)
# Space Complexity: O(n)

#include <vector>
#include <stack>
#include <string>
#include <sstream>

using namespace std;

class Solution {
public:
    int calPoints(vector<string>& operations) {
        stack<int> stk;

        for (const string& op : operations) {
            if (op == "+") {
                int top = stk.top(); stk.pop();
                int newTop = top + stk.top();
                stk.push(top);
                stk.push(newTop);
            } else if (op == "D") {
                stk.push(2 * stk.top());
            } else if (op == "C") {
                stk.pop();
            } else {
                stk.push(stoi(op));
            }
        }

        int sum = 0;
        while (!stk.empty()) {
            sum += stk.top(); stk.pop();
        }

        return sum;
    }
};

import java.util.*;

public 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);
                stack.push(newTop);
            } else if (op.equals("D")) {
                stack.push(stack.peek() * 2);
            } else if (op.equals("C")) {
                stack.pop();
            } else {
                stack.push(Integer.parseInt(op));
            }
        }

        int sum = 0;
        while (!stack.isEmpty()) {
            sum += stack.pop();
        }
        
        return sum;
    }
}

/**
 * @param {string[]} operations
 * @return {number}
 */
var calPoints = function(operations) {
    const stack = [];

    for (const op of operations) {
        if (op === "+") {
            const top = stack.pop();
            const newTop = top + stack[stack.length - 1];
            stack.push(top);
            stack.push(newTop);
        } else if (op === "D") {
            stack.push(stack[stack.length - 1] * 2);
        } else if (op === "C") {
            stack.pop();
        } else {
            stack.push(parseInt(op));
        }
    }

    return stack.reduce((acc, val) => acc + val, 0);
};

Detailed Explanation

Understanding the Problem: Baseball Game

The “Baseball Game” problem is a simulation-based question where you’re asked to calculate the total score of a baseball game from a list of operations. Each operation is one of the following:

Integer: Add this number to the score.
"+": Add the sum of the previous two scores.
"D": Double the previous score and add it.
"C": Invalidate and remove the previous score.

Your task is to evaluate the sequence of operations and return the total score after all operations are processed.

Why This Problem Matters

This problem is a great test of your ability to simulate a stack-based process, especially where operations depend on previously recorded values. It is often asked in interviews because it challenges your understanding of state maintenance and control flow.

Optimal Approach: Use a Stack

Since the rules of the problem depend on previous operations, a stack is the perfect data structure to keep track of the score history. You can push scores, pop them when canceled, and peek at the top of the stack to retrieve recent values.

Steps:

Initialize an empty stack scores.
Loop through each operation in the input list:
- If the operation is "+", compute the sum of the last two elements and push it onto the stack.
- If the operation is "D", double the last score and push it onto the stack.
- If the operation is "C", remove the last score by popping from the stack.
- If it's a numeric string, convert it to an integer and push it onto the stack.
Once all operations are complete, sum all values in the stack to get the total score.

Example Walkthrough

Input: ["5", "2", "C", "D", "+"]
Execution steps:

"5" → push 5 → stack: [5]
"2" → push 2 → stack: [5, 2]
"C" → pop 2 → stack: [5]
"D" → push 10 (2×5) → stack: [5, 10]
"+" → push 15 (5+10) → stack: [5, 10, 15]

Final score = 5 + 10 + 15 = 30

Time and Space Complexity

Time Complexity: O(n), where n is the number of operations. Each operation is processed once.
Space Complexity: O(n), for storing up to n scores on the stack.

Edge Cases to Consider

Multiple consecutive "C" operations
Using "+" or "D" when stack has fewer than 2 or 1 elements (guaranteed safe by constraints)
Empty operations list → return 0
Only numeric values → return sum of all

Conclusion

The “Baseball Game” problem is an excellent example of stack-based simulation. It helps solidify your understanding of how to use a stack for processing dynamic operations that depend on previously recorded values. This kind of problem frequently appears in interviews for companies that value problem-solving and data structure fluency.

NEW!Need help landing software roles? 💡

AlgoMap.io