Baseball Game

LeetCode 682 | Difficulty: Easy

Easy

Problem Description

You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.

You are given a list of strings operations, where operations[i] is the i^th operation you must apply to the record and is one of the following:

- An integer `x`.



    - Record a new score of `x`.





- `'+'`.


    - Record a new score that is the sum of the previous two scores.





- `'D'`.


    - Record a new score that is the double of the previous score.





- `'C'`.


    - Invalidate the previous score, removing it from the record.

Return the sum of all the scores on the record after applying all the operations.

The test cases are generated such that the answer and all intermediate calculations fit in a 32-bit integer and that all operations are valid.

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","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.

Constraints:

- `1 <= operations.length <= 1000`

- `operations[i]` is `"C"`, `"D"`, `"+"`, or a string representing an integer in the range `[-3 * 10^4, 3 * 10^4]`.

- 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.

Topics: Array, Stack, Simulation

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

---

Solutions

Solution 1: C# (Best: 129 ms)

Metric	Value
Runtime	129 ms
Memory	37.4 MB
Date	2022-01-18

Solution

public class Solution {
    public int CalPoints(string[] ops) {
        List<int> scores = new List<int>();
    foreach (var op in ops)
    {
        int len = scores.Count;
        if (op == "+")
        {
            scores.Add(scores[len - 1] + scores[len - 2]);
        }
        else if (op == "D")
        {
            scores.Add(scores[len - 1] * 2);
        }
        else if (op == "C")
        {
            scores.RemoveAt(len - 1);
        }
        else
            scores.Add(Convert.ToInt32(op));
    }
    return scores.Sum();
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?