682. Baseball Game

Problem Description

In this problem, we are given a set of operations that simulate the scoring of a baseball game, but with unique rules. A score record starts empty, and the operations are applied in sequence as given in the list of strings called operations. Each element in this list operations[i] represents an action to modify the score record. The operations include:

A positive or negative integer x which means adding a new score of x to the record.
A '+' which means adding a new score that is the sum of the two most recent scores.
A 'D' which signifies that you need to double the latest recorded score and add this new value to the record.
A 'C' which means removing the last score from the record, effectively invalidating the last operation.

The primary goal is to calculate the sum of all the scores on the record after all the operations have been applied.

The inputs are designed such that the final result, as well as any intermediate results, will fit within a 32-bit integer, and that all operations can be applied without error (operations are valid).

Intuition

To solve this problem, we can use a stack, which is perfectly suited for situations where we need to keep track of a list of elements and frequently add or remove items from the end.

Iterate through each operation in the operations list.
If the operation is a positive or negative integer, convert it to an integer and push it onto the stack.
If the operation is a '+', calculate the sum of the last two scores in the stack and push the result back onto the stack.
If the operation is a 'D', double the last score in the stack (using the left shift operation << 1 for efficiency, which is equivalent to multiplying by 2) and push the result onto the stack.
If the operation is a 'C', pop the last score off the stack to remove it from the record.
After processing all operations, the stack will contain all the valid scores. Summing these scores will give us the final result required.

The key to this solution is realizing that the last score is always at the top of the stack, and previous scores are below it, which aligns perfectly with the operation requirements of the problem. Applying each operation modifies the top portion of the stack, and in the end, we only need to sum the elements present in the stack to get the total score.

Learn more about Stack patterns.

Solution Approach

The implementation of the solution employs a stack to manage the operations on the scores effectively. Here is a step-by-step breakdown of how the algorithm works:

Initialize an empty stack stk, which will be used to keep track of the scores as they are recorded and modified.
Loop through each op in the ops list, which contains all the operations that need to be applied to the record in sequence.
Within the loop, determine the type of operation:
- If op is '+', we need to add the last two scores. Since the stack is LIFO (Last In, First Out), the last two scores are stk[-1] and stk[-2]. We sum these two and push the result back onto the stack with stk.append(stk[-1] + stk[-2]).
- If op is 'D', we need to double the last score. Doubling can be efficiently done by using the bitwise left shift operation << 1 (which is similar to multiplying the last score by 2). The result is then pushed onto the stack with stk.append(stk[-1] << 1).
- If op is 'C', we need to remove the last score from the record. Popping from the stack with stk.pop() removes the last element.
- If op is neither of these special characters, it is an integer in string format. Convert it to an integer with int(op) and push it onto the stack with stk.append(int(op)).
Once all the operations are applied, the scores that remain on the stack represent the valid scores after following all the operations.
The sum of the entire stack is calculated using the sum() function, which adds up all the integers in the stack. This sum is then returned as the final result of the function sum(stk).

This solution approach relies on the ability of the stack to efficiently manage elements where the most recent elements need to be accessed or modified. It makes use of the fact that each operation only affects the most recent scores, which are always at the top of the stack, making the rest of the list irrelevant for that specific operation. By pushing the results of operations onto the stack and popping when necessary, the algorithm correctly simulates the scoring system of the game using a last-in, first-out structure.

The Python implementation is straightforward and makes use of the native list data structure in Python, which can be used as a stack with its append and pop methods.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a sample round of the baseball game with the following series of operations:

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

Following is the walk-through of how the scoring will be updated step-by-step, applying the solution approach:

The stack is initially empty: stk = []
Process the first operation "5". Since "5" is an integer (not a special character), push it onto the stack:
- stk = [5]
Next operation is "-2". It's an integer, so push it onto the stack:
- stk = [5, -2]
The operation "4" is also an integer. Append it to the stack:
- stk = [5, -2, 4]
The operation "C" indicates that we should remove the last score. Pop the last element from the stack:
- stk = [5, -2]
The operation "D" requires doubling the last score and pushing the result onto the stack. Double the last score (-2) to get -4 and push it onto the stack:
- stk = [5, -2, -4]
The operation "9" is an integer. Append it to the stack:
- stk = [5, -2, -4, 9]
For the operation "+", add the last two scores (9 + (-4) = 5) and push the result onto the stack:
- stk = [5, -2, -4, 9, 5]
Finally, apply another "+"' operation, add the last two scores again (5 + 9 = 14) and push the result onto the stack:
- stk = [5, -2, -4, 9, 5, 14]
With all operations processed, we now sum the elements of the stack to obtain the final result.
- The final score: 5 - 2 - 4 + 9 + 5 + 14 = 27

Thus, the sum of the scores on the stack is 27, which would be the output of the solution for these operations.

The walk-through vividly demonstrates the use of a stack to manage the scores throughout the operation sequence, complying with the rules of the special baseball game. Each operation is applied in turn, modifying the state of the stack until all operations have been processed, at which point the sum of the stack represents the final score.

Solution Implementation

1# Class to define the solution for the problem.
2class Solution:
3    # Function to calculate the final score using a list of operations.
4    def calPoints(self, ops: List[str]) -> int:
5        # Initialize a stack to keep track of the scores.
6        scores_stack = []
7
8        # Loop over each operation in the list of operations.
9        for op in ops:
10            # If operation is "+", add the sum of the last two scores to the stack.
11            if op == '+':
12                scores_stack.append(scores_stack[-1] + scores_stack[-2])
13            # If operation is "D", double the last score and add to the stack.
14            elif op == 'D':
15                scores_stack.append(scores_stack[-1] * 2)
16            # If operation is "C", remove the last score from the stack.
17            elif op == 'C':
18                scores_stack.pop()
19            # Otherwise, the operation is a number, so parse and add to the stack.
20            else:
21                scores_stack.append(int(op))
22      
23        # Return the sum of the scores on the stack, which is the final score.
24        return sum(scores_stack)
25

1class Solution {
2    public int calPoints(String[] ops) {
3        // Create a deque to use as a stack to keep track of the points.
4        Deque<Integer> stack = new ArrayDeque<>();
5      
6        // Loop through the operations.
7        for (String op : ops) {
8            switch (op) {
9                case "+": // If the operation is "+", add the sum of the last two scores.
10                    int last = stack.pop(); // Remove the last score from the stack.
11                    int newTop = stack.peek(); // Peek at the new top without removing it.
12                    stack.push(last); // Push the last score back onto the stack.
13                    stack.push(last + newTop); // Push the sum of last two scores onto the stack.
14                    break;
15                case "D": // If the operation is "D", double the last score.
16                    stack.push(stack.peek() * 2); // Peek the last score, double it, and push onto the stack.
17                    break;
18                case "C": // If the operation is "C", remove the last score.
19                    stack.pop(); // Remove the last score from the stack.
20                    break;
21                default: // For any number, parse it and put onto the stack.
22                    stack.push(Integer.parseInt(op)); // Parse the string to an integer and push it onto the stack.
23                    break;
24            }
25        }
26      
27        // Sum up and return the points in the stack.
28        int sum = 0;
29        for (int score : stack) {
30            sum += score; // Accumulate the scores.
31        }
32      
33        return sum; // Return the final sum of the scores.
34    }
35}
36

1#include <vector>
2#include <string>
3#include <numeric>
4
5class Solution {
6public:
7    int calPoints(vector<string>& operations) {
8        vector<int> recordStack; // Stack to maintain the record of points
9
10        // Iterate through each operation
11        for (const auto& operation : operations) {
12            int currentSize = recordStack.size(); // Current size of the record stack
13
14            // If operation is "+", push the sum of the last two scores onto the recordStack
15            if (operation == "+") {
16                int lastScore = recordStack[currentSize - 1];
17                int secondLastScore = recordStack[currentSize - 2];
18                recordStack.push_back(lastScore + secondLastScore);
19            } 
20            // If operation is "D", double the last score and push onto the recordStack
21            else if (operation == "D") {
22                recordStack.push_back(recordStack[currentSize - 1] * 2);
23            } 
24            // If operation is "C", remove the last score from the recordStack
25            else if (operation == "C") {
26                recordStack.pop_back();
27            } 
28            // Otherwise, operation is assumed to be a number, convert to int and push onto the recordStack
29            else {
30                recordStack.push_back(stoi(operation));
31            }
32        }
33
34        // Sum up all the scores in the recordStack to get the total points
35        return accumulate(recordStack.begin(), recordStack.end(), 0);
36    }
37};
38

1function calculatePoints(operations: string[]): number {
2    // Initialize a stack to store the valid round points
3    const pointsStack: number[] = [];
4  
5    // Iterate over each operation in the array
6    for (const operation of operations) {
7        const length = pointsStack.length; // The current length of the stack
8      
9        switch (operation) {
10            case '+': // If the operation is '+', add the last two round's points
11                if (length >= 2) {
12                    const lastRoundPoints = pointsStack[length - 1];
13                    const secondLastRoundPoints = pointsStack[length - 2];
14                    pointsStack.push(lastRoundPoints + secondLastRoundPoints);
15                }
16                break;
17            case 'D': // If the operation is 'D', double the last round's points
18                if (length >= 1) {
19                    const lastRoundPoints = pointsStack[length - 1];
20                    pointsStack.push(lastRoundPoints * 2);
21                }
22                break;
23            case 'C': // If the operation is 'C', remove the last round's points
24                if (length >= 1) {
25                    pointsStack.pop();
26                }
27                break;
28            default: // If the operation is a number, parse it and add to the stack
29                const roundPoints = Number(operation);
30                if (!isNaN(roundPoints)) {
31                    pointsStack.push(roundPoints);
32                }
33                break;
34        }
35    }
36
37    // Sum up all the points in the stack and return the total
38    const totalPoints = pointsStack.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
39    return totalPoints;
40}
41

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the input list ops. This is because the code iterates through each element in ops once, and the operations performed within the loop (push, pop, addition, and doubling) are all constant-time operations, occurring in O(1).

The space complexity of the code is also O(n). In the worst case, if there are no 'C' operations to cancel the previous scores, the stack stk will have to store an integer for each input operation in ops. Therefore, the space used by the stack is directly proportional to the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know