Baseball Game
Last Updated: March 29, 2026
Understanding the Problem
We are simulating a scoring system where we process a sequence of operations one by one. Some operations add a numeric score, some compute a new score based on previous ones, and one operation removes the most recent score. At the end, we return the total of all remaining scores.
The key observation here is that we always need access to the most recent score (for "D" and "C") and the two most recent scores (for "+"). This "last in, first out" access pattern is a textbook fit for a stack. Every operation either pushes a value onto the stack or pops one off.
Key Constraints:
1 <= operations.length <= 1000→ With n up to 1000, even an O(n^2) approach would be fine. But this problem naturally solves in O(n) with a single pass.- Values fit in a 32-bit integer → No need for long or BigInteger handling. Standard int works.
- Operations are guaranteed valid → We don't need to handle error cases like "C" on an empty record.
Approach 1: Stack Simulation
Intuition
Every operation revolves around the most recent elements. A number gets added on top. "D" needs the most recent score. "+" needs the two most recent scores. "C" removes the most recent score. That is a stack. We push scores on, pop them off for "C", and peek at the top for "D" and "+". There is no need for random access into the middle of our record, so a stack is the perfect fit.
This is one of those problems where picking the right data structure makes everything fall into place. Once you see "most recent" and "remove most recent," the stack choice is almost automatic.
The stack perfectly mirrors the problem's scoring record. Every time we add a score, it goes on top. Every time we invalidate ("C"), we remove from the top. The "D" and "+" operations only ever look at the top one or two elements. The stack preserves the order of scores and gives us O(1) access to exactly the elements we need.
Algorithm
- Initialize an empty stack to hold the record of scores.
- Iterate through each operation in the input array.
- If the operation is "C", pop the top element from the stack (removing the last score).
- If the operation is "D", peek at the top element and push its double onto the stack.
- If the operation is "+", peek at the top two elements and push their sum onto the stack.
- Otherwise, the operation is a number. Parse it and push it onto the stack.
- After processing all operations, sum up all elements remaining in the stack and return the total.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through each of the n operations exactly once. Each operation (push, pop, peek, parse) takes O(1) time. The final summation iterates through the stack, which has at most n elements.
- Space Complexity: O(n). In the worst case (no "C" operations), every operation adds a score to the stack, so the stack holds up to n elements.
Since we are already at O(n) time and O(n) space, there is no asymptotic improvement possible. But we can implement the same logic using a plain array and a pointer instead of a stack class.
Approach 2: Array-Based Simulation
Intuition
Since we know the maximum number of operations is 1000, we can simulate this using a plain array and an index pointer. Instead of push/pop, we just move an index forward or backward. This avoids any overhead from dynamic resizing or stack class methods.
The idea is identical to Approach 1. We are just using a fixed-size array and a top pointer instead of a stack object. Incrementing top is a push, decrementing it is a pop, and record[top] is a peek.
Algorithm
- Create an integer array of size equal to the number of operations (worst case, every operation is a number).
- Maintain an index
topstarting at -1 (empty record). - For each operation:
- "C": decrement
topby 1 (logically removes the last score). - "D": increment
top, setarr[top] = 2 * arr[top - 1]. - "+": increment
top, setarr[top] = arr[top - 1] + arr[top - 2]. - Number: increment
top, setarr[top] = parsed number. - Sum all elements from index 0 to
topand return.
Example Walkthrough
Code
- Time Complexity: O(n). One pass through operations, O(1) per operation, O(n) for the final sum.
- Space Complexity: O(n). We allocate an array of size n upfront. In practice, the used portion may be smaller if "C" operations remove elements, but the allocation is still O(n).