💬 Discord
Sign In
NeetCode #344LC-682EasyStackNC 250
← Back to All Problems

#344 · #682 · Baseball Game(棒球比赛)

📌 Problem Statement & Constraints

You are keeping score for a baseball game with strange rules. Given a list of operations, return the total score. Operations: an integer x records a new score; + records the sum of the previous two scores; D records double the previous score; C invalidates the previous score, removing it. Constraints: 1 <= operations.length <= 1000.

💡 Core Algorithmic Approaches

  1. A stack of valid scores is the natural representation, since C removes the most recent score and +/D depend on the most recent ones.
  2. + pushes stack[-1] + stack[-2]; D pushes 2 * stack[-1]; C pops.
  3. Integer operations push the parsed value.
  4. The answer is the sum of the stack at the end.

💻 Benchmark Python3 Implementation

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        st = []
        for op in operations:
            if op == "+":
                st.append(st[-1] + st[-2])   # sum of the last two
            elif op == "D":
                st.append(2 * st[-1])        # double the last
            elif op == "C":
                st.pop()                     # invalidate the last
            else:
                st.append(int(op))
        return sum(st)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each operation is O(1).
💾 Space Complexity
O(n) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Treating D and C as numbers: they are operation codes, so the string comparison must come first.
  • Using st[-2] without checking the length: the constraints guarantee validity, but defensive code would check len(st) >= 2.
  • Modifying the list while iterating: the stack is separate from the operations list.
  • Forgetting that C removes rather than zeroes: the invalidated score must not contribute to later + or D operations.