Problem Description

You need to calculate the total score of a baseball game that follows special scoring rules. The game starts with an empty score record.

You're given a list of strings called operations, where each operation tells you how to update the score record. There are four types of operations:

1. Integer x: Add a new score of value x to the record
2. '+': Add a new score that equals the sum of the two most recent scores
3. 'D': Add a new score that is double the most recent score
4. 'C': Cancel and remove the most recent score from the record

Your task is to process all operations in order and return the sum of all scores remaining in the record after all operations are applied.

For example, if you have operations ["5", "2", "C", "D", "+"]:

• "5": Record score 5. Record: [5]
• "2": Record score 2. Record: [5, 2]
• "C": Cancel last score. Record: [5]
• "D": Double the last score (5 × 2 = 10). Record: [5, 10]
• "+": Sum of last two scores (5 + 10 = 15). Record: [5, 10, 15]
• Final sum: 5 + 10 + 15 = 30

The problem guarantees that all operations will be valid (you won't get a "+" when there are fewer than two scores, etc.) and all numbers fit within a 32-bit integer range.

Intuition

The key insight is recognizing that we need to maintain a dynamic record of scores where we can:

• Add new scores to the end
• Access the most recent scores (last one or last two)
• Remove the most recent score

These operations naturally point us toward using a stack data structure, since stacks excel at operations involving the "most recent" or "last" elements through their Last-In-First-Out (LIFO) property.

When we think about each operation:

• Adding a number: We simply push it onto the stack
• "+" operation: We need the last two scores, which are at the top of the stack (accessible via stack[-1] and stack[-2])
• "D" operation: We need only the last score to double it (accessible via stack[-1])
• "C" operation: We need to remove the last score, which is exactly what pop() does

The stack perfectly mirrors our score record - the top of the stack is always the most recent score, and we can easily access previous scores by their position from the top. After processing all operations, the stack contains exactly the valid scores we need to sum up.

This approach is intuitive because we're essentially simulating the score-keeping process directly - maintaining a list of scores and modifying it according to the rules, with the stack providing efficient access to the most recent entries that the operations care about.

Learn more about Stack patterns.

Solution Approach

We implement the solution using a stack to simulate the scoring process step by step.

Algorithm Steps:

1. Initialize an empty stack stk to store the scores.

2. Iterate through each operation in the operations list:

   • If operation is "+": Calculate the sum of the top two elements (stk[-1] + stk[-2]) and push the result onto the stack
   • If operation is "D": Double the top element (stk[-1] * 2 or stk[-1] << 1 using bit shift) and push the result onto the stack
   • If operation is "C": Remove the top element using stk.pop()
   • Otherwise (it's a number string): Convert it to an integer using int(op) and push onto the stack

3. After processing all operations, return the sum of all elements in the stack using sum(stk).

Implementation Details:

The solution uses a bit shift operation stk[-1] << 1 to double the value, which is equivalent to multiplying by 2 but can be slightly more efficient. The left shift by 1 position in binary effectively doubles the number.

For accessing previous scores:

• stk[-1] gives us the most recent score (top of stack)
• stk[-2] gives us the second most recent score

The beauty of this approach is its simplicity - we directly simulate what's happening in the game, and the stack naturally maintains the order and allows easy access to recent scores. Each operation takes O(1) time, making the overall time complexity O(n) where n is the number of operations.

Example Walkthrough

Let's trace through a simple example with operations ["5", "-2", "4", "C", "D", "9", "+", "C"]:

Initial state: Stack is empty []

Step 1: Operation = "5" (integer)

• This is a number, so convert to integer and push onto stack
• Stack: [5]

Step 2: Operation = "-2" (integer)

• This is a number, so convert to integer and push onto stack
• Stack: [5, -2]

Step 3: Operation = "4" (integer)

• This is a number, so convert to integer and push onto stack
• Stack: [5, -2, 4]

Step 4: Operation = "C" (cancel)

• Remove the most recent score using pop()
• Stack: [5, -2]

Step 5: Operation = "D" (double)

• Double the most recent score: stk[-1] * 2 = -2 * 2 = -4
• Push -4 onto stack
• Stack: [5, -2, -4]

Step 6: Operation = "9" (integer)

• This is a number, so convert to integer and push onto stack
• Stack: [5, -2, -4, 9]

Step 7: Operation = "+" (sum last two)

• Sum the two most recent scores: stk[-1] + stk[-2] = 9 + (-4) = 5
• Push 5 onto stack
• Stack: [5, -2, -4, 9, 5]

Step 8: Operation = "C" (cancel)

• Remove the most recent score using pop()
• Stack: [5, -2, -4, 9]

Final step: Calculate the sum of all remaining scores

• Sum = 5 + (-2) + (-4) + 9 = 8

The function returns 8.

This walkthrough demonstrates how the stack maintains our score record throughout the game, with the top of the stack always representing the most recent score, making operations like cancel, double, and sum efficient and straightforward.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the operations list.

The algorithm iterates through the operations list exactly once. For each operation:

• "+" operation: Accesses the last two elements and performs addition - O(1)
• "D" operation: Accesses the last element and performs left shift (multiplication by 2) - O(1)
• "C" operation: Removes the last element from the stack - O(1)
• Integer string: Converts string to integer and appends to stack - O(1)

After the loop, sum(stk) iterates through all elements in the stack, which in the worst case contains n elements, taking O(n) time.

Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n), where n is the length of the operations list.

The algorithm uses a stack stk to store integer values. In the worst case, when all operations are integer values (no "C" operations to remove elements), the stack will contain n elements. Even with "+" and "D" operations that add elements based on existing ones, and "C" operations that remove elements, the maximum size of the stack is bounded by n.

Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect String to Integer Conversion

A common mistake is trying to check if an operation is a number using methods like operation.isdigit() or operation.isnumeric(). These methods fail for negative numbers because they don't recognize the minus sign as part of a digit.

Incorrect approach:

if operation.isdigit():  # This fails for negative numbers like "-4"
    score_stack.append(int(operation))

Correct approach: Use try-except or check against known operations:

# Option 1: Check against known operations (recommended)
if operation not in ["+", "D", "C"]:
    score_stack.append(int(operation))

# Option 2: Try-except block
try:
    score_stack.append(int(operation))
except ValueError:
    # Handle special operations
    if operation == "+":
        # ...

2. Not Handling Edge Cases in Early Operations

While the problem guarantees valid operations, developers often write defensive code that checks for edge cases unnecessarily, making the code more complex:

Overly defensive (unnecessary):

if operation == "+":
    if len(score_stack) >= 2:  # Unnecessary check
        score_stack.append(score_stack[-1] + score_stack[-2])

Clean approach (trusting the problem constraints):

if operation == "+":
    score_stack.append(score_stack[-1] + score_stack[-2])

3. Using Wrong Data Structure

Some might use a list and try to track the "current position" with an index instead of using it as a stack, leading to complex index management:

Problematic approach:

scores = []
index = -1
for operation in operations:
    if operation == "C":
        index -= 1  # Wrong! This doesn't remove the element
    # ... complex index tracking

Correct approach: Simply use list methods as stack operations (append/pop).

4. Misunderstanding the "+" Operation

A common misinterpretation is thinking "+" means to add the last score to itself, rather than summing the last two scores:

Wrong interpretation:

if operation == "+":
    score_stack.append(score_stack[-1] * 2)  # Wrong!

Correct interpretation:

if operation == "+":
    score_stack.append(score_stack[-1] + score_stack[-2])