algoadvance

Leetcode 682. Baseball Game

Problem Statement

You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds’ scores.

At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply sequentially to the record and it 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 the double of 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.

Example

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record -> [5]
"2" - Add 2 to the record -> [5, 2]
"C" - Invalidate and remove the previous score -> [5]
"D" - Add 2 * 5 to the record -> [5, 10]
"+" - Add 5 + 10 to the record -> [5, 10, 15]
The sum is 5 + 10 + 15 = 30

Constraints

Clarifying Questions

  1. Are we guaranteed that the input operations follow the constraints strictly? For instance, whenever we encounter a "+" operation, there will be at least two scores before it.
    • Yes, the input will always follow the constraints strictly.

Strategy

  1. Use a vector or stack to maintain the record of scores.
  2. Iterate through the operations and apply the corresponding logic based on the operation type.
  3. For each integer in the list, push it to the record.
  4. For "+", push the sum of the last two scores in the record.
  5. For "D", push the double of the last score in the record.
  6. For "C", pop the last score from the record.
  7. After processing all operations, sum the scores in the record and return the result.

Code

#include <vector>
#include <string>
#include <numeric> // for accumulate
using namespace std;

class Solution {
public:
    int calPoints(vector<string>& ops) {
        vector<int> record;
        for (const string& op : ops) {
            if (op == "C") {
                record.pop_back();
            } else if (op == "D") {
                record.push_back(2 * record.back());
            } else if (op == "+") {
                record.push_back(record[record.size() - 1] + record[record.size() - 2]);
            } else {
                record.push_back(stoi(op));
            }
        }
        // Calculate the sum of the elements in the record.
        return accumulate(record.begin(), record.end(), 0);
    }
};

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of operations in the ops list. This is because we are iterating through the list of operations once and each operation is processed in constant time.

Explanation

  1. Initialize an empty vector record to keep track of the scores.
  2. Iterate over each operation in the ops list:
    • If the operation is a valid integer, convert it to an integer and push it to the record.
    • If the operation is "C", remove the last score from the record.
    • If the operation is "D", push the double of the last score in the record.
    • If the operation is "+", push the sum of the last two scores in the record.
  3. Use std::accumulate to sum all the scores in the record and return the result.

This solution efficiently handles all the rules specified in the problem statement and respects all constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI