Baseball Game Leetcode Problem 682 [Python Solution]

Welcome to another coding adventure! Today, we’re going to tackle the Baseball Game problem from LeetCode.

This problem has an “easy” difficulty level and falls under the category of Stack.

It’s a fun little challenge that may not have much to do with baseball, but it will surely exercise your coding skills.

Question: You are keeping the scores for a baseball game with some unique rules.

At the beginning of the game, you start with an empty record.

You are given a list of strings operations, where each operations[i] represents the i-th operation you must apply to the record.

These operations can be one of the following:

1. An integer x: Record a new score of x.
2. '+': Record a new score that is the sum of the previous two scores.
3. 'D': Record a new score that is double the previous score.
4. 'C': Invalidate the previous score, removing it from the record.

Your task is to return the sum of all the scores on the record after applying all the operations.

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:

Erm, you already get the point.

So,

Problem Overview

The problem presents us with a series of operations that we need to perform on a record, maintaining the scores according to the given rules.

We will implement this using a stack data structure.

A stack allows us to add and remove elements in a last-in, first-out (LIFO) order, which aligns perfectly with the problem requirements.

Understanding Constraints

To solve this problem efficiently, we need to be aware of a few constraints:

• The integer scores provided can range from -30,000 to 30,000. So, we need to handle a wide range of score values.
• For the 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.

Baseball Game LeetCode Problem Solution

Now that we’ve grasped the problem and its constraints, let’s explore how we can implement a solution in Python.

We’ll use a stack to keep track of the scores.

We’ll iterate through the given operations and apply the following logic:

• If the operation is '+', we will add the sum of the last two scores to the stack.
• If the operation is 'D', we will double the last score and add it to the stack.
• If the operation is 'C', we will remove the last score from the stack.
• If the operation is an integer, we will convert it from a string to an integer and add it to the stack.

Here’s the Python code for the brute-force approach:

def calPoints(self, operations):
    score_stack = []

    for o in operations:
        if o == '+' and len(score_stack) >= 2:
            summed = score_stack[-2] + score_stack[-1]
            score_stack.append(summed)
        elif o == 'D' and len(score_stack) >= 1:
            doubled = score_stack[-1] * 2
            score_stack.append(doubled)
        elif o == 'C' and len(score_stack) >= 1:
            score_stack.pop()
        else:
            score_stack.append(int(o))

    return sum(score_stack)

This code efficiently handles the given operations and calculates the final sum of scores.

Time and Space Complexity

• Time Complexity: The code iterates through all the operations once, resulting in a time complexity of O(N), where N is the length of the operations list.
• Space Complexity: The space complexity is O(N) as well since, in the worst case, all operations could result in new scores being added to the stack.

Related Interview Questions By Company:

• Find Pivot Index LeetCode
• Move Zeroes LeetCode
• Construct String From Binary Tree LeetCode

Related Interview Questions By Difficulty:

• Baseball Game LeetCode
• Remove All Adjacent Duplicates In String II LeetCode
• Decode String LeetCode

Related Interview Questions By Category:

• Add Binary LeetCode
• Binary Tree Postorder Traversal LeetCode
• Remove Duplicates From Sorted Array II LeetCode

Reasoning Behind Our Approach

The provided solution leverages a stack data structure to efficiently track and manipulate scores.

It maintains all necessary information to calculate the final sum accurately.

By iterating through the given operations in a single pass, we keep the code simple and computationally efficient.

In summary, the Baseball Game problem is a delightful exercise in data manipulation.

We’ve successfully implemented a Python solution that takes advantage of a stack to manage the scoring system.

By understanding the problem’s constraints and utilizing a stack, we’ve created an efficient and straightforward solution.

Feel free to explore more LeetCode problems, ask questions, make suggestions, and share this content.

Learning and mastering data structures and algorithms is a valuable skill for any aspiring coder.

Happy coding!

Question Link