Baseball Game

Difficulty: Easy | Acceptance: 80.40% | Paid: No Topics: Array, Stack, Simulation

You are given a list of strings ops, where ops[i] is the ith operation applied to a record of baseball scores.

The record starts empty. You can perform the following operations on the record:

• An integer x - Record a new score of x.
• ”+” - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be at least two previous scores.
• ”D” - Record a new score that is double the previous score. It is guaranteed there will always be at least one previous score.
• ”C” - Invalidate the previous score, removing it from the record. It is guaranteed there will always be at least one previous score.

Return the sum of all the scores on the record.

• Examples
• Constraints
• Approach 1: Stack Simulation
• Approach 2: Array Pointer Simulation

Examples

Example 1:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"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
Explanation:
"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"]
Output: 1

Constraints

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

Approach 1: Stack Simulation

Intuition The operations “C” (remove last), “D” (access last), and ”+” (access last two) naturally align with the Last-In-First-Out (LIFO) principle of a Stack data structure.

Steps

• Initialize an empty stack.
• Iterate through each operation in the input list.
• If the operation is an integer, push it onto the stack.
• If the operation is “C”, pop the top element from the stack.
• If the operation is “D”, peek the top element, multiply by 2, and push the result.
• If the operation is ”+”, peek the top two elements, sum them, and push the result.
• After processing all operations, sum all elements remaining in the stack and return the result.

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

Complexity

• Time: O(n), where n is the number of operations. We iterate through the list once.
• Space: O(n), in the worst case, we store all operations in the stack.
• Notes: This is the most intuitive approach given the problem constraints.

Approach 2: Array Pointer Simulation

Intuition Instead of using a formal Stack class, we can simulate the stack behavior using a dynamic array and an integer pointer (or index) to track the top of the stack. This can be slightly more performant by avoiding the overhead of method calls associated with Stack classes in some languages.

Steps

• Initialize an integer array (or vector) with a size equal to the number of operations (max possible size).
• Initialize an index i to -1.
• Iterate through the operations.
• If integer, increment i and store value at arr[i].
• If “C”, decrement i (effectively removing the top element).
• If “D”, increment i and store 2 * arr[i-1] at arr[i].
• If ”+”, increment i and store arr[i-1] + arr[i-2] at arr[i].
• Sum the elements from index 0 to i.

class Solution:
    def calPoints(self, ops: list[str]) -> int:
        arr = [0] * len(ops)
        i = -1
        for op in ops:
            if op == "+":
                i += 1
                arr[i] = arr[i-1] + arr[i-2]
            elif op == "D":
                i += 1
                arr[i] = 2 * arr[i-1]
            elif op == "C":
                i -= 1
            else:
                i += 1
                arr[i] = int(op)
        return sum(arr[:i+1])

Complexity

• Time: O(n), where n is the number of operations.
• Space: O(n), for the array storage.
• Notes: This approach avoids dynamic resizing overhead (if pre-allocated) and method call overhead, though the difference is negligible for the given constraints.