# Baseball Game
**Difficulty:** EASY
[External](https://leetcode.com/problems/baseball-game)
Canonical: https://scaleengineer.com/dsa/problems/baseball-game
**Data structures:** Array, Stack
**Companies:** [Turing](https://scaleengineer.com/companies/turing)
---
## Problem
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 `ith` 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 * 104, 3 * 104]`.
* 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.

# Approaches
## Inefficient Simulation with ArrayList
This approach simulates the record of scores using an `ArrayList`. However, it uses inefficient methods to mimic stack-like behavior. New scores are added to the beginning of the list, and removals also happen from the beginning. This forces the list to shift all its elements on every such operation, leading to poor performance.
**Time:** O(N^2), where N is the number of operations. In the worst case, each operation involves adding or removing from the beginning of the `ArrayList`, which takes O(k) time where k is the current size of the list. Since k can be up to N, the total time complexity is quadratic. · **Space:** O(N), as the `record` list can store up to N scores.
**Pros:** Simple to understand the logic.; Uses a common data structure.
**Cons:** Highly inefficient due to using `add(0, ...)` and `remove(0)` on an `ArrayList`.; Will be very slow for large inputs, although the problem constraints (`N <= 1000`) might allow it to pass.
### Explanation
We can use a Java `ArrayList` to store the scores. We'll iterate through the `operations` array and perform actions based on the current operation string.
- For a number, we parse it and add it to the *front* of the list using `list.add(0, score)`.
- For a `'+'`, we get the first two elements (`list.get(0)` and `list.get(1)`), sum them, and add the result to the front.
- For a `'D'`, we get the first element, double it, and add the result to the front.
- For a `'C'`, we remove the first element using `list.remove(0)`.

Adding or removing from the beginning of an `ArrayList` requires shifting all subsequent elements, which is an O(k) operation, where k is the current size of the list. Since this is done inside a loop that runs N times, the total time complexity becomes quadratic.

After processing all operations, we sum up the elements remaining in the list to get the final score.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int calPoints(String[] operations) {
        List<Integer> record = new ArrayList<>();
        for (String op : operations) {
            if (op.equals("+")) {
                int newScore = record.get(0) + record.get(1);
                record.add(0, newScore);
            } else if (op.equals("D")) {
                int newScore = 2 * record.get(0);
                record.add(0, newScore);
            } else if (op.equals("C")) {
                record.remove(0);
            } else {
                record.add(0, Integer.parseInt(op));
            }
        }

        int sum = 0;
        for (int score : record) {
            sum += score;
        }
        return sum;
    }
}
```
### Algorithm
- Initialize an empty `ArrayList<Integer>` named `record`.
- Iterate through each `operation` in the input `ops` array.
- Use a `switch` statement or `if-else` chain to handle the `operation`:
    - Case `"+"`: Calculate `sum = record.get(0) + record.get(1)` and add it to the front: `record.add(0, sum)`.
    - Case `"D"`: Calculate `double = 2 * record.get(0)` and add it to the front: `record.add(0, double)`.
    - Case `"C"`: Remove the score at the front: `record.remove(0)`.
    - Default (number): Parse the string to an integer and add it to the front: `record.add(0, Integer.parseInt(operation))`.
- After the loop, iterate through the final `record` list and calculate the total sum of its elements.
- Return the total sum.

## Efficient Simulation with ArrayList
This approach also uses an `ArrayList` to simulate the record, but it does so efficiently. Instead of adding and removing from the beginning, it treats the end of the list as the "top" of the record. This leverages the O(1) amortized time complexity of adding to and removing from the end of an `ArrayList`.
**Time:** O(N), where N is the number of operations. We iterate through the operations once. Each operation on the `ArrayList` (add to end, get from end, remove from end) takes O(1) amortized time. The final summation is also linear. · **Space:** O(N), as the `record` list can store up to N scores.
**Pros:** Efficient with linear time complexity.; Still uses a very common and easy-to-understand data structure.
**Cons:** While efficient, using an `ArrayList` as a stack is slightly less idiomatic than using a dedicated `Stack` or `Deque` interface. The code `record.get(record.size() - 1)` is more verbose than `stack.peek()`.
### Explanation
The core idea is to use an `ArrayList` as if it were a stack. The "previous" score is always the last element in the list.
- For a number, we parse it and append it to the end of the list using `list.add(score)`.
- For a `'+'`, we access the last two elements (`list.get(list.size() - 1)` and `list.get(list.size() - 2)`), sum them, and append the result.
- For a `'D'`, we access the last element, double it, and append the result.
- For a `'C'`, we remove the last element using `list.remove(list.size() - 1)`.

All these operations that modify the end of an `ArrayList` are very fast (amortized constant time). This makes the overall algorithm linear in time.

After processing all operations, we sum up the elements in the list.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int calPoints(String[] operations) {
        List<Integer> record = new ArrayList<>();
        for (String op : operations) {
            int n = record.size();
            if (op.equals("+")) {
                record.add(record.get(n - 1) + record.get(n - 2));
            } else if (op.equals("D")) {
                record.add(2 * record.get(n - 1));
            } else if (op.equals("C")) {
                record.remove(n - 1);
            } else {
                record.add(Integer.parseInt(op));
            }
        }

        int sum = 0;
        for (int score : record) {
            sum += score;
        }
        return sum;
    }
}
```
### Algorithm
- Initialize an empty `ArrayList<Integer>` named `record`.
- Iterate through each `operation` in the input `ops` array.
- Use a `switch` statement or `if-else` chain:
    - Case `"+"`: Get the last two scores: `score1 = record.get(record.size() - 1)` and `score2 = record.get(record.size() - 2)`. Append their sum to the list.
    - Case `"D"`: Get the last score: `score = record.get(record.size() - 1)`. Append `2 * score` to the list.
    - Case `"C"`: Remove the last score: `record.remove(record.size() - 1)`.
    - Default (number): Parse the string to an integer and append it to the list.
- After the loop, calculate the sum of all elements in the `record`.
- Return the sum.

## Optimal Approach using a Stack
This is the most natural and idiomatic approach for this problem. The operations (`+`, `D`, `C`) all concern the most recently added scores, which follows a Last-In, First-Out (LIFO) principle. A `Stack` is the perfect data structure for this pattern.
**Time:** O(N), where N is the number of operations. Each operation is processed once, and stack operations (`push`, `pop`, `peek`) take constant O(1) time. · **Space:** O(N). In the worst-case scenario, the stack can grow to hold N scores.
**Pros:** Most idiomatic and conceptually clean solution for a LIFO problem.; Code is expressive and easy to read.; Optimal time and space complexity.; Using `ArrayDeque` is slightly more performant than the legacy `Stack` class in single-threaded environments.
**Cons:** No significant cons; this is the standard and best way to solve this problem.
### Explanation
We can use a `Stack<Integer>` to maintain the record of valid scores. We process each operation one by one.
- For a number, we parse it and `push` it onto the stack.
- For a `'+'`, we `pop` the top score, `peek` at the new top, calculate their sum, then `push` the first score back, and finally `push` the sum. This sequence ensures the stack remains correct for subsequent operations.
- For a `'D'`, we `peek` at the top score, double it, and `push` the result onto the stack.
- For a `'C'`, we simply `pop` the top score from the stack.

Using a stack makes the code cleaner and more expressive, as the methods (`push`, `pop`, `peek`) directly correspond to the logic of adding, removing, and accessing the most recent score. In modern Java, it's often recommended to use a `Deque` (like `ArrayDeque`) as a stack for better performance, as `Stack` is a legacy synchronized class.

After all operations are processed, we sum up the remaining scores in the stack to get the final result.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int calPoints(String[] operations) {
        // ArrayDeque is generally preferred over the legacy Stack class.
        Deque<Integer> stack = new ArrayDeque<>();

        for (String op : operations) {
            switch (op) {
                case "+":
                    int top = stack.pop();
                    int newTop = top + stack.peek();
                    stack.push(top);
                    stack.push(newTop);
                    break;
                case "D":
                    stack.push(2 * stack.peek());
                    break;
                case "C":
                    stack.pop();
                    break;
                default:
                    stack.push(Integer.parseInt(op));
                    break;
            }
        }

        int sum = 0;
        for (int score : stack) {
            sum += score;
        }
        return sum;
    }
}
```
### Algorithm
- Initialize an empty `Stack<Integer>` (or `Deque<Integer>`).
- Iterate through each `operation` in the `ops` array.
- Handle the `operation`:
    - Case `"+"`: Pop the top element (`last`). Peek the new top (`prev`). Push `last` back. Push `last + prev`.
    - Case `"D"`: Peek the top element (`last`). Push `2 * last`.
    - Case `"C"`: Pop the top element.
    - Default (number): Parse the string to an integer and push it onto the stack.
- After the loop, iterate through the stack and sum up all its elements.
- Return the sum.

# Solutions
### Java

```java
class Solution {
public
  int calPoints(String[] ops) {
    Deque<Integer> stk = new ArrayDeque<>();
    for (String op : ops) {
      if ("+".equals(op)) {
        int a = stk.pop();
        int b = stk.peek();
        stk.push(a);
        stk.push(a + b);
      } else if ("D".equals(op)) {
        stk.push(stk.peek() << 1);
      } else if ("C".equals(op)) {
        stk.pop();
      } else {
        stk.push(Integer.valueOf(op));
      }
    }
    return stk.stream().mapToInt(Integer : : intValue).sum();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int calPoints(vector<string> &ops) {
    vector<int> stk;
    for (auto &op : ops) {
      int n = stk.size();
      if (op == "+") {
        int a = stk[n - 1];
        int b = stk[n - 2];
        stk.push_back(a + b);
      } else if (op == "D")
        stk.push_back(stk[n - 1] * 2);
      else if (op == "C")
        stk.pop_back();
      else
        stk.push_back(stoi(op));
    }
    return accumulate(stk.begin(), stk.end(), 0);
  }
};

```

### Python

```python
class Solution:
    def calPoints(self, ops: List[str]) -> int: stk = [] for op in ops: if op == '+': stk . append(stk[- 1] + stk[- 2]) elif op == 'D': stk . append(stk[- 1] << 1) elif op == 'C': stk . pop() else: stk . append(int(op)) return sum(stk)

```