465. Optimal Account Balancing
Problem Description
In this problem, we are provided with a list of financial transactions among a group of people, where each person has a unique ID. Each transaction is represented as a list with three integers [from_i, to_i, amount_i]
signifying that the person with ID from_i
has given the amount amount_i
to the person with ID to_i
. The objective is to determine the minimum number of transactions needed to settle all debts in the system. In other words, we want to find the smallest set of transactions so that everybody ends up with a balance of zero without considering the original transactions.
Flowchart Walkthrough
Let's analyze leetcode 465. Optimal Account Balancing using the Flowchart. Here is a step-by-step analysis of the problem:
-
Is it a graph?
- Yes: Though it may not look immediately like a traditional graph problem, the essence of balancing accounts can be seen as creating and balancing transactions between nodes (accounts).
-
Does the problem have small constraints?
- Yes: While not strictly limited in number, the real-world scenarios typically involve a manageable number of accounts, suggesting that we might encounter small constraints for practical purposes.
-
Brute force / Backtracking?
- Yes: Given the complexity of various transactions and the requirement to minimize the transaction count, brute force or backtracking can be highly suitable. This is because every transaction creates a new state of balances, and we may need to backtrack to find the optimal series of transactions.
Conclusion: The flowchart leads us to consider using a backtracking approach to explore different ways transactions can balance the accounts efficiently while minimizing the total number of transactions needed. Such a method systematically tries different transactions, possibly undoing them (backtrack) if they do not lead toward the solution.
Intuition
The intuition behind the solution is to first simplify the problem by calculating the net balance of each person after all the transactions. A net balance is the amount of money a person owes (negative balance) or is owed (positive balance). If a person has a net balance of zero, no further action is needed for them, so we ignore them in the settlement process.
To settle the debts, we aim to find the fewest number of transactions that would balance these net amounts. This becomes a combinatorial optimization problem where we explore different ways to match debtors (people with a negative balance) with creditors (people with a positive balance) in a minimal fashion. Essentially, it's a variation of the subset sum problem, which is computationally challenging (NP-Complete) due to the number of combinations to consider.
We use dynamic programming to manage the complexity. We represent each subset of people using a bitmask, where the i
-th bit represents whether the i
-th person is included in the subset. Our dynamic programming array f
keeps track of the minimum number of transactions needed for each subset of people. The value f[i]
contains the optimal (minimum) number of transactions needed to settle the debts among the subset of people represented by the bitmask i
.
By iterating through all possible subsets, we try to construct solutions from combinations of smaller subsets that sum up to zero, meaning their debts can be settled among themselves. We use bit manipulation to iterate through subsets and to compute the number of bits set (number of people involved) in a state. The bit count of a state minus one gives us the correct number of transactions, assuming a direct transaction could settle the debts among people in that state.
The final answer is then found in f[-1]
, which represents the minimum number of transactions needed to settle all debts among all people, encoded in the bitmask with all bits set.
Learn more about Dynamic Programming, Backtracking and Bitmask patterns.
Solution Approach
The solution relies on dynamic programming, bit manipulation, and understanding of financial transactions to reduce an optimization problem into a solvable algorithm. Let's walk through it step-by-step with reference to the given Python code:
-
Preparing the Net Balance: We initialize a
defaultdict(int)
namedg
to store the net balance of every individual. As we iterate through each transaction[from_i, to_i, amount_i]
intransactions
, we update the net balance by subtractingamount_i
fromfrom_i
's balance and adding it toto_i
's balance. This will ensure that the net balance reflects how much each person is in debt (negative balance) or is owed (positive balance). -
Filtering Zero Balances: We filter out individuals with a zero net balance since they do not need to be involved in any further transactions. This is done by creating a list
nums
containing only non-zero balances. -
Initializing the Dynamic Programming Array: We define a one-dimensional DP array
f
with length1 << m
, wherem
is the number of non-zero net balances (the length ofnums
). The notation1 << m
means we are using a bitmask to represent all possible subsets of thesem
balances. We initialize all values inf
to infinity (inf
), exceptf[0]
which is set to 0 since no transactions are needed if no one is involved. -
Finding the Minimum Transactions: We iterate over all subsets of
nums
by using the variablei
to represent a bitmask. For each subseti
, we calculate the total sums
of the balances in that subset. If the sum is zero (s == 0
), it means this subset can balance itself out with no debt remaining. -
Setting Base Case for Valid Subsets: If the
i
-th subset's sum is 0, we calculate the number of required transactions as one less than the number of set bits ini
. This is because, ifn
people are in a subset,n - 1
transactions are sufficient to settle their debts (everyone settles with one person). -
Optimizing the Transactions: For each valid subset
i
, we look for pairs of disjoint subsetsj
andi ^ j
(where^
is the XOR operation) that combine to formi
and have a sum of zero. We use bit manipulation(j - 1) & i
to iterate through all those potential pairs. The goal is to find the pair that minimizes the sum off[j] + f[i ^ j]
, which represents the minimum transactions needed to settle the subsetsj
andi ^ j
separately. -
Final Answer: The last element in
f
,f[-1]
, holds the smallest number of transactions needed to settle all debts, which is what the functionminTransfers
returns.
In summary, this approach uses a combination of net balance calculation, filtering, dynamic programming, and bit manipulation to efficiently find the minimum number of transactions needed to settle debts across a group of people.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach described above. Suppose we have the following set of transactions between three people with IDs 1, 2, and 3:
1Transactions: [[1, 2, 10], [2, 3, 5], [3, 1, 5]]
This means that person 1 gave 10 to person 2, person 2 gave 5 to person 3, and person 3 gave 5 to person 1.
Step 1: Preparing the Net Balance
We calculate the net balance of each individual:
- Person 1: (received 5) - (gave 10) = -5
- Person 2: (received 10) - (gave 5) = 5
- Person 3: (received 5) - (gave 5) = 0
Step 2: Filtering Zero Balances
Person 3 has a net balance of 0, so they are excluded from further transactions:
1nums: [-5, 5]
Step 3: Initializing the Dynamic Programming Array
There are 2 people with non-zero net balances, so our DP array f
will have 1 << 2
(which is 4) elements:
1f: [0, inf, inf, inf]
Step 4: Finding the Minimum Transactions
We iterate over all subsets of nums
:
- Subset represented by bitmask
00
has sum 0. We already setf[0]
to 0 because no people are involved. - Subset
01
has only person 1, who cannot settle the debt alone. - Subset
10
has only person 2, who also cannot settle the debt alone. - Subset
11
has both person 1 and 2. The sum is 0, so they can settle among themselves.
Step 5: Setting Base Case for Valid Subsets
Since the sum for the subset 11
is 0, we can settle the debt with one transaction:
1f[11] = Number of people in subset - 1 = 2 - 1 = 1
So, f[3]
(binary 11
is 3 in decimal), is updated to 1.
Step 6: Optimizing the Transactions
This step involves disjoint pairs but, in our case, since we have just 2 non-zero net balances, there is only one valid subset (11
) that balances to zero. So we skip the optimization as we've already found the solution.
Step 7: Final Answer
The final answer, found in f[-1]
(or f[3]
since we only have 4 entries and Python allows negative indexing), is the minimum number of transactions needed which is 1. One person pays the other, and all debts are settled.
By this example, we can see how the described dynamic programming solution would work on a small scale and calculate the minimum number of transactions to settle debts.
Solution Implementation
1from collections import defaultdict
2from math import inf
3
4class Solution:
5 def min_transfers(self, transactions) -> int:
6 balance = defaultdict(int)
7 # Calculate the net balance for each person
8 for from_person, to_person, amount in transactions:
9 balance[from_person] -= amount
10 balance[to_person] += amount
11
12 # Filter out people with a zero balance as they do not need any transfers
13 debts = [amount for amount in balance.values() if amount]
14 number_of_people = len(debts)
15
16 # Initialize the dp array to store minimum transfers for each subset
17 # set fewest_transfers[i] = inf for all i, except fewest_transfers[0] = 0
18 fewest_transfers = [inf] * (1 << number_of_people)
19 fewest_transfers[0] = 0
20
21 # Evaluate each subset of people
22 for i in range(1, 1 << number_of_people):
23 sum_of_debts = 0
24 # Calculate the sum of debts for the current subset
25 for j, debt in enumerate(debts):
26 if i >> j & 1:
27 sum_of_debts += debt
28
29 # If the sum of debts is zero, it's possible to settle within the group
30 if sum_of_debts == 0:
31 # The number of transactions needed is the bit count of i (number of set bits) minus 1
32 fewest_transfers[i] = bin(i).count('1') - 1
33
34 # Try to split the subset in different ways and keep the minimum transfers
35 subset = (i - 1) & i
36 while subset > 0:
37 fewest_transfers[i] = min(fewest_transfers[i], fewest_transfers[subset] + fewest_transfers[i ^ subset])
38 subset = (subset - 1) & i
39
40 # The answer is in fewest_transfers[-1] which corresponds to the situation where all people are considered
41 return fewest_transfers[-1]
42
1class Solution {
2 public int minTransfers(int[][] transactions) {
3 // The array 'balance' will hold the net amount for up to 12 individuals
4 // Negative values mean the person needs to pay that amount, positive values mean the person should receive that amount
5 int[] balance = new int[12];
6
7 // Calculate the balance for each person involved in the transactions
8 for (int[] transaction : transactions) {
9 balance[transaction[0]] -= transaction[2]; // person paying out
10 balance[transaction[1]] += transaction[2]; // person receiving payment
11 }
12
13 // Create a list to store non-zero balances (amounts that need to be settled)
14 List<Integer> nonZeroBalances = new ArrayList<>();
15 for (int b : balance) {
16 if (b != 0) {
17 nonZeroBalances.add(b);
18 }
19 }
20
21 // Prepare to find the minimum number of transactions to settle all debts
22 int numAccounts = nonZeroBalances.size();
23 int[] minTransfers = new int[1 << numAccounts]; // 1<<numAccounts is 2^numAccounts
24 Arrays.fill(minTransfers, Integer.MAX_VALUE / 2); // Initialize with a large value
25 minTransfers[0] = 0; // No transfers needed when there is no debt
26
27 // Loop through all possible subsets of debts
28 for (int i = 1; i < (1 << numAccounts); ++i) {
29 int sum = 0;
30
31 // Calculate the sum of balances in the current subset
32 for (int j = 0; j < numAccounts; ++j) {
33 if ((i >> j & 1) == 1) { // If the j-th person is in the current subset (i)
34 sum += nonZeroBalances.get(j);
35 }
36 }
37
38 // If the sum is zero, then the current subset can be settled among themselves
39 if (sum == 0) {
40 // Set initial transfers for this subset as the number of involved accounts minus 1 transfer
41 minTransfers[i] = Integer.bitCount(i) - 1;
42
43 // Try to split the subset into two parts and minimize their transfers
44 for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
45 // Update the minimum transfers for the current subset
46 minTransfers[i] = Math.min(minTransfers[i], minTransfers[j] + minTransfers[i ^ j]);
47 }
48 }
49 }
50
51 // Return the number of transactions for the set including all non-zero balances
52 return minTransfers[(1 << numAccounts) - 1];
53 }
54}
55
1#include <vector>
2#include <cstring>
3#include <algorithm>
4
5class Solution {
6public:
7 int minTransfers(std::vector<std::vector<int>>& transactions) {
8 // Balance for each person
9 int balance[12] = {};
10
11 // Calculate balance for each person based on transactions
12 for (const auto& transaction : transactions) {
13 balance[transaction[0]] -= transaction[2];
14 balance[transaction[1]] += transaction[2];
15 }
16
17 // Vector to store non-zero balances which need to be settled
18 std::vector<int> debts;
19 for (int amount : balance) {
20 if (amount != 0) {
21 debts.push_back(amount);
22 }
23 }
24
25 int numDebts = debts.size();
26
27 // Initialize dp array for subset costs with high values
28 int dp[1 << numDebts];
29 std::memset(dp, 0x3f, sizeof(dp));
30 dp[0] = 0; // Base case: no debts mean no transactions
31
32 // Iterate over all subsets of debts
33 for (int i = 1; i < (1 << numDebts); ++i) {
34 int sum = 0; // Sum of debts in the current subset
35
36 // Calculate sum for the current subset of debts
37 for (int j = 0; j < numDebts; ++j) {
38 if (i & (1 << j)) {
39 sum += debts[j];
40 }
41 }
42
43 // If the sum of this subset is 0, the debts can be settled
44 if (sum == 0) {
45 // A subset with debts that cancel out each other can be settled in "popcount(i) - 1" transactions
46 dp[i] = __builtin_popcount(i) - 1;
47 // The cost of the current set is the minimum number of transactions needed to settle all debts
48 for (int j = (i - 1) & i; j; j = (j - 1) & i) {
49 dp[i] = std::min(dp[i], dp[j] + dp[i ^ j]);
50 }
51 }
52 }
53
54 // The answer is the min number of transactions needed to settle all debts
55 return dp[(1 << numDebts) - 1];
56 }
57};
58
1// Calculates the minimum number of transactions required to settle the debt.
2function minTransfers(transactions: number[][]): number {
3 // Initialize an array to store the net balance for up to 12 individuals
4 const netBalances: number[] = new Array(12).fill(0);
5 // Calculate the net balance for each individual
6 for (const [from, to, amount] of transactions) {
7 netBalances[from] -= amount;
8 netBalances[to] += amount;
9 }
10
11 // Filter out individuals with a net balance of zero, as they do not need to settle
12 const nonZeroBalances = netBalances.filter(balance => balance !== 0);
13 const countNonZero = nonZeroBalances.length;
14
15 // Initialize a dynamic programming array to store the minimum transactions required for each subset
16 const minTransfersForSubset: number[] = new Array(1 << countNonZero).fill(Infinity);
17 minTransfersForSubset[0] = 0; // 0 transactions are needed for the empty subset
18
19 // Loop through all subsets of individuals with non-zero balances
20 for (let i = 1; i < 1 << countNonZero; ++i) {
21 let sum = 0;
22 // Calculate the total balance for this subset
23 for (let j = 0; j < countNonZero; ++j) {
24 if (((i >> j) & 1) === 1) {
25 sum += nonZeroBalances[j];
26 }
27 }
28 // If the subset's balance is zero, it can be settled
29 if (sum === 0) {
30 minTransfersForSubset[i] = bitCount(i) - 1;
31 for (let subset = (i - 1) & i; subset; subset = (subset - 1) & i) {
32 minTransfersForSubset[i] = Math.min(minTransfersForSubset[i], minTransfersForSubset[subset] + minTransfersForSubset[i ^ subset]);
33 }
34 }
35 }
36 // Return the minimum number of transactions to settle all debts
37 return minTransfersForSubset[(1 << countNonZero) - 1];
38}
39
40// Counts the number of bits set to 1 in the binary representation of a number.
41function bitCount(i: number): number {
42 i = i - ((i >>> 1) & 0x55555555); // Group bit pairs and subtract
43 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); // Group by 4 bits
44 i = (i + (i >>> 4)) & 0x0f0f0f0f; // Group by 8 bits
45 i = i + (i >>> 8); // Group by 16 bits
46 i = i + (i >>> 16); // Sum up all 32 bits
47 return i & 0x3f; // Return the count of set bits
48}
49
Time and Space Complexity
Time Complexity
The given code's time complexity is primarily determined by the nested for
loops.
-
Iteration over transactions:
O(N)
, whereN
is the number of transactions. -
Iteration over powerset of debts: This loop iterates over all subsets of a set of
m
debts, leading to2^m
iterations, wherem
is the number of unique debts. -
Inner loop to calculate sum of debts subsets:
O(m)
per subset, since it iterates over allm
debts to identify sums that cancel out to zero. -
Innermost while loop for calculating
f[i]
: The loop will run in the worst-case scenario2^m
times, for each of the combinations from the second iteration.
Consequently, the time complexity is O(N) + O(m * 2^m) + O(m * (2^m))
which simplifies to O(N + m * 2^m)
, where m
is the number of non-zero individual net balances. Since m
can be at most equivalent to N
, in the worst case, the m * 2^m
term dominates, making the time complexity O(m * 2^m)
.
Space Complexity
The space complexity is influenced by:
-
The hashmap (
g
) to store the balances:O(M)
, whereM
is the number of unique people involved. -
The list
nums
of non-zero balances:O(m)
. -
The list
f
of size2^m
to keep track of minimum transfers for each subset of debts:O(2^m)
.
Hence, the space complexity is O(M + m + 2^m)
. However, since the 2^m
term is the most significant, it simplifies to O(2^m)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.