Cash Register Log
EasyStack
Problem
A shop's register writes a log of commands in ops. Each command is one of:
- an integer such as "12" or "-3": record a new entry with that amount;
- "VOID": delete the most recent entry still on the receipt;
- "REPEAT": record a new entry equal to the most recent entry;
- "COMBO": record a new entry equal to the sum of the two most recent entries.
Return the sum of all entries left on the receipt after every command has run. The log is always valid: VOID and REPEAT only appear when at least one entry exists, COMBO only when at least two exist.
Example 1
- Input:
- ops = ["5", "-2", "REPEAT", "COMBO", "VOID", "10"]
- Output:
- 11
Entries: 5, -2, -2 (repeat), -4 (combo of -2 and -2), the void removes -4, then 10. Sum 5 - 2 - 2 + 10 = 11.
Example 2
- Input:
- ops = ["3", "VOID", "7", "4", "COMBO"]
- Output:
- 22
Entries end as 7, 4, 11.
Constraints
- 1 ≤ ops.length ≤ 1000
- Integer commands are in [-3·10^4, 3·10^4]
- Every intermediate value fits in a 32-bit signed integer
Hint
Show the first hint
Every command only ever looks at, or removes, the most recent entries.
Walkthrough
How to approach it
01Clarify before coding
- Can a VOID remove an entry created by REPEAT or COMBO? Yes, every recorded entry is an ordinary entry.
- Does VOID affect earlier commands retroactively? No, it simply deletes the current most recent entry.
- Can amounts be negative? Yes; parse them with the sign.
02Brute force
Keep all entries in a list and recompute the needed values by scanning; there is no really slower naive approach here — the challenge is choosing the right structure.
Cost: A stack-backed list already gives O(n). Re-summing the receipt after every command would cost O(n²) for nothing.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.