465. Optimal Account Balancing

Problem

Given a list of transactions as a list of triplets: (a, b, c), meaning a give b an amount of c dollars. Now we want to settle all the debt with the minimum number of transactions. For example, (0, 1, 5) (1, 2, 5) can be settled with one transaction (2, 0, 5). We only need return one integer: the minimum number of transactions needed.

Solution

We don't need to consider the transaction graph. Imagine during settling the debt, everyone who need to return money to others just put those money in a pool. The people who should receive money from others just take from that pool. After this, all debt are settled without knowing the original transaction graph.

First, we calculate how much money each person owns (can be positive or negative). Then, we just use DFS to settle the debt. One person will return all his debt to another person. The DFS will search every choice of choosing the person. Then we start to search the choices of the next person.

One concern is, what if the optimal solution is not for a person returning all his debt to another person, but returning his debt to multiple people? We can always find an equivalent case in our search space. For example, if the optimial solution is for a return money to b and to c. We can find a equivalent in our search space for a to return all the money to b, and b will return the extra amount to c. The 2 solutions both take 2 transactions to fiinsh.

Code

import collections


class Solution:
  def __init__(self, *args, **kwargs):
    super().__init__(*args, **kwargs)
    self.num_people = 0
    self.debt = []

  def cal_debt(self, transactions):
    temp = collections.defaultdict(lambda : 0)
    for transaction in transactions:
      temp[transaction[0]] += transaction[2]
      temp[transaction[1]] -= transaction[2]
    for key, value in temp.items():
      self.debt.append(value)
    self.num_people = len(self.debt)

  def dfs(self, current_id):
    while (current_id < self.num_people and 
      self.debt[current_id] == 0):
      current_id += 1
    if current_id >= self.num_people:
      return 0
    ret = self.num_people * self.num_people
    for next_id in range(current_id + 1, self.num_people):
      if self.debt[current_id] * self.debt[next_id] < 0:
        self.debt[next_id] += self.debt[current_id]
        ret = min(ret, self.dfs(current_id + 1) + 1)
        self.debt[next_id] -= self.debt[current_id]
    return ret

  def minTransfers(self, transactions: List[List[int]]) -> int:          
    self.cal_debt(transactions)
    return self.dfs(0)