Minimum Number of Transfers to Settle All Debts in a Group
Company: Virtu
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
A group of people have lent money to each other. Each record `transactions[i] = [x, y, amount]` means that person `x` gave `amount` to person `y`. The group now wants to settle up with new transfers so that, counting both the original transactions and the new transfers, every person has given exactly as much as they have received.
Return the minimum number of new transfers needed.
### Function Signature
```python
def min_transfers(transactions: list[list[int]]) -> int:
```
### Rules
- A person's net balance is the total amount they gave minus the total amount they received. All debts are settled when every person's net balance is `0`.
- A new transfer moves a positive integer amount from one person to a different person. Any person may send or receive any number of new transfers, and transfers are not limited to pairs of people who appear together in `transactions`.
- People are identified only by their integer IDs. A person who appears in no transaction is not involved.
- Return `0` if every net balance is already `0`.
### Constraints
- `1 <= len(transactions) <= 8`
- `transactions[i] == [x, y, amount]` with `0 <= x <= 11`, `0 <= y <= 11`, `x != y` and `1 <= amount <= 100`
- Every sum involved fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: transactions = [[0, 1, 10], [2, 0, 5]]
Output: 2
```
Person `0` gave 10 and received 5, so they are owed 5. Person `1` received 10 and owes 10. Person `2` gave 5 and is owed 5. Person `1` pays 5 to person `0` and 5 to person `2`. A single transfer cannot settle three nonzero balances.
**Example 2**
```text
Input: transactions = [[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]]
Output: 1
```
Person `0` gave 10 and received 6, so they are owed 4. Person `1` gave 6 and received 10, so they owe 4. Person `2` gave 5 and received 5, so they are already settled. One transfer of 4 from person `1` to person `0` settles everything.
**Example 3**
```text
Input: transactions = [[0, 1, 5], [1, 0, 5]]
Output: 0
```
Overview: Given a list of past loans between people, compute the minimum number of new money transfers needed so that everyone's net balance returns to zero. Tests reducing a transaction log to net balances and searching for the fewest settling transfers under small input bounds.
Read the full Virtu Quantitative Researcher interview experience this question came from
A group of people have lent money to each other. Each record `transactions[i] = [x, y, amount]` means that person `x` gave `amount` to person `y`. The same pair of people may appear in several records, in either direction. The group now wants to settle up with new transfers so that, counting both the original transactions and the new transfers, every person has given exactly as much as they have received.
Return the minimum number of new transfers needed.
Implement `min_transfers(transactions)`, which receives the list of transactions and returns that minimum as an integer.
### Rules
- A person's net balance is the total amount they gave minus the total amount they received. All debts are settled when every person's net balance is `0`.
- A new transfer moves a positive integer amount from one person to a different person. Any person may send or receive any number of new transfers, and transfers are not limited to pairs of people who appear together in `transactions`.
- People are identified only by their integer IDs. A person who appears in no transaction is not involved.
- Return `0` if every net balance is already `0`.
### Constraints
- `1 <= len(transactions) <= 8`
- `transactions[i] == [x, y, amount]` with `0 <= x <= 11`, `0 <= y <= 11`, `x != y` and `1 <= amount <= 100`
- Every sum involved fits in a 32-bit signed integer. No value can exceed 2^31 - 1, so 32-bit `int` suffices in every language.
### Example 1
```text
Input: transactions = [[0, 1, 10], [2, 0, 5]]
Output: 2
```
Person `0` gave 10 and received 5, so they are owed 5. Person `1` received 10 and owes 10. Person `2` gave 5 and is owed 5. Person `1` pays 5 to person `0` and 5 to person `2`. A single transfer cannot settle three nonzero balances.
### Example 2
```text
Input: transactions = [[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]]
Output: 1
```
Person `0` gave 10 and received 6, so they are owed 4. Person `1` gave 6 and received 10, so they owe 4. Person `2` gave 5 and received 5, so they are already settled. One transfer of 4 from person `1` to person `0` settles everything.
Constraints
- 1 <= len(transactions) <= 8
- transactions[i] == [x, y, amount] with 0 <= x <= 11, 0 <= y <= 11, x != y and 1 <= amount <= 100
- Every sum involved fits in a 32-bit signed integer.
Examples
Input: ([[0, 1, 10], [2, 0, 5]],)
Expected Output: 2
Explanation: Source Example 1: balances +5, -10, +5 have no proper zero-sum subset, so three people need two transfers.
Input: ([[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]],)
Expected Output: 1
Explanation: Source Example 2: person 2 nets to 0 and is excluded; the remaining +4 and -4 need one transfer.
Hints
- Collapse the transactions into a single net balance per person; which records produced a balance no longer matters.
- A person whose net balance is already 0 never has to send or receive a new transfer.
- Ask how many transfers a set of k people whose balances add up to 0 needs on its own, and whether settling smaller such sets separately can save transfers.