LeetCode 682 - Baseball Game
This problem asks us to simulate a baseball scoring system with a set of unusual rules. We begin with an empty score record and process a sequence of operations one by one. Each operation either adds a new score or modifies the history of previously recorded scores.
Difficulty: 🟢 Easy
Topics: Array, Stack, Simulation
Solution
Problem Understanding
This problem asks us to simulate a baseball scoring system with a set of unusual rules. We begin with an empty score record and process a sequence of operations one by one. Each operation either adds a new score or modifies the history of previously recorded scores.
The input is an array of strings called operations. Each string represents an action to perform. There are four possible operation types:
- A numeric string such as
"5"or"-2"means we record a new score with that value. "+"means we create a new score equal to the sum of the previous two valid scores."D"means we create a new score equal to double the previous valid score."C"means we invalidate and remove the previous valid score.
The important detail is that every operation affects the current record of valid scores. Future operations depend on this evolving history. For example, when we see "+", we do not sum the last two input operations, we sum the last two valid scores currently in the record.
At the end, we return the total sum of all valid scores remaining in the record.
The constraints tell us that operations.length can be at most 1000, which is relatively small. This means even moderately inefficient approaches would still run comfortably within limits. However, the problem is fundamentally about maintaining dynamic history, so choosing the right data structure makes the implementation clean and intuitive.
The problem also guarantees that all operations are valid. This means:
"+"always has at least two previous valid scores."D"and"C"always have at least one previous valid score.- Intermediate results fit within a 32-bit integer.
These guarantees simplify the implementation because we do not need defensive checks for invalid operations or empty history.
There are several edge cases worth thinking about upfront. A record may become empty after a "C" operation, such as ["1", "C"]. Negative numbers can appear and should be handled correctly, especially with "D" and "+". Multiple consecutive special operations such as "D" followed by "+" can create dependencies on newly added values, so we must always work with the latest valid state.
Approaches
Brute Force Approach
A straightforward way to solve this problem is to repeatedly reconstruct the current score record whenever an operation depends on previous scores.
For example, after each operation, we could recalculate the entire sum of scores or repeatedly traverse the list to determine the last valid entries. If we use a basic array and recompute information from scratch whenever we encounter "+", "D", or "C", we still obtain the correct result because we are faithfully simulating the rules.
This approach works because every operation only depends on previously processed operations, and recomputing the state guarantees correctness. However, repeatedly recalculating totals or traversing history introduces unnecessary repeated work.
For example, if after every insertion or deletion we recompute the sum of the entire record, the total runtime becomes quadratic in the worst case.
Key Insight for an Optimal Solution
The key observation is that this problem naturally behaves like a stack.
We only ever interact with the most recent valid scores:
"C"removes the most recent score."D"uses the most recent score."+"uses the two most recent scores.
This last-in, first-out behavior matches a stack perfectly.
We maintain a stack of valid scores. As we process each operation:
- Numbers are pushed onto the stack.
"C"pops the top value."D"pushes twice the top value."+"pushes the sum of the top two values.
At the end, we sum the stack.
This avoids recomputation and processes every operation in constant time.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeatedly recalculates score state or totals |
| Optimal | O(n) | O(n) | Uses a stack to efficiently maintain score history |
Algorithm Walkthrough
- Initialize an empty stack to store valid scores.
The stack represents the current score record. Since all special operations only depend on recent values, this data structure provides efficient access.
2. Iterate through each operation in operations.
We process operations sequentially because each one depends on the current state created by earlier operations.
3. If the operation is "C", remove the most recent score.
We pop the top value from the stack because "C" invalidates the last valid score.
4. If the operation is "D", double the previous score.
We look at the top element of the stack, multiply it by 2, and push the result back onto the stack.
5. If the operation is "+", sum the previous two scores.
We access the last two elements in the stack, add them together, and push the result. 6. Otherwise, treat the operation as an integer.
Convert the string into an integer and push it onto the stack. 7. After processing all operations, return the sum of the stack.
The stack contains exactly the valid scores that remain in the record.
Why it works
The core invariant is that after processing each operation, the stack exactly matches the valid score record defined by the problem statement.
Each operation preserves this invariant:
- Numeric values correctly append a new score.
"C"correctly removes the latest score."D"correctly derives a score from the latest valid score."+"correctly derives a score from the latest two valid scores.
Because the invariant holds after every step, the final stack represents the correct score history, and summing it produces the correct answer.
Python Solution
from typing import List
class Solution:
def calPoints(self, operations: List[str]) -> int:
scores = []
for operation in operations:
if operation == "C":
scores.pop()
elif operation == "D":
scores.append(scores[-1] * 2)
elif operation == "+":
scores.append(scores[-1] + scores[-2])
else:
scores.append(int(operation))
return sum(scores)
The implementation follows the stack-based algorithm directly.
We begin by creating an empty list called scores, which acts as a stack. Python lists provide efficient append and pop operations from the end, making them a natural choice.
Inside the loop, we inspect each operation. For "C", we call pop() to remove the most recent score. For "D", we read the last score using scores[-1], double it, and append the result. For "+", we access the last two elements using negative indexing and append their sum.
If the operation is not a special symbol, it must be a numeric string. We convert it to an integer using int() and append it to the stack.
After all operations are processed, scores contains the final valid record, so we simply return sum(scores).
Go Solution
func calPoints(operations []string) int {
scores := []int{}
for _, operation := range operations {
switch operation {
case "C":
scores = scores[:len(scores)-1]
case "D":
scores = append(scores, scores[len(scores)-1]*2)
case "+":
n := len(scores)
scores = append(scores, scores[n-1]+scores[n-2])
default:
var value int
fmt.Sscanf(operation, "%d", &value)
scores = append(scores, value)
}
}
total := 0
for _, score := range scores {
total += score
}
return total
}
The Go solution follows the same logic but uses slices instead of Python lists. The scores slice acts as the stack.
To remove the last score for "C", we reslice using scores[:len(scores)-1]. For "D" and "+", we access recent elements through indexing.
One Go-specific detail is integer parsing. Here we use fmt.Sscanf() to convert string values into integers. Alternatively, strconv.Atoi() could also be used. Since the problem guarantees valid inputs, error handling is unnecessary in practice.
Go slices dynamically resize as needed, so we can safely append new scores throughout execution.
Worked Examples
Example 1
Input:
["5","2","C","D","+"]
| Step | Operation | Action | Stack |
|---|---|---|---|
| 1 | "5" |
Add 5 | [5] |
| 2 | "2" |
Add 2 | [5, 2] |
| 3 | "C" |
Remove last score | [5] |
| 4 | "D" |
Add 5 × 2 = 10 |
[5, 10] |
| 5 | "+" |
Add 5 + 10 = 15 |
[5, 10, 15] |
Final sum:
5 + 10 + 15 = 30
Example 2
Input:
["5","-2","4","C","D","9","+","+"]
| Step | Operation | Action | Stack |
|---|---|---|---|
| 1 | "5" |
Add 5 | [5] |
| 2 | "-2" |
Add -2 | [5, -2] |
| 3 | "4" |
Add 4 | [5, -2, 4] |
| 4 | "C" |
Remove 4 | [5, -2] |
| 5 | "D" |
Add -2 × 2 = -4 |
[5, -2, -4] |
| 6 | "9" |
Add 9 | [5, -2, -4, 9] |
| 7 | "+" |
Add -4 + 9 = 5 |
[5, -2, -4, 9, 5] |
| 8 | "+" |
Add 9 + 5 = 14 |
[5, -2, -4, 9, 5, 14] |
Final sum:
5 + (-2) + (-4) + 9 + 5 + 14 = 27
Example 3
Input:
["1","C"]
| Step | Operation | Action | Stack |
|---|---|---|---|
| 1 | "1" |
Add 1 | [1] |
| 2 | "C" |
Remove 1 | [] |
Final sum:
0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each operation is processed exactly once |
| Space | O(n) | The stack may store all scores |
The runtime is linear because every operation results in a constant amount of work. Stack operations such as append, pop, and indexing are all constant time.
The space complexity is linear in the worst case because every operation may add a score to the stack, such as when all operations are integers.
Test Cases
sol = Solution()
assert sol.calPoints(["5", "2", "C", "D", "+"]) == 30 # Example 1
assert sol.calPoints(["5", "-2", "4", "C", "D", "9", "+", "+"]) == 27 # Example 2
assert sol.calPoints(["1", "C"]) == 0 # Example 3
assert sol.calPoints(["10"]) == 10 # Single score only
assert sol.calPoints(["3", "D"]) == 9 # Double previous score
assert sol.calPoints(["1", "2", "+"]) == 6 # Sum of last two scores
assert sol.calPoints(["5", "C"]) == 0 # Remove only score
assert sol.calPoints(["-5", "D"]) == -15 # Negative number doubling
assert sol.calPoints(["1", "2", "3", "C"]) == 3 # Remove latest score
assert sol.calPoints(["1", "2", "+", "D"]) == 9 # Chained special operations
assert sol.calPoints(["1000"] * 1000) == 1000000 # Maximum input size stress test
| Test | Why |
|---|---|
["5","2","C","D","+"] |
Validates the first example |
["5","-2","4","C","D","9","+","+"] |
Tests mixed operations and negatives |
["1","C"] |
Ensures empty record handling |
["10"] |
Smallest non-empty valid case |
["3","D"] |
Verifies doubling logic |
["1","2","+"] |
Verifies summing last two scores |
["5","C"] |
Ensures removal works correctly |
["-5","D"] |
Validates negative score handling |
["1","2","3","C"] |
Tests invalidation of latest entry |
["1","2","+","D"] |
Verifies chained dependencies |
1000 repeated scores |
Stress test for maximum input size |
Edge Cases
Record Becomes Empty
A case like ["1", "C"] removes the only score from the record, leaving an empty stack. A naive implementation might accidentally access a removed value or fail when computing the final sum. Our implementation handles this correctly because pop() removes the element cleanly, and sum([]) correctly evaluates to 0.
Negative Numbers
Scores can be negative, such as ["-2", "D"]. A careless implementation might assume all scores are positive or mishandle string conversion. Since we explicitly convert numeric strings with int(), negative values are parsed naturally, and doubling preserves the correct sign.
Chained Special Operations
Cases like ["1", "2", "+", "D"] are easy to get wrong because special operations depend on values that were themselves recently generated. The stack-based approach always works from the latest valid state, ensuring newly created scores immediately become available for future operations.
Consecutive Invalidations
An input such as ["5", "3", "C", "C"] repeatedly removes recent values. Some implementations accidentally remove the wrong element or lose track of history. Because the stack always stores the exact valid sequence of scores, consecutive pop() operations naturally maintain correctness.