LeetCode 682: Baseball Game

Problem Restatement

We are given a list of operations called ops.

These operations describe scores in a baseball game.

We process the operations from left to right and maintain a record of valid scores.

The operations are:

After processing all operations, return the sum of all valid scores.

The official examples include ["5","2","C","D","+"] -> 30 and ["5","-2","4","C","D","9","+","+"] -> 27. (leetcode.com)

Input and Output

Example function shape:

def calPoints(ops: list[str]) -> int:
    ...

Examples

Example 1:

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

Process step by step:

Final sum:

5 + 10 + 15 = 30

Answer:

30

Example 2:

ops = ["5","-2","4","C","D","9","+","+"]

Process:

Final sum:

5 - 2 - 4 + 9 + 5 + 14 = 27

Answer:

27

First Thought: Maintain All Valid Scores

Every operation only depends on recent valid scores.

For example:

This naturally suggests a stack.

The stack stores all current valid scores in order.

The top of the stack is the most recent valid score.

Key Insight

The operations exactly match stack behavior.

Because each operation modifies only the most recent scores, we never need random access to older elements.

A stack gives efficient push and pop operations.

Algorithm

Create an empty stack called scores.

Process each operation op in ops.

If op is an integer:

scores.append(int(op))

If op == "C":

scores.pop()

If op == "D":

scores.append(scores[-1] * 2)

If op == "+":

scores.append(scores[-1] + scores[-2])

After processing all operations:

return sum(scores)

Walkthrough

Consider:

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

Start:

scores = []

Operation "5":

scores = [5]

Operation "2":

scores = [5, 2]

Operation "C" removes the most recent score:

scores = [5]

Operation "D" doubles the previous score:

5 * 2 = 10

Now:

scores = [5, 10]

Operation "+" sums the last two scores:

5 + 10 = 15

Now:

scores = [5, 10, 15]

Final result:

5 + 10 + 15 = 30

Correctness

The algorithm maintains the invariant that scores always contains exactly the valid scores after processing the current prefix of operations.

Initially, before processing any operation, the list is empty, which is correct.

If the next operation is an integer x, the rules say to record a new score x. The algorithm appends x to the stack, so the stack remains correct.

If the next operation is "C", the rules say to invalidate the previous valid score. The most recent valid score is the top of the stack, so removing it with pop() produces the correct remaining scores.

If the next operation is "D", the rules say to record double the previous valid score. The previous valid score is the top of the stack, so appending 2 * scores[-1] records the correct new score.

If the next operation is "+", the rules say to record the sum of the previous two valid scores. Those are the top two stack elements, so appending their sum records the correct new score.

Thus, after every operation, the stack exactly matches the valid scores defined by the problem statement.

At the end, the required answer is the total of all valid scores, which the algorithm returns using sum(scores).

Therefore, the algorithm is correct.

Complexity

Let n be the number of operations.

Each stack operation is constant time.

Implementation

class Solution:
    def calPoints(self, ops: list[str]) -> int:
        scores = []

        for op in ops:
            if op == "C":
                scores.pop()
            elif op == "D":
                scores.append(scores[-1] * 2)
            elif op == "+":
                scores.append(scores[-1] + scores[-2])
            else:
                scores.append(int(op))

        return sum(scores)

Code Explanation

We store valid scores in:

scores = []

For each operation:

for op in ops:

If the operation is "C":

scores.pop()

we remove the most recent valid score.

If the operation is "D":

scores.append(scores[-1] * 2)

we double the previous valid score and record it.

If the operation is "+":

scores.append(scores[-1] + scores[-2])

we add the last two valid scores.

Otherwise, the operation is an integer string:

scores.append(int(op))

Finally:

return sum(scores)

returns the total score.

Testing

def run_tests():
    s = Solution()

    assert s.calPoints(["5", "2", "C", "D", "+"]) == 30
    assert s.calPoints(["5","-2","4","C","D","9","+","+"]) == 27
    assert s.calPoints(["1"]) == 1
    assert s.calPoints(["1", "D"]) == 3
    assert s.calPoints(["1", "2", "+"]) == 6
    assert s.calPoints(["10", "-5", "D"]) == -5
    assert s.calPoints(["3", "C", "4"]) == 4

    print("all tests passed")

run_tests()

Test meaning: