Baseball Game solution and explanation
Google
9 more videos on this problem
Baseball Game - Leetcode 682 - PythonNeetCode · 7:02 · 47K views
Baseball Game - Leetcode 682 - Stacks (Python)Greg Hogg · 5:18 · 13K views
Leetcode - Baseball Game (Python)Timothy H Chang · 3:20 · 1K views
682. Baseball Game (Leetcode Easy)Programming Live with Larry · 16:01 · 1K views
Baseball Game | Stack🔥🔥| C++ | LeetCode 682Gantavya Malviya · 8:02 · 970 views
LeetCode 682. Baseball Game in Java (Stack-Based Solution)LeetCode LevelUp · 16:33 · 507 views
682. Baseball Game | Leetcode Daily Challenge | Easy level problemVishal Rajput · 8:22 · 306 views
44. Leetcode 682. Baseball Game : JAVAWeb Fusion with Bharadwaj · 17:42 · 300 views
⚾ LeetCode 682 – Baseball Game 🧠 | Java DSA Series 🚀 Day 6 | Stack Problem Explained Step-by-Step 💻CodeWithMadhav · 7:49 · 279 views
Leetcode 682 - Baseball GameShafik Quoraishee · 12:03 · 264 views
The problem
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 of
'+'.- 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 <= 1000operations[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.
def calPoints(ops):
stack = []
for op in ops:
if op == '+':
stack.append(stack[-1] + stack[-2])
elif op == 'D':
stack.append(2 * stack[-1])
elif op == 'C':
stack.pop()
else:
stack.append(int(op))
return sum(stack)import java.util.Stack;
public class BaseballGame {
public int calPoints(String[] ops) {
Stack<Integer> stack = new Stack<>();
for (String op : ops) {
if (op.equals("+")) {
int top = stack.pop();
int newTop = top + stack.peek();
stack.push(top);
stack.push(newTop);
} else if (op.equals("D")) {
stack.push(2 * stack.peek());
} else if (op.equals("C")) {
stack.pop();
} else {
stack.push(Integer.parseInt(op));
}
}
int sum = 0;
for (int score : stack) {
sum += score;
}
return sum;
}
}#include <vector>
#include <string>
#include <numeric>
int calPoints(std::vector<std::string>& ops) {
std::vector<int> stack;
for (const auto& op : ops) {
if (op == "+") {
stack.push_back(stack.back() + stack[stack.size() - 2]);
} else if (op == "D") {
stack.push_back(2 * stack.back());
} else if (op == "C") {
stack.pop_back();
} else {
stack.push_back(std::stoi(op));
}
}
return std::accumulate(stack.begin(), stack.end(), 0);
}function calPoints(ops) {
let stack = [];
for (let op of ops) {
if (op === '+') {
stack.push(stack[stack.length - 1] + stack[stack.length - 2]);
} else if (op === 'D') {
stack.push(2 * stack[stack.length - 1]);
} else if (op === 'C') {
stack.pop();
} else {
stack.push(parseInt(op));
}
}
return stack.reduce((a, b) => a + b, 0);
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int calPoints(char** ops, int opsSize) {
int stack[1000];
int top = -1;
for (int i = 0; i < opsSize; i++) {
if (strcmp(ops[i], "+") == 0) {
stack[++top] = stack[top] + stack[top - 1];
} else if (strcmp(ops[i], "D") == 0) {
stack[++top] = 2 * stack[top];
} else if (strcmp(ops[i], "C") == 0) {
top--;
} else {
stack[++top] = atoi(ops[i]);
}
}
int sum = 0;
for (int i = 0; i <= top; i++) {
sum += stack[i];
}
return sum;
}using System;
using System.Collections.Generic;
public class Solution {
public int CalPoints(string[] ops) {
Stack<int> stack = new Stack<int>();
foreach (string op in ops) {
switch (op) {
case "+":
int top = stack.Pop();
int newTop = top + stack.Peek();
stack.Push(top);
stack.Push(newTop);
break;
case "D":
stack.Push(2 * stack.Peek());
break;
case "C":
stack.Pop();
break;
default:
stack.Push(Int32.Parse(op));
break;
}
}
int sum = 0;
foreach (int score in stack) {
sum += score;
}
return sum;
}
}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.
Time Complexity: O(n), where n is the number of operations.
Space Complexity: O(n), for the storage of scores in the stack.
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.
def calPoints(ops):
record = []
for op in ops:
if op == '+':
record.append(record[-1] + record[-2])
elif op == 'D':
record.append(2 * record[-1])
elif op == 'C':
record.pop()
else:
record.append(int(op))
return sum(record)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.
Time Complexity: O(n).
Space Complexity: O(n) due to maintaining result list as stack.
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.
function calPoints(operations: string[]): number {
const stk: number[] = [];
for (const op of operations) {
if (op === '+') {
stk.push(stk.at(-1)! + stk.at(-2)!);
} else if (op === 'D') {
stk.push(stk.at(-1)! << 1);
} else if (op === 'C') {
stk.pop();
} else {
stk.push(+op);
}
}
return stk.reduce((a, b) => a + b, 0);
}func calPoints(operations []string) (ans int) {
var stk []int
for _, op := range operations {
n := len(stk)
switch op {
case "+":
stk = append(stk, stk[n-1]+stk[n-2])
case "D":
stk = append(stk, stk[n-1]*2)
case "C":
stk = stk[:n-1]
default:
num, _ := strconv.Atoi(op)
stk = append(stk, num)
}
}
for _, x := range stk {
ans += x
}
return
}impl Solution {
pub fn cal_points(operations: Vec<String>) -> i32 {
let mut stk = vec![];
for op in operations {
match op.as_str() {
"+" => {
let n = stk.len();
stk.push(stk[n - 1] + stk[n - 2]);
}
"D" => {
stk.push(stk.last().unwrap() * 2);
}
"C" => {
stk.pop();
}
n => {
stk.push(n.parse::<i32>().unwrap());
}
}
}
stk.into_iter().sum()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Stack-Based Solution | Time Complexity: O(n), where n is the number of operations. |
| In-Place List Manipulation | Time Complexity: O(n). |
| Stack + Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Simulation | O(n) | O(n) | General case. Best when operations depend on the most recent values and stack semantics match the problem rules. |
| In-Place List Manipulation | O(n) | O(n) | Python-specific implementation where a list is used directly as a stack for concise code. |
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.