Replay a Score Log With Undo and Combine Commands
Solve this Problemops, replay them in order to build a log of scores and return the sum of every score remaining in the log once all commands have run. Each command is either a signed integer (record that score), "+" (record the sum of the two most recent scores), "X2" (record double the most recent score), or "UNDO" (erase the most recently recorded score).
Every command here only ever touches the most recent end of the log — new scores go on top, and undo removes from the top — which is exactly what a stackStackA LIFO (Last In, First Out) structure — the natural fit whenever an operation only ever needs to read or remove the most recently added item. is built for. The only question is how to track the running total efficiently: re-deriving it from the whole log after every command works, but wastes effort re-reading scores that didn't change; updating it by exactly the one value that was just added or removed keeps every command O(1).
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ ops.length ≤ 12 - ◆
Each entry in ops is a signed integer string, or one of the commands "+", "X2", "UNDO" - ◆
"+" is only ever given when at least 2 prior scores exist in the log; "X2" and "UNDO" only when at least 1 does - ◆
-100 ≤ any integer score or computed value ≤ 200
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recompute the Total From Scratch Every Time
BruteKeep a running log of every score. For each operation, update the log (append a new integer, append the sum of the last two entries for "+", append double the last entry for "X2", or remove the last entry for "UNDO"), then re-sum the entire log from scratch to get the current total. Correct, but re-summing a log of size k costs O(k), and that happens after every one of the n operations — O(n²) total, even though most operations only actually change one entry.
O(n²)O(n)1class Solution {
2 public int replayScoreLog(String[] ops) {
3 List<Integer> log = new ArrayList<>();
4 int total = 0;
5 for (String op : ops) {
6 if (op.equals("+")) {
7 log.add(log.get(log.size() - 1) + log.get(log.size() - 2));
8 } else if (op.equals("X2")) {
9 log.add(log.get(log.size() - 1) * 2);
10 } else if (op.equals("UNDO")) {
11 log.remove(log.size() - 1);
12 } else {
13 log.add(Integer.parseInt(op));
14 }
15 total = 0;
16 for (int v : log) total += v;
17 }
18 return total;
19 }
20}Optimal — Maintain a Running Total Incrementally
OptimalEvery operation only ever adds or removes exactly one entry from the log, and that entry's value is known the moment the operation happens — there's no need to ever re-scan the whole log. Track a running total alongside it: add the new entry's value when appending, subtract it when undoing. Each operation becomes O(1) instead of O(size of log), for O(n) total.
O(n)O(n)1class Solution {
2 public int replayScoreLog(String[] ops) {
3 Deque<Integer> log = new ArrayDeque<>();
4 int total = 0;
5 for (String op : ops) {
6 if (op.equals("+")) {
7 int a = log.pop();
8 int b = log.peek();
9 log.push(a);
10 int sum = a + b;
11 log.push(sum);
12 total += sum;
13 } else if (op.equals("X2")) {
14 int doubled = log.peek() * 2;
15 log.push(doubled);
16 total += doubled;
17 } else if (op.equals("UNDO")) {
18 total -= log.pop();
19 } else {
20 int v = Integer.parseInt(op);
21 log.push(v);
22 total += v;
23 }
24 }
25 return total;
26 }
27}