Chain Reorg Balances
EasyStack · Coinbase
A wallet indexer receives blocks in arrival order. Each element of blocks is [height, transfers], where transfers is a list of [account, amount] balance changes (amounts may be negative).
The chain starts empty, so the first block has height 1. Let tip be the height of the current last block. Each arriving block has 1 <= height <= tip + 1:
- If
height == tip + 1, the block extends the chain. - If
height <= tip, a reorg happened: every block currently at heightheightor above is discarded and its transfers are undone, and then the new block is added atheight(it becomes the new tip).
A balance is the sum of the transfer amounts for that account across the blocks currently on the chain. Return [account, balance] for every account whose final balance is nonzero, sorted by account name.
Example 1
- Input:
- blocks = [[1, [["alice", 50]]], [2, [["alice", -20], ["bob", 20]]], [3, [["bob", 5]]], [2, [["carol", 7]]]]
- Output:
- [["alice", 50], ["carol", 7]]
- Explanation
- Blocks 1 to 3 build the chain. The second block at height 2 is a reorg: the old blocks at heights 2 and 3 are undone, and the new block becomes the tip. Only alice's 50 and carol's 7 remain on the chain.
Example 2
- Input:
- blocks = [[1, [["dan", 10]]], [1, [["erin", 4]]], [2, [["dan", 3]]]]
- Output:
- [["dan", 3], ["erin", 4]]
- Explanation
- The second height-1 block replaces the first, so dan's 10 is undone. dan only receives the 3 from the block at height 2.
Example 3
- Input:
- blocks = [[1, [["x", 5], ["x", -5]]], [2, []]]
- Output:
- []
- Explanation
- x nets to 0, so it is left out of the result. An empty block is still a valid block.
Constraints
0 <= blocks.length <= 10^51 <= height <= tip + 1for every block- The total number of transfers is at most
2 * 10^5 -10^9 <= amount <= 10^9