Domain 1EasyCORE

Baseball Game

The problem involves simulating a baseball game where scores are recorded based on specific operations. The input is a list of strings representing operations, and the output is the sum of all valid scores after processing all operations. The operations include: - Recording a new score (an integer). - Doubling the previous score (`D`). - Invalidating the previous score (`C`). - Summing the last two scores (`+`).

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Stack

682. Baseball Game

Model: qwen2.5-coder:14b
Topics: Stack
FAANG asked: 1
Acceptance rate: 67.4%


Problem Breakdown

The problem involves simulating a baseball game where scores are recorded based on specific operations. The input is a list of strings representing operations, and the output is the sum of all valid scores after processing all operations. The operations include:

  • Recording a new score (an integer).
  • Doubling the previous score (D).
  • Invalidating the previous score (C).
  • Summing the last two scores (+).

The constraints ensure that there are always enough previous scores for D and +, and at least one previous score for C.

Intuition

A brute-force approach would involve maintaining a list of scores and processing each operation sequentially. However, this approach could be inefficient in terms of space complexity if the list grows very large.

The key insight is to use a stack data structure to efficiently manage the scores. A stack allows us to easily add, remove, and access the most recent score, which aligns perfectly with the operations required by the problem.

Approach

  1. Initialize a Stack: Use a stack to keep track of valid scores.
  2. Iterate through Operations:
    • If the operation is an integer, convert it to an integer and push it onto the stack.
    • If the operation is "D", pop the top score from the stack, double it, and push the doubled value back onto the stack.
    • If the operation is "C", simply pop the top score from the stack (invalidate it).
    • If the operation is "+", pop the top two scores, sum them, push both popped scores back onto the stack, and then push the sum.
  3. Calculate the Sum: After processing all operations, sum all the values in the stack to get the final result.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of operations. Each operation (push, pop) on a stack takes constant time.
  • Space Complexity: O(n), where n is the number of operations. In the worst case, all operations could be integers, leading to a stack size equal to the number of operations.

Solution

def calPoints(ops):
    stack = []
    
    for op in ops:
        if op == '+':
            # Pop the last two scores, sum them, and push back both scores and their sum
            top1 = stack.pop()
            top2 = stack.pop()
            stack.append(top2)
            stack.append(top1)
            stack.append(top1 + top2)
        elif op == 'D':
            # Double the last score and push it onto the stack
            stack.append(stack[-1] * 2)
        elif op == 'C':
            # Invalidate the last score by popping it from the stack
            stack.pop()
        else:
            # Convert the operation to an integer and push it onto the stack
            stack.append(int(op))
    
    # Return the sum of all scores in the stack
    return sum(stack)

Edge Cases Handled

  • Single Operation: If there’s only one operation, such as ["1"], the code correctly returns 1.
  • Negative Scores: The code handles negative scores by converting them to integers and processing them normally.
  • Mixed Operations: The code processes a mix of integer operations, "D", "C", and "+" correctly, maintaining the order and validity of scores.