465. Optimal Account Balancing

HardBit ManipulationArrayDynamic ProgrammingBacktrackingBitmask
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which two pointer technique does Quick Sort use?

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:

  1. Preparing the Net Balance: We initialize a defaultdict(int) named g to store the net balance of every individual. As we iterate through each transaction [from_i, to_i, amount_i] in transactions, we update the net balance by subtracting amount_i from from_i's balance and adding it to to_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).

  2. 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.

  3. Initializing the Dynamic Programming Array: We define a one-dimensional DP array f with length 1 << m, where m is the number of non-zero net balances (the length of nums). The notation 1 << m means we are using a bitmask to represent all possible subsets of these m balances. We initialize all values in f to infinity (inf), except f[0] which is set to 0 since no transactions are needed if no one is involved.

  4. Finding the Minimum Transactions: We iterate over all subsets of nums by using the variable i to represent a bitmask. For each subset i, we calculate the total sum s 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.

  5. 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 in i. This is because, if n people are in a subset, n - 1 transactions are sufficient to settle their debts (everyone settles with one person).

  6. Optimizing the Transactions: For each valid subset i, we look for pairs of disjoint subsets j and i ^ j (where ^ is the XOR operation) that combine to form i 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 of f[j] + f[i ^ j], which represents the minimum transactions needed to settle the subsets j and i ^ j separately.

  7. Final Answer: The last element in f, f[-1], holds the smallest number of transactions needed to settle all debts, which is what the function minTransfers 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example 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 set f[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
Not Sure What to Study? Take the 2-min Quiz๏ผš

What data structure does Breadth-first search typically uses to store intermediate states?

Time and Space Complexity

Time Complexity

The given code's time complexity is primarily determined by the nested for loops.

  1. Iteration over transactions: O(N), where N is the number of transactions.

  2. Iteration over powerset of debts: This loop iterates over all subsets of a set of m debts, leading to 2^m iterations, where m is the number of unique debts.

  3. Inner loop to calculate sum of debts subsets: O(m) per subset, since it iterates over all m debts to identify sums that cancel out to zero.

  4. Innermost while loop for calculating f[i]: The loop will run in the worst-case scenario 2^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:

  1. The hashmap (g) to store the balances: O(M), where M is the number of unique people involved.

  2. The list nums of non-zero balances: O(m).

  3. The list f of size 2^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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Dynamic Programming Introduction and Patterns

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 1

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 Introduction

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 Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ