You are building a daily ledger service.
A transaction record has three fields: timestamp, user_id, and delta_amount. delta_amount can be positive or negative and represents how that user's balance changes during the day. All amounts are integers.
-
Given a list of transaction records for a single day, compute each user's end-of-day net balance, assuming every user's starting balance is 0.
-
Using the resulting balances, generate a settlement plan with the minimum possible number of transfers so that every user's final balance becomes 0. A user with a negative balance must pay money, and a user with a positive balance must receive money. Each settlement transfer should be represented as
(from_user, to_user, amount)
.
Notes:
-
Users whose balance is 0 do not need to appear in the settlement plan.
-
You may assume the sum of all balances is 0.
-
For the exact-minimum settlement part, assume the number of users with non-zero balance is small enough to permit an exponential-search solution if needed.