Baseball Game
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.
Every operation works on the most recent end of the record: "D" and "C" need the last score, and "+" needs the last two. This last-in, first-out access pattern is what a stack provides. Every operation either pushes a value onto the stack or pops one off.
Key Constraints:
1 <= operations.length <= 1000→ Small input, so performance is not a concern. A single pass over the operations runs in O(n).- 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
A stack matches each operation directly. A number is a push. "D" is a peek followed by a push of double that value. "+" is a look at the top two elements followed by a push of their sum. "C" is a pop. No operation ever reads or modifies the middle of the record, so push, pop, and peek (all O(1)) cover everything, and the stack contents at the end are the valid scores to sum.
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
Tracing ops = ["5", "-2", "4", "C", "D", "9", "+", "+"] (Example 2). The expected output is 27.
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.
The stack can also be implemented as a fixed-size array of length n plus an index pointer, where incrementing the pointer is a push and decrementing it is a pop. The operations and complexity are identical, so that variant is an implementation detail rather than a different algorithm.