Skip to main content

682. Baseball Game

easy

Process a list of scoring operations on a stack — push, double-the-previous, sum-the-last-two, undo. The cleanest 'stack as a running record' problem in the catalog.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 that you must apply. An integer x represents a new score x for this round. '+' records a new score that is the sum of the previous two scores. 'D' records a new score that is the double of the previous score. 'C' invalidates the previous score, removing it from the record. Return the sum of all the scores on the record after applying all the operations.

Constraints

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

Examples

Example 1

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

Explanation: Stack evolves: [5] -> [5,2] -> [5] (C) -> [5,10] (D) -> [5,10,15] (+). Sum = 30.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Use a stack of integers. Each operation is O(1) on the stack.

Hint 2

Integer string -> push the parsed value. '+' -> push stack[-1] + stack[-2]. 'D' -> push 2 * stack[-1]. 'C' -> pop.

Hint 3

After processing all operations, sum the remaining stack.

Hint 4

Edge case: negative integers. Don't assume non-negative when parsing.

Solution approach

Reveal approach

Linear scan with a stack of integers. For each op: if op == '+', push stack[-1] + stack[-2]. If op == 'D', push 2 * stack[-1]. If op == 'C', pop the top. Otherwise (integer string), parse and push. Sum the stack at the end and return. Each operation touches only the top one or two elements, so O(n) time and O(n) space where n = operations.length. The teaching point: any time you have an operation that depends on 'the most recent valid items', a stack is the right data structure — pushes and pops keep the invariant 'top = current latest score' without any indexing gymnastics.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • simulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Google

Practice these live with InterviewChamp.AI

Drill Baseball Game and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →