321. Cancel Zero Runs
A bank's ledger is a chain of nodes, each holding a signed amount: positive for a deposit, negative for a withdrawal. An auditor discards any block of consecutive entries whose amounts add up to exactly 0, because such a block changes nothing. A single entry equal to 0 is also such a block.
Repeat the following until no block of consecutive nodes sums to zero: among all zero-sum blocks, choose the one that starts earliest in the chain (if several start there, the longest one) and remove it from the chain. Return the head of the final chain. The final chain is uniquely determined by this rule. A chain can have up to 100,000 nodes, so testing every block one by one is too slow.
Example 1
- Input:
- head = [6,-2,-4,9,-1,1,5]
- Output:
- [9,5]
- Explanation:
The block 6, -2, -4 sums to 0 and starts first, so it goes. In [9, -1, 1, 5] the block -1, 1 sums to 0 and goes too. Result: [9, 5].
Example 2
- Input:
- head = [5,-5,5,-5,3]
- Output:
- [3]
- Explanation:
Two blocks start at the first node: [5, -5] and [5, -5, 5, -5]. The longer one is removed, leaving [3].
Constraints
0 ≤ chain length ≤ 105
-1000 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)