DSA problem
Baseball Game
You are keeping the scores for a baseball game with strange rules. The game consists of several rounds, and the scores of past rounds may affect future rounds. At the beginning of the game, you start with an empty record.
You are given a list of strings operations, where each operations[i] is one of four possible operations: an integer x (record a new score of x), "+" (record a new score equal to the sum of the previous two scores), "D" (record a new score equal to double the previous score), or "C" (the previous score was invalid — remove it from the record).
After applying every operation in order, return the sum of all the scores currently on the record. Notice how each "+" and "D" depends only on the most recent score(s), which suggests a stack-like structure where you only ever interact with the top.
The clean solution is to maintain a stack of integers. For an integer push it; for "+" peek the top two scores and push their sum; for "D" peek the top score and push twice that value; for "C" pop the top score. After every operation has been processed, sum the contents of the stack and return that sum. This single-pass approach runs in O(n) time and O(n) space, where n is the number of operations.
Examples
ops = ["5","2","C","D","+"]30ops = ["5","-2","4","C","D","9","+","+"]27ops = ["1","C"]0Constraints
- 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 "+", there will always be at least two previous scores on the record.
- For "C" and "D", there will always be at least one previous score on the record.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.