Baseball Game - Practice Coding Problems

Baseball Game - Problem

You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.

You are given a list of strings operations, where operations[i] is the i-th operation you must apply to the record and is one of the following:

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 the double of the previous score
'C' - Invalidate the previous score, removing it from the record

Return the sum of all the scores on the record after applying all the operations.

The test cases are generated such that the answer and all intermediate calculations fit in a 32-bit integer and that all operations are valid.

Input & Output

Example 1 — Mixed Operations

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

› Output: 30

💡 Note: "5" → [5], "2" → [5,2], "C" → [5], "D" → [5,10], "+" → [5,10,15]. Sum = 5+10+15 = 30

Example 2 — Simple Numbers

$ Input: operations = ["5","-2","4","C","D","9","+","+"]

› Output: 27

💡 Note: "5" → [5], "-2" → [5,-2], "4" → [5,-2,4], "C" → [5,-2], "D" → [5,-2,-4], "9" → [5,-2,-4,9], "+" → [5,-2,-4,9,5], "+" → [5,-2,-4,9,5,14]. Sum = 27

Example 3 — Only Numbers

$ Input: operations = ["1"]

› Output: 1

💡 Note: Single operation adds 1 to record. Sum = 1

Constraints

1 ≤ operations.length ≤ 1000
operations[i] is "C", "D", "+", or a string representing an integer in range [-3 × 10⁴, 3 × 10⁴]
For 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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of string operations: ["5","2","C","D","+"]

Process

Apply each operation to modify the score record

Output

Sum of all valid scores: 30

Key Takeaway

🎯 Key Insight: Stack data structure naturally handles last-in operations like cancel, double, and sum-previous-two

Asked in

a Amazon 15 G Google 8 f Facebook 5

The key insight is to use a stack data structure to efficiently handle the last-in operations (cancel, double, sum of previous two). Best approach is the stack method with single pass processing. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Stack Approach	O(n)	O(n)	Use stack to efficiently handle operations and calculate sum once
Brute Force with List	O(n²)	O(n)	Use a list to store scores and recalculate sum after each operation

Optimized Stack Approach — Algorithm Steps

Initialize empty stack
Process each operation: push/pop based on operation type
Sum all elements in stack at the end

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Operations

Use stack push/pop for each operation

Stack State

Maintain valid scores in stack

Final Sum

Calculate sum once at the end

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char operations[][10], int n) {
    int stack[1000];
    int top = -1;
    
    for (int i = 0; i < n; i++) {
        if (strcmp(operations[i], "C") == 0) {
            top--;
        } else if (strcmp(operations[i], "D") == 0) {
            stack[++top] = stack[top-1] * 2;
        } else if (strcmp(operations[i], "+") == 0) {
            stack[++top] = stack[top-1] + stack[top-2];
        } else {
            stack[++top] = atoi(operations[i]);
        }
    }
    
    int sum = 0;
    for (int i = 0; i <= top; i++) {
        sum += stack[i];
    }
    return sum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    char operations[100][10];
    int n = 0;
    
    char* token = strtok(line + 1, ",");
    while (token != NULL && n < 100) {
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == ']')) {
            *end = '\0';
            end--;
        }
        strcpy(operations[n], token);
        n++;
        token = strtok(NULL, ",");
    }
    
    int result = solution(operations, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through operations, constant time per operation, one final sum calculation

✓ Linear Growth

Space Complexity

O(n)

Stack stores up to n valid scores in worst case

⚡ Linearithmic Space

285.0K Views

Medium Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Stack Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler