# 465. Optimal Account Balancing

Mar 3rd, 2024 (edited)
640
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # 1. Record all balances after transactions
2. # 2. Keep only the non-zero balances in a list
3. # 3. We know the sum of this list is 0, so at most we'll have n-1 transactions.
4. # Goal is to create minimum number of transactions between positive and negative balances to reach 0 sum
5. # So let's try recursively evaluating every possibility in the transaction graph, via DFS
6. # at balance i, try to transact with every eligible subsequent balance (opposite sign) from i+1 to n, recurse
7. # backtrack afterwards
8. # TC: O((n-1)!)
9. # SC: O(n)
10.
11. class Solution:
12.     def minTransfers(self, transactions: List[List[int]]) -> int:
13.         balances = defaultdict(int)
14.
15.         for tx in transactions:
16.             payer, payee, amount = tx
17.             balances[payer] += amount
18.             balances[payee] -= amount
19.
20.         balance_list = [v for v in balances.values() if v != 0]
21.         n = len(balance_list)
22.
23.         def dfs(cur):
24.             while cur < n and balance_list[cur] == 0:
25.                 cur += 1
26.
27.             if cur == n:
28.                 return 0
29.
30.             txs = float('inf')
31.             for nxt in range(cur+1, n):
32.                 if balance_list[nxt] * balance_list[cur] < 0:
33.                     balance_list[nxt] += balance_list[cur]
34.                     txs = min(txs, 1 + dfs(cur + 1))
35.                     balance_list[nxt] -= balance_list[cur]
36.
37.             return txs
38.
39.         return dfs(0)
40.
41.
42.
43.
44. # Approach 2: BFS
45. # compared to DFS, this will save some time since BFS won't evaluate paths that take more moves than absolute minimum
46. # however, you will need to keep copies of the state (balance list) instead of re-using the same state as in backtracking
47. # So trading off memory for time
48. # TC: O((N-1)!), same as DFS but won't evaluate more paths than necessary
49. # 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))
50.
51. class Solution:
52.     def minTransfers(self, transactions: List[List[int]]) -> int:
53.         balances = defaultdict(int)
54.
55.         for tx in transactions:
56.             payer, payee, amount = tx
57.             balances[payer] += amount
58.             balances[payee] -= amount
59.
60.         balance_list = [v for v in balances.values() if v != 0]
61.         n = len(balance_list)
62.
63.         queue = deque([(0, 0, balance_list.copy())]) # moves, cur_idx, state
64.
65.         while queue:
66.             moves, cur_idx, bal_state = queue.popleft()
67.             if cur_idx == n:
68.                 return moves
69.
70.             for tx_target in range(cur_idx + 1, n):
71.                 if bal_state[tx_target] * bal_state[cur_idx] >= 0: #opposite sign only
72.                     continue
73.
74.                 new_bal_state = bal_state.copy()
75.                 new_bal_state[tx_target] += new_bal_state[cur_idx]
76.                 nxt = cur_idx + 1
77.
78.                 while nxt < n and new_bal_state[nxt] == 0:
79.                     nxt += 1
80.
81.                 queue.append((moves+1, nxt, new_bal_state))
82.
83.         return -1
84.
85.
86. # More optimized BFS: Since we are progressively moving our current_idx pointer forward, we don't care about
87. # what's behind the it. So don't copy more balanace_state than necessary
88.
89. class Solution:
90.     def minTransfers(self, transactions: List[List[int]]) -> int:
91.         balances = defaultdict(int)
92.
93.         for tx in transactions:
94.             payer, payee, amount = tx
95.             balances[payer] += amount
96.             balances[payee] -= amount
97.
98.         balance_list = [v for v in balances.values() if v != 0]
99.         n = len(balance_list)
100.
101.         queue = deque([(0, balance_list.copy())]) # moves, state
102.
103.         while queue:
104.             moves, bal_state = queue.popleft()
105.             if not bal_state:
106.                 return moves
107.
108.             for tx_target in range(1, len(bal_state)):
109.                 if bal_state[tx_target] * bal_state[0] >= 0: #opposite sign only
110.                     continue
111.
112.                 bal_state[tx_target] += bal_state[0]
113.                 nxt = 1
114.
115.                 while nxt < len(bal_state) and bal_state[nxt] == 0:
116.                     nxt += 1
117.
118.                 queue.append((moves+1, bal_state[nxt:].copy()))
119.                 bal_state[tx_target] -= bal_state[0]
120.
121.         return -1
122.