Leetcode – Baseball Game Solution in Python

Spread the love

Introduction

In programming, the ability to model real-world scenarios and events is an invaluable asset. The “Baseball Game” problem on Leetcode presents an opportunity to simulate a sports event through the manipulation of stacks. This article aims to provide a comprehensive walkthrough of the problem, acquaint the reader with relevant concepts, and detail different algorithmic approaches for solving the problem in Python.

Problem Statement

You’re now a baseball game point recorder.

Given a list of strings ops, where ops[i] is one of the following:

  • An integer (represented as a string): Directly represents the number of points you get in this round.
  • “+” (a plus sign): Represents that the points you get in this round are the sum of the last two valid round’s points.
  • “D” (a capital letter D): Represents that the points you get in this round are the doubled data of the last valid round’s points.
  • “C” (a capital letter C): Represents an invalid round, where the points you earned were invalid and should be removed.

Return the sum of the points you could get in all the rounds.

Example:

Input: ops = ["5", "2", "C", "D", "+"]

Output: 30

Explanation:

  • Round 1: You could get 5 points. The sum is: 5.
  • Round 2: You could get 2 points. The sum is: 7.
  • Operation 1: The round 2’s data is invalid. The sum is: 5.
  • Round 3: You could get 10 points (the round 2’s data has been removed). The sum is: 15.
  • Round 4: You could get 5 + 10 = 15 points. The sum is: 30.

Key Concepts

1. Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) order, i.e., the last element added to the stack is the first one to be removed. It is particularly useful in scenarios where we need to keep track of objects in an order and access the last object added.

Algorithmic Approach

Stack-based Approach

The stack-based approach is the most intuitive and optimal way to solve the Baseball Game problem. The idea is to use a stack to keep track of the points in each round. For each operation in ops, we perform the corresponding action and update the stack accordingly.

Algorithm:

  1. Initialize an empty stack called points.
  2. Iterate through each operation in ops. a. If the operation is an integer, push it onto the stack. b. If the operation is “C”, pop the top element from the stack (effectively removing the last round’s points). c. If the operation is “D”, push twice the value of the top element onto the stack. d. If the operation is “+”, push the sum of the top two elements onto the stack.
  3. Return the sum of the elements in the stack, as this represents the total points earned.
def calPoints(ops):
    points = []
    
    for op in ops:
        if op == "C":
            points.pop()
        elif op == "D":
            points.append(points[-1] * 2)
        elif op == "+":
            points.append(points[-1] + points[-2])
        else:
            points.append(int(op))
            
    return sum(points)

Time Complexity:

  • O(n), where n is the length of the input list ops, since we need to iterate through each operation.

Space Complexity:

  • O(n), as we are using a stack to keep track of points, and in the worst case, it can contain n elements.

Conclusion

The Baseball Game problem is an excellent example of how stacks can be used to effectively model and solve real-world scenarios. Through the stack-based approach, we were able to keep track of points in a simulated baseball game while accounting for different operations that may occur.

Leave a Reply