Skip to main content
Talentd

Baseball Game - Solution & Explanation

EasyArrayStackSimulation16 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.

You are given a list of strings operations, where operations[i] is the ith operation you must apply to the record and is one of the following:

  • An integer x.
    • Record a new score of x.
  • '+'.
    • Record a new score that is the sum of the previous two scores.
  • 'D'.
    • Record a new score that is the double of the previous score.
  • 'C'.
    • Invalidate the previous score, removing it from the record.

Return the sum of all the scores on the record after applying all the operations.

The test cases are generated such that the answer and all intermediate calculations fit in a 32-bit integer and that all operations are valid.

 

Example 1:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

Example 2:

Input: ops = ["5","-2","4","C","D","9","+","+"]
Output: 27
Explanation:
"5" - Add 5 to the record, record is now [5].
"-2" - Add -2 to the record, record is now [5, -2].
"4" - Add 4 to the record, record is now [5, -2, 4].
"C" - Invalidate and remove the previous score, record is now [5, -2].
"D" - Add 2 * -2 = -4 to the record, record is now [5, -2, -4].
"9" - Add 9 to the record, record is now [5, -2, -4, 9].
"+" - Add -4 + 9 = 5 to the record, record is now [5, -2, -4, 9, 5].
"+" - Add 9 + 5 = 14 to the record, record is now [5, -2, -4, 9, 5, 14].
The total sum is 5 + -2 + -4 + 9 + 5 + 14 = 27.

Example 3:

Input: ops = ["1","C"]
Output: 0
Explanation:
"1" - Add 1 to the record, record is now [1].
"C" - Invalidate and remove the previous score, record is now [].
Since the record is empty, the total sum is 0.

 

Constraints:

  • 1 <= operations.length <= 1000
  • operations[i] is "C", "D", "+", or a string representing an integer in the range [-3 * 104, 3 * 104].
  • For operation "+", there will always be at least two previous scores on the record.
  • For operations "C" and "D", there will always be at least one previous score on the record.

Approach Overview

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.

Approach 1: Stack-Based Solution

This approach involves using a stack (or list) to simulate the score record. Each operation determines how you transform the record:

  • If the operation is a number, push it onto the stack.
  • If it is "+", push the sum of the last two elements. Ensure there are at least two elements in the stack beforehand.
  • If it is "D", push the double of the last element. Ensure there's at least one element in the stack beforehand.
  • If it is "C", pop the last element from the stack.

After processing all operations, sum up the stack to get the total score.

We used a list to implement a stack to record scores based on the operations. We iterate over each operation and update the stack accordingly. Finally, we return the sum of elements in the stack.

Code

PythonJavaScriptC++CJavaC#

Python

JavaScript

C++

C

Java

C#

Complexity

Time Complexity: O(n), where n is the number of operations.
Space Complexity: O(n), for the storage of scores in the stack.

Try this approach in the editor →

Approach 2: In-Place List Manipulation

This approach leverages in-place list manipulation without using any explicit stack. Use a low-level list operation to track the scores and operations similar to calcualtions within the same list. Ideal for scripting languages that optimize list operations.

Instead of a designated stack, the list itself is used to apply operations which may concatenate new scores or remove past ones. The final sum is the sum of list elements.

Code

Python

Python

Complexity

Time Complexity: O(n).
Space Complexity: O(n) due to maintaining result list as stack.

Try this approach in the editor →

Approach 3: Stack + Simulation

We can use a stack to simulate this process.

Traverse operations, for each operation:

  • If it is +, add the top two elements of the stack and push the result onto the stack;
  • If it is D, multiply the top element of the stack by 2 and push the result onto the stack;
  • If it is C, pop the top element of the stack;
  • If it is a number, push the number onto the stack.

Finally, sum all the elements in the stack to get the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of operations.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Stack-Based Solution

Time Complexity: O(n), where n is the number of operations.
Space Complexity: O(n), for the storage of scores in the stack.

In-Place List Manipulation

Time Complexity: O(n).
Space Complexity: O(n) due to maintaining result list as stack.

Stack + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-Based SimulationO(n)O(n)General case. Best when operations depend on the most recent values and stack semantics match the problem rules.
In-Place List ManipulationO(n)O(n)Python-specific implementation where a list is used directly as a stack for concise code.

Video Solution

Baseball Game - Leetcode 682 - Python • NeetCode • 47,538 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Baseball Game easy or hard?
Baseball Game is categorized as an Easy problem. The challenge mainly involves correctly simulating operations and choosing a stack to manage previous scores. Developers comfortable with basic array traversal and stack operations can usually solve it quickly.
Baseball Game Python/Java solution
In Python, a list is typically used as a stack with append() and pop() operations. In Java, developers commonly use a Stack or ArrayDeque to store scores. Both implementations follow the same O(n) simulation logic and maintain previous round results for future operations.
How to solve Baseball Game in O(n)?
Iterate through the operations array once and maintain a stack of valid round scores. Push numbers directly, pop the last score for "C", push double the last score for "D", and push the sum of the last two scores for "+". After processing all operations, sum the stack values to get the final score.
What is the best approach for Baseball Game?
The best approach is a stack-based simulation. Each valid round score is pushed onto a stack, while operations like "C", "D", and "+" manipulate the most recent scores. This matches the problem's rule that operations depend on the latest rounds. The solution runs in O(n) time with O(n) space.
Is Baseball Game asked at Google/Amazon/Meta?
Baseball Game is commonly used in coding interviews at companies that test fundamental data structure knowledge. It appears frequently in interview prep lists and practice platforms because it evaluates stack usage, array iteration, and simulation skills.
What data structure is used in Baseball Game?
A stack is the primary data structure used to track previous round scores. The stack allows efficient access to the most recent values, which is required for operations like removing the last score, doubling it, or summing the last two scores.
What is the time complexity of Baseball Game?
The optimal solution runs in O(n) time where n is the number of operations. Each operation is processed exactly once, and stack operations such as push, pop, and top access take constant time. The space complexity is O(n) because previous scores are stored for later operations.

Ready to solve this problem?

Practice Baseball Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Crawler Log Folder