Baseball Game

Q: Can Baseball Game be solved in O(1) extra space?

Not in general. A run of numbers followed by a run of "C" entries cancels them in reverse order, so you must remember every number until you know whether it will be cancelled. That needs O(n) memory in the worst case. A running total saves the final pass, not the stack.

Q: How do you tell a number from an operation in Baseball Game?

Compare the entry with the three symbols "+" , "D" and "C" first, and treat anything else as an integer. Converting with the language's parser handles a leading minus sign, so "-30000" becomes -30000 .

EasyStack

+10

You keep score for an unusual game. The list operations is read from left to right, and each entry changes a record of scores. An integer such as "7" or "-2" adds that score to the record. "+" adds a score equal to the sum of the two latest scores, "D" adds a score equal to twice the latest score, and "C" removes the latest score from the record for good.

Write a function named calPoints that returns the sum of the scores left on the record after the last operation. An empty record sums to 0.

Function

calPoints(operations: string-array) → integer

operationsstring-array: the operations in order: integers as text, or "+", "D", "C"
Returnsinteger: the sum of the scores still on the record at the end

Constraints

1 ≤ operations.length ≤ 5000
Each entry is "+", "D", "C", or an integer written in decimal with -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Every operation is valid: "+" comes only when the record holds at least two scores, "D" and "C" only when it holds at least one.
Every score on the record and the final sum fit in a 32-bit signed integer.

Examples

Input: operations = ["4", "-2", "D", "+", "C", "7"]
Output: 5
Explanation: The record grows to [4, -2], "D" adds -4, "+" adds -2 + -4 = -6, "C" removes that -6, and 7 goes on last. The record [4, -2, -4, 7] sums to 5.

Input: operations = ["6", "D", "C", "C"]
Output: 0
Explanation: "D" adds 12 after the 6, then the two "C" entries remove 12 and 6. Nothing is left, so the answer is 0.

Input: operations = ["1", "2", "+", "+", "D"]
Output: 21
Explanation: The two "+" entries add 1 + 2 = 3 and then 2 + 3 = 5, and "D" adds 10. The record [1, 2, 3, 5, 10] sums to 21.

+13 hidden tests on Submit

Follow-up

Can you return the sum without adding up the record at the end, so that every operation, a cancel included, takes O(1) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Every operation looks at the latest scores, and "C" can peel scores off one at a time, so the scores before a cancelled one become the latest again. That last-in, first-out pattern is exactly a stack. Push each new score, pop on "C", and read the top one or two entries for "D" and "+".

Build the record on a stack, add it up at the end

Intuition

Keep the record as a list where the newest score sits at the end. Then each operation touches only the end of the list: an integer is pushed, "D" pushes twice the last entry, "+" pushes the sum of the last two entries, and "C" pops the last entry.

Why a stack is enough: after a "C", the score that was second newest becomes the newest, and that is the one a following "D" or "+" must read. Popping gives you that for free. In the first example, "C" pops -6 and leaves [4, -2, -4], so any later "+" would add -2 + -4 again.

When the operations run out, the list holds exactly the scores that count. Add them up. Each operation is O(1) and the final sum is O(n), so the whole run is O(n) time with O(n) space for the stack.

Algorithm

Start with an empty stack record.
For "+", push the sum of the top two entries. For "D", push twice the top entry.
For "C", pop the top entry.
Otherwise the entry is a number: convert the text to an integer and push it.
Return the sum of everything left on the stack.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    for op in operations:
        if op == "+":
            record.append(record[-1] + record[-2])
        elif op == "D":
            record.append(2 * record[-1])
        elif op == "C":
            record.pop()
        else:
            record.append(int(op))
    return sum(record)

Stack with a running total

Intuition

The final loop over the stack is extra work you can avoid. Keep a variable total that always equals the sum of the stack. Every push adds the new score to total, and every "C" subtracts the score it pops.

The stack is still needed. A cancel must know which score to take back out of the total, and "+" and "D" must know the latest scores after any cancels. In the first example the total moves 4, 2, -2, -8, then the cancel takes the -6 back out for -2, and the final 7 brings it to 5.

The time is O(n) with a single pass, and the answer is ready after any prefix of the operations, which matters when scores arrive live. The space is O(n): all n operations could be numbers that stay on the record.

Algorithm

Start with an empty stack record and total = 0.
For "C", pop the top score and subtract it from total.
Otherwise work out the new score: the sum of the top two for "+", twice the top for "D", or the integer itself.
Push the new score and add it to total.
Return total.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    total = 0    # always the sum of record
    for op in operations:
        if op == "C":
            total -= record.pop()  # the cancelled score leaves the total too
            continue
        if op == "+":
            score = record[-1] + record[-2]
        elif op == "D":
            score = 2 * record[-1]
        else:
            score = int(op)
        record.append(score)
        total += score
    return total

Pitfalls and edge cases

The rules are short, so most bugs come from reading the wrong score or from parsing the text.

Keeping only a running total and the last two scores. After a "C", you need the score before those two, so a cancel followed by "+" reads stale values. Keep the whole stack.
Forgetting that cancelled scores leave the total. With a running total, "C" must subtract the popped score, not ignore it.
Parsing negative scores by hand and dropping the sign. Use the language's integer parser, which reads "-2" as -2.
Checking for a digit to decide whether an entry is a number. "-5" starts with a minus sign; test for the three symbols and treat everything else as a number.
Assuming the answer is positive. Negative scores and cancels can leave a negative sum, or 0 when every score was cancelled.

Frequently asked questions4

What is the time complexity of Baseball Game?

Each operation does a constant amount of work on the top of the stack, so processing n operations takes O(n) time. Adding up the stack at the end is another O(n) at most, and a running total removes even that. The stack uses O(n) space when most operations add scores.

Why is a stack the right data structure for Baseball Game?

Every rule reads or removes the most recent scores, and a cancel exposes the score that came before. That is last-in, first-out order, which is what a stack gives you with O(1) push, pop and peek. A plain array or list used only at its end works as the stack in every language.

Can Baseball Game be solved in O(1) extra space?

Not in general. A run of numbers followed by a run of "C" entries cancels them in reverse order, so you must remember every number until you know whether it will be cancelled. That needs O(n) memory in the worst case. A running total saves the final pass, not the stack.

How do you tell a number from an operation in Baseball Game?

Compare the entry with the three symbols "+", "D" and "C" first, and treat anything else as an integer. Converting with the language's parser handles a leading minus sign, so "-30000" becomes -30000.

Python

def calPoints(operations):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

operations = ["4", "-2", "D", "+", "C", "7"]

Expected