We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Baseball Game

Number: 682

Difficulty: Easy

Paid? No

Companies: Meta, Microsoft, Turing, Google, Apple, Amazon

Problem Description

Given a list of operations representing tracked scores, update the score record based on the following rules:

  • An integer x: Record a new score of x.
  • "+": Record a new score that is the sum of the previous two scores.
  • "D": Record a new score that is twice the previous score.
  • "C": Invalidate the previous score, removing it from the record. Return the sum of all scores after processing all operations.

Key Insights

  • Use a stack (list) to keep track of valid scores.
  • Process operations sequentially, updating the stack accordingly.
  • Handle different operations by manipulating the stack: push new scores, pop invalid scores.
  • Final result is the sum of scores left in the stack.

Space and Time Complexity

Time Complexity: O(n), where n is the number of operations. Space Complexity: O(n), in the worst-case the stack stores all operation results.

Solution

The solution uses a stack-based approach. Iterate through each operation and:

  • If the operation is a numeric value, convert it to an integer and push it onto the stack.
  • If it is "C", remove the most recent score by popping from the stack.
  • If it is "D", double the most recent score and push the result.
  • If it is "+", calculate the sum of the two most recent scores and push that value. Finally, sum all the values in the stack to obtain the final score.

Code Solutions

# Define the function to calculate total score for the baseball game
def calPoints(ops):
    # Initialize a list to be used as a stack for scores
    score_stack = []
    
    # Iterate over each operation in the list
    for op in ops:
        # If the operation is "C", remove the last score from the stack
        if op == "C":
            score_stack.pop()
        # If the operation is "D", double the last score and append it
        elif op == "D":
            score_stack.append(2 * score_stack[-1])
        # If the operation is "+", sum the last two scores and append the result
        elif op == "+":
            score_stack.append(score_stack[-1] + score_stack[-2])
        # Otherwise, the operation is a number in string form, convert to integer and append
        else:
            score_stack.append(int(op))
    
    # Return the total sum of all scores in the stack
    return sum(score_stack)

# Example usage:
print(calPoints(["5", "2", "C", "D", "+"]))  # Expected output: 30
← Back to All Questions