Baseball Game
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most natural and idiomatic approach for this problem. The operations (+, D, C) all concern the most recently added scores, which follows a Last-In, First-Out (LIFO) principle. A Stack is the perfect data structure for this pattern.
Algorithm
- Initialize an empty
Stack<Integer>(orDeque<Integer>). - Iterate through each
operationin theopsarray. - Handle the
operation:- Case
"+": Pop the top element (last). Peek the new top (prev). Pushlastback. Pushlast + prev. - Case
"D": Peek the top element (last). Push2 * last. - Case
"C": Pop the top element. - Default (number): Parse the string to an integer and push it onto the stack.
- Case
- After the loop, iterate through the stack and sum up all its elements.
- Return the sum.
Walkthrough
We can use a Stack<Integer> to maintain the record of valid scores. We process each operation one by one.
- For a number, we parse it and
pushit onto the stack. - For a
'+', wepopthe top score,peekat the new top, calculate their sum, thenpushthe first score back, and finallypushthe sum. This sequence ensures the stack remains correct for subsequent operations. - For a
'D', wepeekat the top score, double it, andpushthe result onto the stack. - For a
'C', we simplypopthe top score from the stack.
Using a stack makes the code cleaner and more expressive, as the methods (push, pop, peek) directly correspond to the logic of adding, removing, and accessing the most recent score. In modern Java, it's often recommended to use a Deque (like ArrayDeque) as a stack for better performance, as Stack is a legacy synchronized class.
After all operations are processed, we sum up the remaining scores in the stack to get the final result.
import java.util.ArrayDeque;import java.util.Deque; class Solution { public int calPoints(String[] operations) { // ArrayDeque is generally preferred over the legacy Stack class. Deque<Integer> stack = new ArrayDeque<>(); for (String op : operations) { 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(Integer.parseInt(op)); break; } } int sum = 0; for (int score : stack) { sum += score; } return sum; }}Complexity
Time
O(N), where N is the number of operations. Each operation is processed once, and stack operations (`push`, `pop`, `peek`) take constant O(1) time.
Space
O(N). In the worst-case scenario, the stack can grow to hold N scores.
Trade-offs
Pros
Most idiomatic and conceptually clean solution for a LIFO problem.
Code is expressive and easy to read.
Optimal time and space complexity.
Using
ArrayDequeis slightly more performant than the legacyStackclass in single-threaded environments.
Cons
No significant cons; this is the standard and best way to solve this problem.
This approach simulates the record of scores using an ArrayList. However, it uses inefficient methods to mimic stack-like behavior. New scores are added to the beginning of the list, and removals also happen from the beginning. This forces the list to shift all its elements on every such operation, leading to poor performance.
Algorithm
- Initialize an empty
ArrayList<Integer>namedrecord. - Iterate through each
operationin the inputopsarray. - Use a
switchstatement orif-elsechain to handle theoperation:- Case
"+": Calculatesum = record.get(0) + record.get(1)and add it to the front:record.add(0, sum). - Case
"D": Calculatedouble = 2 * record.get(0)and add it to the front:record.add(0, double). - Case
"C": Remove the score at the front:record.remove(0). - Default (number): Parse the string to an integer and add it to the front:
record.add(0, Integer.parseInt(operation)).
- Case
- After the loop, iterate through the final
recordlist and calculate the total sum of its elements. - Return the total sum.
Walkthrough
We can use a Java ArrayList to store the scores. We'll iterate through the operations array and perform actions based on the current operation string.
- For a number, we parse it and add it to the front of the list using
list.add(0, score). - For a
'+', we get the first two elements (list.get(0)andlist.get(1)), sum them, and add the result to the front. - For a
'D', we get the first element, double it, and add the result to the front. - For a
'C', we remove the first element usinglist.remove(0).
Adding or removing from the beginning of an ArrayList requires shifting all subsequent elements, which is an O(k) operation, where k is the current size of the list. Since this is done inside a loop that runs N times, the total time complexity becomes quadratic.
After processing all operations, we sum up the elements remaining in the list to get the final score.
import java.util.ArrayList;import java.util.List; class Solution { public int calPoints(String[] operations) { List<Integer> record = new ArrayList<>(); for (String op : operations) { if (op.equals("+")) { int newScore = record.get(0) + record.get(1); record.add(0, newScore); } else if (op.equals("D")) { int newScore = 2 * record.get(0); record.add(0, newScore); } else if (op.equals("C")) { record.remove(0); } else { record.add(0, Integer.parseInt(op)); } } int sum = 0; for (int score : record) { sum += score; } return sum; }}Complexity
Time
O(N^2), where N is the number of operations. In the worst case, each operation involves adding or removing from the beginning of the `ArrayList`, which takes O(k) time where k is the current size of the list. Since k can be up to N, the total time complexity is quadratic.
Space
O(N), as the `record` list can store up to N scores.
Trade-offs
Pros
Simple to understand the logic.
Uses a common data structure.
Cons
Highly inefficient due to using
add(0, ...)andremove(0)on anArrayList.Will be very slow for large inputs, although the problem constraints (
N <= 1000) might allow it to pass.
This approach also uses an ArrayList to simulate the record, but it does so efficiently. Instead of adding and removing from the beginning, it treats the end of the list as the "top" of the record. This leverages the O(1) amortized time complexity of adding to and removing from the end of an ArrayList.
Algorithm
- Initialize an empty
ArrayList<Integer>namedrecord. - Iterate through each
operationin the inputopsarray. - Use a
switchstatement orif-elsechain:- Case
"+": Get the last two scores:score1 = record.get(record.size() - 1)andscore2 = record.get(record.size() - 2). Append their sum to the list. - Case
"D": Get the last score:score = record.get(record.size() - 1). Append2 * scoreto the list. - Case
"C": Remove the last score:record.remove(record.size() - 1). - Default (number): Parse the string to an integer and append it to the list.
- Case
- After the loop, calculate the sum of all elements in the
record. - Return the sum.
Walkthrough
The core idea is to use an ArrayList as if it were a stack. The "previous" score is always the last element in the list.
- For a number, we parse it and append it to the end of the list using
list.add(score). - For a
'+', we access the last two elements (list.get(list.size() - 1)andlist.get(list.size() - 2)), sum them, and append the result. - For a
'D', we access the last element, double it, and append the result. - For a
'C', we remove the last element usinglist.remove(list.size() - 1).
All these operations that modify the end of an ArrayList are very fast (amortized constant time). This makes the overall algorithm linear in time.
After processing all operations, we sum up the elements in the list.
import java.util.ArrayList;import java.util.List; class Solution { public int calPoints(String[] operations) { List<Integer> record = new ArrayList<>(); for (String op : operations) { int n = record.size(); if (op.equals("+")) { record.add(record.get(n - 1) + record.get(n - 2)); } else if (op.equals("D")) { record.add(2 * record.get(n - 1)); } else if (op.equals("C")) { record.remove(n - 1); } else { record.add(Integer.parseInt(op)); } } int sum = 0; for (int score : record) { sum += score; } return sum; }}Complexity
Time
O(N), where N is the number of operations. We iterate through the operations once. Each operation on the `ArrayList` (add to end, get from end, remove from end) takes O(1) amortized time. The final summation is also linear.
Space
O(N), as the `record` list can store up to N scores.
Trade-offs
Pros
Efficient with linear time complexity.
Still uses a very common and easy-to-understand data structure.
Cons
While efficient, using an
ArrayListas a stack is slightly less idiomatic than using a dedicatedStackorDequeinterface. The coderecord.get(record.size() - 1)is more verbose thanstack.peek().
Solutions
Solution
class Solution {public int calPoints(String[] ops) { Deque<Integer> stk = new ArrayDeque<>(); for (String op : ops) { if ("+".equals(op)) { int a = stk.pop(); int b = stk.peek(); stk.push(a); stk.push(a + b); } else if ("D".equals(op)) { stk.push(stk.peek() << 1); } else if ("C".equals(op)) { stk.pop(); } else { stk.push(Integer.valueOf(op)); } } return stk.stream().mapToInt(Integer : : intValue).sum(); }}class Solution {public: int calPoints(vector<string> &ops) { vector<int> stk; for (auto &op : ops) { int n = stk.size(); if (op == "+") { int a = stk[n - 1]; int b = stk[n - 2]; stk.push_back(a + b); } else if (op == "D") stk.push_back(stk[n - 1] * 2); else if (op == "C") stk.pop_back(); else stk.push_back(stoi(op)); } return accumulate(stk.begin(), stk.end(), 0); }};class Solution: def calPoints(self, ops: List[str]) -> int: stk = [] for op in ops: if op == '+': stk . append(stk[- 1] + stk[- 2]) elif op == 'D': stk . append(stk[- 1] << 1) elif op == 'C': stk . pop() else: stk . append(int(op)) return sum(stk)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.