Optimal Account Balancing
Asked at Salesforce
Problem
A group of friends went on a trip and borrowed/lent money from each other. Given a list of transactions where transactions[i] = [from, to, amount], find the minimum number of transactions needed to settle all debts. Each transaction involves transferring money from one person to another.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | HARD | View all Salesforce questions → |
How to Think About It
First compute net balance for each person (sum of amounts lent minus borrowed)
People with zero net balance are irrelevant — remove them
The problem reduces to: split non-zero balances into minimum subsets that sum to zero
Brute force: try all 2^n subsets, check if subset sums to zero, then recurse on remaining
Optimize with bitmask DP: dp[mask] = min transactions to settle people in mask
Optimal Approach
Compute net balances for each person, filter out zeros. Use backtracking or bitmask DP to find the minimum number of transactions. The answer equals the minimum number of zero-sum subsets the balances can be partitioned into minus one (equivalently, min transactions = n - max number of independent zero-sum groups). With bitmask DP, dp[mask] = min(dp[mask], dp[mask ^ submask] + 1) for all submasks of mask that sum to zero.
What Trips People Up in Real Interviews
Simplify first: compute net balances, drop zeros
Key insight: minimum transactions = number of non-zero balances minus max zero-sum subsets
Backtracking with pruning: sort balances, skip duplicates
Bitmask approach: for each mask, try all submasks that sum to zero
Edge case: all balances zero means 0 transactions needed
Solution Code
class Solution:
def minTransfers(self, transactions: list[list[int]]) -> int:
from collections import defaultdict
balance = defaultdict(int)
for f, t, a in transactions:
balance[f] -= a
balance[t] += a
debts = [v for v in balance.values() if v != 0]
n = len(debts)
if n == 0:
return 0
dp = [float('inf')] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == float('inf'):
continue
total = 0
picked = []
for i in range(n):
if mask & (1 << i):
total += debts[i]
picked.append(i)
if total == 0 and picked:
dp[mask] = min(dp[mask], len(picked) - 1)
for submask in range(mask + 1, 1 << n):
if (submask & mask) != submask:
continue
s = 0
for i in range(n):
if submask & (1 << i):
s += debts[i]
if s == 0:
dp[mask | submask] = min(dp[mask | submask], dp[mask] + bin(submask).count('1') - 1)
return dp[(1 << n) - 1]Frequently Asked Questions
What is the Optimal Account Balancing problem?
A group of friends went on a trip and borrowed/lent money from each other. Given a list of transactions where transactions[i] = [from, to, amount], find the minimum number of transactions needed to settle all debts. Each transaction involves transferring money from one person to another.
How do you solve Optimal Account Balancing?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Optimal Account Balancing?
Optimal Account Balancing is asked at Salesforce. It is a hard difficulty problem.
What are common mistakes on Optimal Account Balancing?
- Simplify first: compute net balances, drop zeros
- Key insight: minimum transactions = number of non-zero balances minus max zero-sum subsets
- Backtracking with pruning: sort balances, skip duplicates
- Bitmask approach: for each mask, try all submasks that sum to zero
- Edge case: all balances zero means 0 transactions needed