Baseball Game
Easy · Stack · Explanation and code example
Stack - II
How it works
This approach is similar to the first one, but we maintain a running total as we process operations instead of computing the sum at the end. Whenever we add a score, we add it to our result. When we remove a score with C, we subtract it. This gives us the same answer but avoids a final pass through the stack.
Steps
- Initialize an empty stack and a result variable set to
0. - For each operation:
- If it's
+, calculate the sum of the top two elements, push it, and add to result. - If it's
D, calculate double the top element, push it, and add to result. - If it's
C, pop the top element and subtract it from result. - Otherwise, parse the number, push it, and add to result.
- If it's
- Return the result.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Things to watch for
Forgetting to Convert String to Integer
When the operation is a number, it comes as a string. Forgetting to parse it as an integer causes type errors or incorrect arithmetic.
Accessing Stack Elements in Wrong Order for "+"
The + operation requires adding the last two scores. When popping, the first pop gives the most recent score, and the second pop gives the one before it. Getting this order confused can lead to wrong results when the operation depends on position.
Python code example
from typing import List
class Solution:
def calPoints(self, operations: List[str]) -> int:
stack, res = [], 0
for op in operations:
if op == "+":
res += stack[-1] + stack[-2]
stack.append(stack[-1] + stack[-2])
elif op == "D":
res += (2 * stack[-1])
stack.append(2 * stack[-1])
elif op == "C":
res -= stack.pop()
else:
res += int(op)
stack.append(int(op))
return res
C++ code example
class Solution {
public:
int calPoints(vector<string>& ops) {
stack<int> stack;
int res = 0;
for (const string& op : ops) {
if (op == "+") {
int top = stack.top(); stack.pop();
int newTop = top + stack.top();
stack.push(top);
stack.push(newTop);
res += newTop;
} else if (op == "D") {
stack.push(2 * stack.top());
res += stack.top();
} else if (op == "C") {
res -= stack.top();
stack.pop();
} else {
stack.push(stoi(op));
res += stack.top();
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.