Baseball Game

NeetCode: Baseball Game · LeetCode: 682. Baseball Game · Difficulty: Easy

Keep the score of a game from a list of strings operations, starting with an empty record. Each operation is one of:

an integer x: record a new score of x;
"+": record a new score equal to the sum of the previous two scores;
"D": record a new score equal to double the previous score;
"C": remove the previous score from the record.

Return the sum of all scores in the record at the end. Every operation is valid, so "+" always has two previous scores and "D" and "C" always have one.

Example

Text

Input:  ["5", "2", "C", "D", "+"]                        Output: 30
Input:  ["5", "-2", "4", "C", "D", "9", "+", "+"]        Output: 27

Trace of the first example: record [5], [5, 2], C gives [5], D gives [5, 10], + gives [5, 10, 15], and the sum is 30.

Brute force: keep the record as a stack, sum at the end

The record behaves exactly like a stack: new scores are pushed, C pops, and + and D only look at the top one or two entries. Apply every operation, then add up whatever is left. This is already linear. The record is an ArrayDeque<Integer>: push and pop work on the top, and peek reads the top without removing it. + needs the second entry, so it pops the top, reads the next one with peek, and pushes the top back. Integer.parseInt converts a score string such as "-2" to an int.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int calPoints(String[] operations) {
        Deque<Integer> record = new ArrayDeque<>();
        for (String op : operations) {
            switch (op) {
                case "+": {
                    int last = record.pop();
                    int sum = last + record.peek();
                    record.push(last);
                    record.push(sum);
                    break;
                }
                case "D":
                    record.push(2 * record.peek());
                    break;
                case "C":
                    record.pop();
                    break;
                default:
                    record.push(Integer.parseInt(op));
            }
        }
        int total = 0;
        for (int score : record) {
            total += score;
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.calPoints(new String[]{"5", "2", "C", "D", "+"}));
        System.out.println(s.calPoints(new String[]{"5", "-2", "4", "C", "D", "9", "+", "+"}));
        System.out.println(s.calPoints(new String[]{}));
        System.out.println(s.calPoints(new String[]{"7", "C"}));
    }
}

Output

Time: O(n). Space: O(n).

Optimal: stack plus a running total

Keep the same stack, but also maintain the total. When a score is pushed, add it to the total; when C pops a score, subtract it. The answer is then available without a final pass. The stack is still required because later operations read the previous entries. Here C pops and subtracts, so the total always equals the sum of the stack.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int calPoints(String[] operations) {
        Deque<Integer> stack = new ArrayDeque<>();
        int total = 0;
        for (String op : operations) {
            switch (op) {
                case "C":
                    total -= stack.pop();
                    break;
                case "D": {
                    int x = 2 * stack.peek();
                    stack.push(x);
                    total += x;
                    break;
                }
                case "+": {
                    int last = stack.pop();
                    int x = last + stack.peek();
                    stack.push(last);
                    stack.push(x);
                    total += x;
                    break;
                }
                default: {
                    int x = Integer.parseInt(op);
                    stack.push(x);
                    total += x;
                }
            }
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.calPoints(new String[]{"5", "2", "C", "D", "+"}));
        System.out.println(s.calPoints(new String[]{"5", "-2", "4", "C", "D", "9", "+", "+"}));
        System.out.println(s.calPoints(new String[]{}));
        System.out.println(s.calPoints(new String[]{"7", "C"}));
    }
}

Output

Time: O(n). Space: O(n) for the stack.

Scores can double repeatedly, and int arithmetic wraps silently on overflow. The solution keeps int because the LeetCode signature returns int; a record whose values exceed the int range would need long for the stack and the total. The operations are guaranteed valid, so pop and peek never find an empty stack (on an empty ArrayDeque, pop throws NoSuchElementException and peek returns null).