Advertisement
bennyfromtheblock

465. Optimal Account Balancing

Mar 3rd, 2024 (edited)
640
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.25 KB | None | 0 0
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement