465 - Optimal Account Balancing
Written on February 2, 2020
Tweet
A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill’s lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person’s ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]]. Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
from collections import defaultdict
class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
value_map = defaultdict(int)
for a, b, c in transactions:
value_map[a] -= c
value_map[b] += c
debts = list(value_map.values())
def dfs(start):
while start < len(debts) and debts[start] == 0:
start += 1
if start == len(debts):
return 0
ret = float("inf")
for i in range(start + 1, len(debts)):
if debts[i] * debts[start] < 0:
debts[i] += debts[start]
ret = min(ret, dfs(start + 1) + 1)
debts[i] -= debts[start]
return ret
return dfs(0)