465. Optimal Account Balancing

# 1. Record all balances after transactions
# 2. Keep only the non-zero balances in a list
# 3. We know the sum of this list is 0, so at most we'll have n-1 transactions.
# Goal is to create minimum number of transactions between positive and negative balances to reach 0 sum
# So let's try recursively evaluating every possibility in the transaction graph, via DFS
# at balance i, try to transact with every eligible subsequent balance (opposite sign) from i+1 to n, recurse
# backtrack afterwards
# TC: O((n-1)!)
# SC: O(n)

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        balances = defaultdict(int)

        for tx in transactions:
            payer, payee, amount = tx
            balances[payer] += amount
            balances[payee] -= amount

        balance_list = [v for v in balances.values() if v != 0]
        n = len(balance_list)

        def dfs(cur):
            while cur < n and balance_list[cur] == 0:
                cur += 1

            if cur == n:
                return 0

            txs = float('inf')
            for nxt in range(cur+1, n):
                if balance_list[nxt] * balance_list[cur] < 0:
                    balance_list[nxt] += balance_list[cur]
                    txs = min(txs, 1 + dfs(cur + 1))
                    balance_list[nxt] -= balance_list[cur]

            return txs

        return dfs(0)




# Approach 2: BFS
# compared to DFS, this will save some time since BFS won't evaluate paths that take more moves than absolute minimum
# however, you will need to keep copies of the state (balance list) instead of re-using the same state as in backtracking
# So trading off memory for time
# TC: O((N-1)!), same as DFS but won't evaluate more paths than necessary
# SC: Let M be min number of transactions. widest point of graph is at level M, where we have (N-1)(N-2)...(N-M) * N which reduces to O(N^(M+1))

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        balances = defaultdict(int)

        for tx in transactions:
            payer, payee, amount = tx
            balances[payer] += amount
            balances[payee] -= amount

        balance_list = [v for v in balances.values() if v != 0]
        n = len(balance_list)

        queue = deque([(0, 0, balance_list.copy())]) # moves, cur_idx, state

        while queue:
            moves, cur_idx, bal_state = queue.popleft()
            if cur_idx == n:
                return moves

            for tx_target in range(cur_idx + 1, n):
                if bal_state[tx_target] * bal_state[cur_idx] >= 0: #opposite sign only
                    continue

                new_bal_state = bal_state.copy()
                new_bal_state[tx_target] += new_bal_state[cur_idx]
                nxt = cur_idx + 1

                while nxt < n and new_bal_state[nxt] == 0:
                    nxt += 1

                queue.append((moves+1, nxt, new_bal_state))

        return -1


# More optimized BFS: Since we are progressively moving our current_idx pointer forward, we don't care about
# what's behind the it. So don't copy more balanace_state than necessary

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        balances = defaultdict(int)

        for tx in transactions:
            payer, payee, amount = tx
            balances[payer] += amount
            balances[payee] -= amount

        balance_list = [v for v in balances.values() if v != 0]
        n = len(balance_list)

        queue = deque([(0, balance_list.copy())]) # moves, state

        while queue:
            moves, bal_state = queue.popleft()
            if not bal_state:
                return moves

            for tx_target in range(1, len(bal_state)):
                if bal_state[tx_target] * bal_state[0] >= 0: #opposite sign only
                    continue

                bal_state[tx_target] += bal_state[0]
                nxt = 1

                while nxt < len(bal_state) and bal_state[nxt] == 0:
                    nxt += 1

                queue.append((moves+1, bal_state[nxt:].copy()))
                bal_state[tx_target] -= bal_state[0]

        return -1