Start practising

Baseball Game

Easy Stack Stack Basics Original on LeetCode

Baseball Game is a easy stack problem solved with the stack basics pattern. The best approach, optimal (stack), runs in O(n) time and O(n) space.

Problem

You keep score in a strange game. Each operation is one of:

  • an integer x: record a new score x
  • +: record the sum of the previous two scores
  • D: record double the previous score
  • C: remove the previous score

Return the sum of all scores still on the record after every operation.

Examples

Example 1

Input
ops = ["4", "-1", "C", "3", "D", "+"]
Output
22
Why
Record: [4] → [4,-1] → [4] → [4,3] → [4,3,6] → [4,3,6,9]; total 22.

Example 2

Input
ops = ["7", "C"]
Output
0

Constraints

  • 1 <= ops.length <= 1000
  • Operations are always valid (C, D and + always have enough scores).

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Optimal (stack)O(n)O(n)

1Optimal (stack)

TimeO(n)
SpaceO(n)

Keep the valid scores on a stack. A number is pushed; C pops; D pushes double the top; + pushes the sum of the top two. Sum the stack at the end. There is no meaningfully slower approach; a list used as a stack is the natural model.

  1. For each op, update the stack as described.
  2. Return the sum of the stack.
Java
class Solution {
    public int calPoints(String[] operations) {
        Deque<Integer> st = new ArrayDeque<>();
        for (String op : operations) {
            switch (op) {
                case "C" -> st.pop();
                case "D" -> st.push(2 * st.peek());
                case "+" -> {
                    int top = st.pop();
                    int next = top + st.peek();
                    st.push(top);
                    st.push(next);
                }
                default -> st.push(Integer.parseInt(op));
            }
        }
        int total = 0;
        for (int x : st) total += x;
        return total;
    }
}

Edge cases to test

  • Negative scores
  • Everything cancelled (total 0)

Hints

Hint 1

Every operation looks only at the most recent scores.

FAQ

What is the best time complexity for Baseball Game?

Optimal (stack) runs in O(n) time and O(n) extra space.

Which pattern does Baseball Game use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Asteroid Collision, Min Stack.

Which edge cases should I test for Baseball Game?

Negative scores; Everything cancelled (total 0).