102. Baseball Game

🔗 LeetCode Problem: 682. Baseball Game
📊 Difficulty: Easy
🏷️ Topics: Stack, Array, Simulation

Problem Statement

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:

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.

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.

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:

Input: ops = ["1","C"]
Output: 0

Explanation:
"1" - Add 1 to the record, record is now [1].
"C" - Invalidate and remove the previous score, record is now [].
The total sum is 0.

Constraints: - 1 <= operations.length <= 1000 - operations[i] is "C", "D", "+", or a string representing an integer in the range [-3 * 10^4, 3 * 10^4]. - 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.

---

🌟 ELI5: The Simple Idea!

Think of a scorekeeper with special rules:

Normal score: Write it down
  "5" → Record: [5]

Plus (+): Add last two scores
  "+" → Record: [5, 10] → Add 5+10=15 → [5, 10, 15]

Double (D): Double the last score
  "D" → Record: [5] → Add 5×2=10 → [5, 10]

Cancel (C): Erase last score
  "C" → Record: [5, 10] → Remove 10 → [5]

Why Stack?

All operations work with:
  - Most recent score
  - Two most recent scores

This is LIFO = Stack!

Operations:
  Number → Push
  "D"    → Push (peek × 2)
  "+"    → Push (peek + peek-1)
  "C"    → Pop

---

🎨 Visual Understanding

Example Walkthrough

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

═══════════════════════════════════════════════════════════════
Step-by-Step
═══════════════════════════════════════════════════════════════

Operation: "5"
  Parse: Integer 5
  Action: Add 5
  Stack: [5]

Operation: "2"
  Parse: Integer 2
  Action: Add 2
  Stack: [5, 2]

Operation: "C"
  Parse: Cancel command
  Action: Remove last score
  Stack: [5]
  Removed: 2

Operation: "D"
  Parse: Double command
  Action: Double last score (5 × 2 = 10)
  Stack: [5, 10]

Operation: "+"
  Parse: Plus command
  Action: Sum last two scores (5 + 10 = 15)
  Stack: [5, 10, 15]

═══════════════════════════════════════════════════════════════
Final Result
═══════════════════════════════════════════════════════════════

Sum all scores in stack:
  5 + 10 + 15 = 30 ✓

---

🎯 Approach: Stack with Number Tracking ⭐

The Optimal Solution

Algorithm:

1. Create stack to store valid scores
2. For each operation:
   - If number: push to stack
   - If "C": pop from stack
   - If "D": push (top × 2)
   - If "+": push (top + second)
3. Sum all values in stack

Implementation

/**
 * Stack-based score tracking
 * Time: O(n), Space: O(n)
 */
public int calPoints(String[] operations) {
    Stack<Integer> stack = new Stack<>();

    for (String op : operations) {
        if (op.equals("C")) {
            // Cancel: remove last score
            stack.pop();

        } else if (op.equals("D")) {
            // Double: add double of last score
            stack.push(2 * stack.peek());

        } else if (op.equals("+")) {
            // Plus: add sum of last two scores
            int top = stack.pop();
            int sum = top + stack.peek();
            stack.push(top);  // Put back
            stack.push(sum);

        } else {
            // Number: add to record
            stack.push(Integer.parseInt(op));
        }
    }

    // Sum all scores
    int total = 0;
    for (int score : stack) {
        total += score;
    }

    return total;
}

⏰ Time: O(n) - Process each operation once, then sum
💾 Space: O(n) - Stack stores valid scores

Cleaner "+" Implementation

// Alternative for "+" operation
else if (op.equals("+")) {
    int second = stack.get(stack.size() - 2);
    int top = stack.peek();
    stack.push(top + second);
}

Using get() to peek second element without popping!

🔍 Super Detailed Dry Run

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

Goal: Calculate final sum after all operations

═══════════════════════════════════════════════════════════════
Initialization
═══════════════════════════════════════════════════════════════

stack = []

═══════════════════════════════════════════════════════════════
Iteration 1: op = "5"
═══════════════════════════════════════════════════════════════

Check operation type:
  Not "C", not "D", not "+"
  → Must be a number

Action: Parse and push
  Integer.parseInt("5") = 5
  stack.push(5)

Stack: [5]

═══════════════════════════════════════════════════════════════
Iteration 2: op = "2"
═══════════════════════════════════════════════════════════════

Check: Number

Action: Push 2
  stack.push(2)

Stack: [5, 2]

═══════════════════════════════════════════════════════════════
Iteration 3: op = "C"
═══════════════════════════════════════════════════════════════

Check: Equals "C"
  → Cancel operation

Action: Remove last score
  stack.pop() → removes 2

Stack: [5]

═══════════════════════════════════════════════════════════════
Iteration 4: op = "D"
═══════════════════════════════════════════════════════════════

Check: Equals "D"
  → Double operation

Action: Double last score
  stack.peek() = 5
  5 × 2 = 10
  stack.push(10)

Stack: [5, 10]

═══════════════════════════════════════════════════════════════
Iteration 5: op = "+"
═══════════════════════════════════════════════════════════════

Check: Equals "+"
  → Plus operation (sum last two)

Action: Sum last two scores
  Method 1 (pop and push back):
    top = stack.pop() = 10
    stack: [5]

    sum = top + stack.peek()
        = 10 + 5
        = 15

    stack.push(top) → push 10 back
    stack: [5, 10]

    stack.push(sum) → push 15
    stack: [5, 10, 15]

Stack: [5, 10, 15]

═══════════════════════════════════════════════════════════════
Calculate Sum
═══════════════════════════════════════════════════════════════

Sum all values in stack:
  total = 0

  for (int score : stack):
    Iteration 1: score = 5, total = 0 + 5 = 5
    Iteration 2: score = 10, total = 5 + 10 = 15
    Iteration 3: score = 15, total = 15 + 15 = 30

Final total: 30 ✓

Return: 30

Example 2: ops = ["5","-2","4","C","D","9","+","+"]

Operation: "5"    → Stack: [5]
Operation: "-2"   → Stack: [5, -2]
Operation: "4"    → Stack: [5, -2, 4]
Operation: "C"    → Stack: [5, -2]         (removed 4)
Operation: "D"    → Stack: [5, -2, -4]     (-2 × 2 = -4)
Operation: "9"    → Stack: [5, -2, -4, 9]
Operation: "+"    → Stack: [5, -2, -4, 9, 5]   (-4 + 9 = 5)
Operation: "+"    → Stack: [5, -2, -4, 9, 5, 14]   (9 + 5 = 14)

Sum: 5 + (-2) + (-4) + 9 + 5 + 14 = 27 ✓

---

🎯 Why This Solution Works

The Stack Insight

All operations reference most recent scores:
  "D" → Last score
  "+" → Last TWO scores
  "C" → Remove last score

Stack provides:
  ✓ O(1) access to most recent (peek)
  ✓ O(1) access to second recent (get or pop/push)
  ✓ O(1) add score (push)
  ✓ O(1) remove score (pop)

Perfect fit!

Operation Breakdown

1. NUMBER:
   Just add to record
   → stack.push(num)

2. "C" (Cancel):
   Remove most recent
   → stack.pop()

3. "D" (Double):
   Get most recent, double it, add
   → stack.push(2 * stack.peek())

4. "+" (Plus):
   Get last two, sum them, add
   → Need top and second-to-top
   → Pop, peek, push back, push sum
   OR
   → Use get(size-2) to avoid pop

Why Not Array?

Array issues:
  ✗ Need to track size
  ✗ Manual index management
  ✗ More error-prone

Stack benefits:
  ✓ Automatic size tracking
  ✓ Built-in operations
  ✓ Cleaner code

---

🎯 Alternative Approaches

Approach 1: Using ArrayList

public int calPoints(String[] operations) {
    List<Integer> scores = new ArrayList<>();

    for (String op : operations) {
        int n = scores.size();

        if (op.equals("C")) {
            scores.remove(n - 1);
        } else if (op.equals("D")) {
            scores.add(2 * scores.get(n - 1));
        } else if (op.equals("+")) {
            scores.add(scores.get(n - 1) + scores.get(n - 2));
        } else {
            scores.add(Integer.parseInt(op));
        }
    }

    return scores.stream().mapToInt(Integer::intValue).sum();
}

Why ArrayList works: - Can access by index easily - get(n-2) for second-to-last

Stack is still cleaner for this problem!

Approach 2: Manual Array

public int calPoints(String[] operations) {
    int[] scores = new int[operations.length];
    int index = 0;  // Current position

    for (String op : operations) {
        if (op.equals("C")) {
            index--;
        } else if (op.equals("D")) {
            scores[index] = 2 * scores[index - 1];
            index++;
        } else if (op.equals("+")) {
            scores[index] = scores[index - 1] + scores[index - 2];
            index++;
        } else {
            scores[index] = Integer.parseInt(op);
            index++;
        }
    }

    int sum = 0;
    for (int i = 0; i < index; i++) {
        sum += scores[i];
    }
    return sum;
}

More error-prone but O(1) space overhead!

---

⚠️ Common Mistakes

Mistake 1: Forgetting to push back when using "+"

// ❌ WRONG - Lost the top value!
int top = stack.pop();
int sum = top + stack.peek();
stack.push(sum);  // Forgot to push top back!

// ✓ CORRECT - Push top back first
int top = stack.pop();
int sum = top + stack.peek();
stack.push(top);  // Put it back!
stack.push(sum);

Mistake 2: Wrong order for "+"

// ❌ WRONG - Order matters for debugging
int sum = stack.peek() + stack.pop();
// peek happens before pop, confusing!

// ✓ CORRECT - Clear order
int top = stack.pop();
int sum = top + stack.peek();
stack.push(top);
stack.push(sum);

Mistake 3: Not handling negative numbers

// ❌ WRONG - Assumes all numbers positive
if (op.equals("-")) {  // Trying to detect negative

// ✓ CORRECT - Parse handles negatives
Integer.parseInt(op);  // Works for "-2", "5", etc.

Mistake 4: String comparison error

// ❌ WRONG - Using == for strings
if (op == "C") {  // Reference comparison!

// ✓ CORRECT - Use .equals()
if (op.equals("C")) {

Mistake 5: Not summing at end

// ❌ WRONG - Returning stack size
return stack.size();

// ✓ CORRECT - Sum all values
int sum = 0;
for (int score : stack) {
    sum += score;
}
return sum;

---

🎯 Pattern Recognition

Problem Type: Number Stack with Operations
Core Pattern: Stack Pattern 3 - Number Stack

When to Apply:
✓ Track scores/numbers
✓ Operations on recent values
✓ Add/remove/modify based on history
✓ Game simulation with stack-like rules

Recognition Keywords:
- "score"
- "record"
- "operations"
- "previous score(s)"
- "double", "sum", "cancel"

Similar Problems:
- Evaluate Reverse Polish Notation (LC 150)
- Basic Calculator (LC 224, 227)
- Crawler Log Folder (LC 1598)
- Removing Stars From String (LC 2390)

Key Components:
┌────────────────────────────────────────────┐
│ Stack: Store valid scores                 │
│ Number: Push to stack                     │
│ "C": Pop (cancel)                         │
│ "D": Push (peek × 2)                      │
│ "+": Push (top + second)                  │
│ Sum: All values at end                    │
│ Time: O(n), Space: O(n)                   │
└────────────────────────────────────────────┘

---

🧠 Interview Strategy

Step 1: "This is a stack-based simulation problem"
Step 2: "I'll use a stack to track valid scores"
Step 3: "Process each operation, then sum"

Key Points to Mention:
- Stack stores only valid scores (after cancellations)
- Each operation works on most recent score(s)
- "C" removes, "D" doubles, "+" sums last two
- Final answer is sum of all remaining scores
- Time: O(n), Space: O(n)

Walk Through Example:
"For ['5','2','C','D','+']:
 '5' → Push 5: [5]
 '2' → Push 2: [5, 2]
 'C' → Remove 2: [5]
 'D' → Double 5, add 10: [5, 10]
 '+' → Sum 5+10, add 15: [5, 10, 15]
 Sum: 5+10+15 = 30"

Why Stack:
"All operations reference recent scores.
 Stack gives O(1) access to most recent.
 Natural fit for LIFO operations."

Edge Cases to Mention:
✓ Negative numbers in input
✓ Multiple consecutive operations
✓ All scores canceled (empty stack)
✓ Operations that reduce stack size

---

📝 Quick Revision Notes

🎯 Core Concept:

Baseball Game: Use stack to track valid scores. Number → push. "C" → pop (cancel). "D" → push (peek × 2). "+" → push (top + second). At end, sum all values in stack. Handle negative numbers with Integer.parseInt().

⚡ Quick Implementation:

import java.util.Stack;

class Solution {
  public int calPoints(String[] operations) {
    Stack<Integer> s = new Stack<>();
    int res = 0;

    for(String op : operations) {
      switch (op) {
        case "+":
          int temp1 = s.pop();
          int temp2 = s.pop();
          s.push(temp2);
          s.push(temp1);
          s.push(temp1 + temp2);
          break;
        case "D":
          s.push(s.peek() * 2);
          break;
        case "C":
          s.pop();
          break;                
        default:
          s.push(Integer.parseInt(op));
          break;
      }
    }

    for(int num : s) {
      res += num;
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.calPoints(new String[] {"5","2","C","D","+"}) == 30);
    System.out.println(s.calPoints(new String[] {"5","-2","4","C","D","9","+","+"}) == 27);
  }
}

🔑 Key Insights:

• Pattern: Stack Pattern 3 (Number Stack)
• Operations: All on most recent value(s)
• "+" tricky: Pop, sum, push back, push sum
• Negative: Integer.parseInt() handles it
• Final step: Sum all remaining values
• Time: O(n), Space: O(n) ✓

🎪 Memory Aid:

"Push numbers, pop for C, double for D, sum for +!"
"Number push, C pop, D double, + sum!" ✨

⚠️ Critical Detail:

For "+" operation:

❌ WRONG:
int top = stack.pop();
int sum = top + stack.peek();
stack.push(sum);  // Lost top!

✓ CORRECT:
int top = stack.pop();
int sum = top + stack.peek();
stack.push(top);   // Push back!
stack.push(sum);   // Then sum

OR use get():
int second = stack.get(stack.size() - 2);
int sum = stack.peek() + second;
stack.push(sum);

---

🧪 Edge Cases

Case 1: All canceled

Input: ops = ["5","C"]
Output: 0
Stack empty at end

Case 2: Negative numbers

Input: ops = ["5","-2","4"]
Output: 7
Handles negative correctly

Case 3: Multiple "+" operations

Input: ops = ["1","2","+","+"]
Output: 9
1, 2, 3(1+2), 5(2+3)
Sum: 1+2+3+5 = 11
Wait, let me recalculate...
[1], [1,2], [1,2,3], [1,2,3,5]
Sum: 1+2+3+5 = 11

Case 4: "D" after "C"

Input: ops = ["5","2","C","D"]
Output: 15
5, 2, cancel 2, double 5 → 10
Sum: 5+10 = 15

All handled correctly! ✓

---

🎓 Complexity Analysis

Time Complexity: O(n)

Process operations: O(n)
  for (String op : operations)  // n iterations
  Each operation: O(1)

Sum scores: O(k) where k ≤ n
  for (int score : stack)

Total: O(n) + O(k) = O(n) ✓

Space Complexity: O(n)

Stack space:
  Worst case: all operations add scores
  Example: ["1","2","3","4","5"]
  Stack stores n values

Total: O(n) ✓

---

📚 Related Problems

Same Pattern: - Crawler Log Folder (LC 1598) - Similar with "../", "./", "x/" - Build Array With Stack Operations (LC 1441)

Number Stack Pattern: - Evaluate RPN (LC 150) - More complex operations - Basic Calculator (LC 224, 227) - Full expressions

Simulation: - Design a Stack With Increment (LC 1381)

---

Happy practicing! 🎯

Note: This problem teaches Stack Pattern 3: Number Stack! Master this and you understand: (1) stack for number tracking, (2) operations on most recent values, (3) simulation with stack rules. The key insight: all operations work on most recent score(s) = perfect for stack! This pattern appears in calculator problems and game simulations. 💪✨