How do you approach Baseball Game?

Every operation only looks at or removes the most recent score(s) - which structure gives you that cheaply?

What is the time complexity of Baseball Game?

Time complexity: O(n) - each operation does O(1) stack work. Space complexity: O(n) for the record stack.

What are common mistakes on Baseball Game?

Popping without first checking the stack is non-empty. Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer. Pushing values where the problem needs indices back.

gitGood.dev

← Back to problems

Baseball Game

EasyData Structures

Description

You are keeping the scores for a baseball game with strange rules. You begin with an empty record, and you are given a list of operations operations to apply, where operations[i] is one of:

An integer x (as a string): record a new score of x.
"+": record a new score that is the sum of the previous two scores.
"D": record a new score that is double 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. All operations are guaranteed to be valid at the moment they are applied.

Example 1

Input: operations = ["5","2","C","D","+"]

Output: 30

Explanation: "5" -> [5]. "2" -> [5,2]. "C" -> [5]. "D" -> [5,10]. "+" -> [5,10,15]. Total = 30.

Example 2

Input: operations = ["5","-2","4","C","D","9","+","+"]

Output: 27

Example 3

Input: operations = ["1","C"]

Output: 0

Explanation: The record is empty, so the total is 0.

Constraints

- 1 <= operations.length <= 1000 - operations[i] is "C", "D", "+", or a string representing an integer in the range [-3 * 10^4, 3 * 10^4]. - For "+" there will always be at least two previous scores on the record. - For "C" and "D" there will always be at least one previous score on the record.

Baseball Game: approach, complexity and pitfalls

An easy stack problem, graded against 7 test cases (4 of them hidden).

The pattern: Stack

Last-in-first-out processing - matching, nesting, and deferred evaluation.

Reach for it when you see: Balanced brackets, nested structures, undo/back semantics, or expression evaluation.

If you are stuck

Show the 3-step hint ladder

Every operation only looks at or removes the most recent score(s) - which structure gives you that cheaply?
Maintain a stack of valid scores; '+' peeks at the top two, 'D' peeks at the top, 'C' pops.
After processing all operations, the answer is just the sum of what's left on the stack.

The optimal approach

Show the approach: Stack

Every rule operates on the most recent scores, so keep a stack of valid scores: push integers, push `top + second` for `"+"`, push `2 * top` for `"D"`, and pop for `"C"`. The answer is the sum of the remaining stack.

Time: O(n) - each operation does O(1) stack work
Space: O(n) for the record stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Stack mistakes

These apply to the pattern as a whole, not just this problem.

Popping without first checking the stack is non-empty.
Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer.
Pushing values where the problem needs indices back.