Leetcode 682. Baseball Game

Problem

Leetcode 682 - Baseball Game

Example:

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.

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.

Input: ops = ["1","C"]
Output: 0
Explanation:
"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.

Approach

We can use a stack to implement this. We can simply iterate through an input array

• ’+’: append addition of two last elements
• ‘D’: append 2 * last element
• ‘C’: pop from stack
• else: append the string as int

Once we’re done iterating through input array, we can just return the sum of array

Visualization of the Approach:

ops = ['5', '2', 'C', 'D', '+']
record = []

val = 5
record = [5]

val = 2
record = [5, 2]

val = 'C'
record = [5], since we pop the last element

val = 'D'
record = [5, 10], since record[-1] * 2 = 10

val = '+'
record = [5, 10, 15], since record[-1] + record[-2] = 15

Thus, sum of record = 30
return 30

Here is the Python code for the solution:

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        record = []

        for val in operations:
            if val == '+':
                record.append(record[-1] + reocrd[-2])
            elif val == 'D':
                record.append(record[-1] * 2)
            elif val == 'C':
                record.pop()
            else:
                record.append(int(val))
        
        res = 0
        for num in record:
            res += num
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$