682. Baseball Game

EasyStackArraySimulation
Leetcode Link

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:

  1. A positive or negative integer x which means adding a new score of x to the record.
  2. A '+' which means adding a new score that is the sum of the two most recent scores.
  3. A 'D' which signifies that you need to double the latest recorded score and add this new value to the record.
  4. 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.

  1. Iterate through each operation in the operations list.
  2. If the operation is a positive or negative integer, convert it to an integer and push it onto the stack.
  3. If the operation is a '+', calculate the sum of the last two scores in the stack and push the result back onto the stack.
  4. 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.
  5. If the operation is a 'C', pop the last score off the stack to remove it from the record.
  6. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

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:

  1. Initialize an empty stack stk, which will be used to keep track of the scores as they are recorded and modified.

  2. Loop through each op in the ops list, which contains all the operations that need to be applied to the record in sequence.

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

  4. Once all the operations are applied, the scores that remain on the stack represent the valid scores after following all the operations.

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

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

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

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

1operations = ["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:

  1. The stack is initially empty: stk = []

  2. Process the first operation "5". Since "5" is an integer (not a special character), push it onto the stack:

    • stk = [5]

  3. Next operation is "-2". It's an integer, so push it onto the stack:

    • stk = [5, -2]

  4. The operation "4" is also an integer. Append it to the stack:

    • stk = [5, -2, 4]

  5. The operation "C" indicates that we should remove the last score. Pop the last element from the stack:

    • stk = [5, -2]

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

  7. The operation "9" is an integer. Append it to the stack:

    • stk = [5, -2, -4, 9]

  8. For the operation "+", add the last two scores (9 + (-4) = 5) and push the result onto the stack:

    • stk = [5, -2, -4, 9, 5]

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

  10. 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
Not Sure What to Study? Take the 2-min Quiz：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Stack Intro

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫