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 ofx
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 theops
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 arestk[-1]
andstk[-2]
. We sum these two and push the result back onto the stack withstk.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 withstk.append(stk[-1] << 1)
. - If
op
is'C'
, we need to remove the last score from the record. Popping from the stack withstk.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 withint(op)
and push it onto the stack withstk.append(int(op))
.
- If
-
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 functionsum(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 EvaluatorExample 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
- The final score:
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.
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
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!