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.
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(); }}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.