> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Optimal Account Balancing Python Solution

> Tested Python solution for LeetCode 465 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 465, [Hard](/catalog/hard). Topics: [Bit Manipulation](/catalog/topics/bit-manipulation), [Array](/catalog/topics/array), [Dynamic Programming](/catalog/topics/dynamic-programming), [Backtracking](/catalog/topics/backtracking), [Bitmask](/catalog/topics/bitmask). [View on LeetCode](https://leetcode.com/problems/optimal-account-balancing/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 465   # by problem number
lcpy gen -s optimal_account_balancing   # by problem name
```

## Problem

You are given an array of transactions `transactions` where `transactions[i] = [from_i, to_i, amount_i]` indicates that the person with `ID = from_i` gave `amount_i $` to the person with `ID = to_i`.

Return the minimum number of transactions required to settle the debt.

### Examples

```
Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
```

```
Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.
```

### Constraints

* `1 <= transactions.length <= 8`
* `transactions[i].length == 3`
* `0 <= from_i, to_i < 12`
* `from_i != to_i`
* `1 <= amount_i <= 100`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/optimal_account_balancing/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/optimal_account_balancing/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(k! ) worst case over k non-zero balances
    # Space: O(k)
    def min_transfers(self, transactions: list[list[int]]) -> int:
        balances: dict[int, int] = {}
        for sender, receiver, amount in transactions:
            balances[sender] = balances.get(sender, 0) - amount
            balances[receiver] = balances.get(receiver, 0) + amount
        debts = [v for v in balances.values() if v != 0]

        def settle(start: int) -> int:
            while start < len(debts) and debts[start] == 0:
                start += 1
            if start == len(debts):
                return 0
            best = len(debts)
            seen: set[int] = set()
            for i in range(start + 1, len(debts)):
                if debts[i] * debts[start] < 0 and debts[i] not in seen:
                    seen.add(debts[i])
                    debts[i] += debts[start]
                    best = min(best, 1 + settle(start + 1))
                    debts[i] -= debts[start]
            return best

        return settle(0)
```

## Complexity

| Time | Space |
| - | - |
| O(k! ) worst case over k non-zero balances | O(k) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.