The Optimal Account Balancing problem asks you to determine the minimum number of transactions required to settle all debts among a group of people, based on a list of transactions. Each transaction is represented as a list [x, y, z], meaning person x gave person y z dollars. The goal is to minimize the number of transactions needed so that every person's net balance becomes zero (everyone is settled up).
transactions, where each element is a list [from, to, amount].At first glance, you might think to simulate each transaction and try to settle debts one by one. However, this quickly becomes inefficient, especially as the number of people grows, since there are many possible ways to pair up debts and credits.
A brute-force approach would be to try every possible sequence of debt settlements, but this is computationally expensive due to the exponential number of possibilities. To optimize, we need to focus on the net balance of each person—how much they owe or are owed after all transactions are considered. Once we know each person's net balance, the problem reduces to finding the minimum number of transactions that can zero out all non-zero balances.
The key insight is that we can ignore the actual transaction history and just work with the net balances. Then, we try to settle debts recursively, pairing people with opposite balances, and use backtracking to explore the minimum number of settlements.
Let's break down the optimized solution:
Consider the input: transactions = [[0,1,10], [2,0,5]]
Balances: [ -5, +10, -5 ]
This is optimal; you can't do it in fewer than 2 transactions. The solution backtracks through all possible pairings to ensure this is the minimum.
The Optimal Account Balancing problem is about minimizing the number of transactions needed to settle all debts among a group of people. By focusing on each person's net balance, we can ignore the original transaction order and use backtracking to efficiently explore all possible ways to settle debts. Pruning and skipping zero balances greatly improve performance. The solution is elegant because it reduces a seemingly complex set of transactions to a problem of pairing up positive and negative balances optimally.
class Solution:
def minTransfers(self, transactions):
from collections import defaultdict
balance = defaultdict(int)
for frm, to, amt in transactions:
balance[frm] -= amt
balance[to] += amt
debt = [v for v in balance.values() if v != 0]
def dfs(start):
while start < len(debt) and debt[start] == 0:
start += 1
if start == len(debt):
return 0
min_txn = float('inf')
for i in range(start + 1, len(debt)):
if debt[start] * debt[i] < 0:
debt[i] += debt[start]
min_txn = min(min_txn, 1 + dfs(start + 1))
debt[i] -= debt[start]
return min_txn if min_txn != float('inf') else 0
return dfs(0)
class Solution {
public:
int minTransfers(vector<vector<int>>& transactions) {
unordered_map<int, int> balance;
for (auto& t : transactions) {
balance[t[0]] -= t[2];
balance[t[1]] += t[2];
}
vector<int> debt;
for (auto& p : balance)
if (p.second != 0)
debt.push_back(p.second);
return dfs(debt, 0);
}
int dfs(vector<int>& debt, int start) {
while (start < debt.size() && debt[start] == 0) ++start;
if (start == debt.size()) return 0;
int min_txn = INT_MAX;
for (int i = start + 1; i < debt.size(); ++i) {
if (debt[start] * debt[i] < 0) {
debt[i] += debt[start];
min_txn = min(min_txn, 1 + dfs(debt, start + 1));
debt[i] -= debt[start];
}
}
return min_txn == INT_MAX ? 0 : min_txn;
}
};
class Solution {
public int minTransfers(int[][] transactions) {
Map<Integer, Integer> balance = new HashMap<>();
for (int[] t : transactions) {
balance.put(t[0], balance.getOrDefault(t[0], 0) - t[2]);
balance.put(t[1], balance.getOrDefault(t[1], 0) + t[2]);
}
List<Integer> debt = new ArrayList<>();
for (int val : balance.values())
if (val != 0) debt.add(val);
return dfs(debt, 0);
}
private int dfs(List<Integer> debt, int start) {
while (start < debt.size() && debt.get(start) == 0) start++;
if (start == debt.size()) return 0;
int minTxn = Integer.MAX_VALUE;
for (int i = start + 1; i < debt.size(); i++) {
if (debt.get(start) * debt.get(i) < 0) {
debt.set(i, debt.get(i) + debt.get(start));
minTxn = Math.min(minTxn, 1 + dfs(debt, start + 1));
debt.set(i, debt.get(i) - debt.get(start));
}
}
return minTxn == Integer.MAX_VALUE ? 0 : minTxn;
}
}
var minTransfers = function(transactions) {
const balance = {};
for (const [from, to, amt] of transactions) {
balance[from] = (balance[from] || 0) - amt;
balance[to] = (balance[to] || 0) + amt;
}
const debt = [];
for (const val of Object.values(balance)) {
if (val !== 0) debt.push(val);
}
function dfs(start) {
while (start < debt.length && debt[start] === 0) start++;
if (start === debt.length) return 0;
let minTxn = Infinity;
for (let i = start + 1; i < debt.length; i++) {
if (debt[start] * debt[i] < 0) {
debt[i] += debt[start];
minTxn = Math.min(minTxn, 1 + dfs(start + 1));
debt[i] -= debt[start];
}
}
return minTxn === Infinity ? 0 : minTxn;
}
return dfs(0);
};