Baseball Game - Solution & Explanation

Problem Overview: You are given a list of operations representing a baseball game scoring system. Each operation either records a new score, removes the previous score, doubles the last score, or sums the previous two scores. The task is to simulate these operations and return the final total score.

Approach 1: Stack-Based Simulation (O(n) time, O(n) space)

The most natural way to model the scoring rules is with a stack. Each valid round score is pushed onto the stack. When you see an operation, apply it using the top elements: "C" pops the most recent score, "D" pushes double the top value, and "+" pushes the sum of the top two values. Numeric values are simply converted to integers and pushed onto the stack.

The key insight is that every operation depends only on the most recent scores, which matches the LIFO behavior of a stack. Iterate through the operations once, updating the stack as you go. At the end, sum all values in the stack to get the final result. This approach runs in O(n) time since each operation is processed once, with O(n) space for storing round scores.

Approach 2: In-Place List Manipulation (O(n) time, O(n) space)

A Python list can act as a stack directly, so you can implement the same logic using list operations such as append(), pop(), and index access. The list stores all valid round scores, and operations manipulate the last elements. For example, scores.append(scores[-1] * 2) handles the double operation, while scores.append(scores[-1] + scores[-2]) handles the sum of the last two rounds.

This approach is essentially the same algorithm but expressed using list operations instead of an explicit stack abstraction. It still processes the operations sequentially, making it a classic simulation problem. The time complexity remains O(n), and the list may store up to n scores, giving O(n) space complexity.

Because the operations directly reference recent results, both solutions rely on sequential processing over the input array. No sorting or complex data structures are required.

Recommended for interviews: The stack-based simulation is what interviewers expect. It mirrors the problem statement and clearly demonstrates understanding of stack operations and state tracking. Starting with a straightforward simulation shows you understand the rules, while implementing it with a stack highlights the correct data structure choice and clean O(n) performance.