#682

Easy

auto_awesomeStack-based state management

LeetCode Problem Workspace

Baseball Game

Simulate baseball score operations using a stack-based approach to compute the final score after all operations.

Problem Statement

In this problem, you're tasked with simulating the score management of a baseball game. You start with an empty score record. The operations you apply to this record will modify the scores in different ways, and your goal is to compute the final sum of the scores after applying all the operations.

You are given a list of operations, where each operation can either be a numeric value, a command to remove the last score ('C'), double the last score ('D'), or sum the last two scores ('+'). Apply these operations in sequence and return the final total of the scores in the record.

Examples

Example 1

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

Output: 30

"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

"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

"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 <= 1000
operations[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.

Solution Approach

Use a Stack for State Management

We can use a stack to track the scores, as the operations either add new scores, remove the last one, or perform calculations based on the last scores. Pushing, popping, and peeking the stack will allow us to simulate the operations efficiently.

Handle Operations Sequentially

Iterate through the operations list. For each operation, determine if it's a number (which gets pushed onto the stack), a 'C' (remove the last score), a 'D' (duplicate the last score), or a '+' (sum the last two scores). Carefully apply the changes to the stack as per the operation.

Optimize Space Usage

Since we only need to store the current record of scores in a stack, the space complexity is O(N), where N is the number of operations. There's no need for extra data structures, and the problem can be solved with minimal memory usage.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The time complexity of this solution is O(N) because we process each operation once. For each operation, we either push a score, pop the last score, or perform constant-time operations (like duplicating or summing). The space complexity is also O(N), as we need to store up to N scores in the stack at any point.

What Interviewers Usually Probe

Candidate demonstrates understanding of stack-based state management.
Candidate effectively handles the various operations and edge cases (e.g., invalidations, empty stack).
Candidate explains the space complexity and how it relates to the number of operations.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the behavior of the '+' operation, which requires at least two previous scores.
Failing to properly handle the 'C' operation when the stack is empty.
Overcomplicating the space or time complexity when the solution is straightforward with a stack.

Follow-up variants

Changing the number of operations or limiting the types of operations.
Allowing negative or very large numbers in the score list.
Handling a larger range of invalidation rules, such as invalidating multiple previous scores at once.

FAQ

How do I handle the '+' operation in the Baseball Game problem?

The '+' operation requires you to sum the last two scores in the stack. Ensure that there are at least two scores before applying this operation.

Why do I need to use a stack to solve this problem?

A stack is ideal because it allows us to efficiently manage and modify the last few scores, which is central to operations like removing or duplicating the last score.

Can I solve this problem without using a stack?

While it's possible to solve this with other data structures, a stack provides a simple and efficient way to handle the problem's operations in O(N) time and O(N) space.

What is the time and space complexity of this problem?

The time complexity is O(N), where N is the number of operations. The space complexity is O(N) because we store up to N scores in the stack at any point.

How do I handle invalidations when the stack is empty?

Ensure that any operation that removes a score ('C') checks that there is at least one score in the stack to prevent errors.

terminal

Solution

Solution 1: Stack + Simulation

We can use a stack to simulate this process.

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        stk = []
        for op in operations:
            if op == "+":
                stk.append(stk[-1] + stk[-2])
            elif op == "D":
                stk.append(stk[-1] << 1)
            elif op == "C":
                stk.pop()
            else:
                stk.append(int(op))
        return sum(stk)

Continue Practicing

#735 asteroid collision #946 validate stack sequences #1441 build an array with stack operations