# 465 Optimal Account Balancing

## 465. [Optimal Account Balancing](https://leetcode.com/problems/optimal-account-balancing/description/)

## 1. Question

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as`[[0, 1, 10], [2, 0, 5]]`.

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.

**Note:**

1. A transaction will be given as a tuple (x, y, z). Note that`x ≠ y`and`z > 0`.
2. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.

**Example 1:**

```
Input: [[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.
```

**Example 2:**

```
Input: [[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.
```

## 2. Implementation

**(1) Hash Table + Backtracking**

思路:

(1)用hashmap预处理transaction，将balance为0的人去除掉

(2)用backtracking对枚举出所有能将剩余debt settle的组合，

```java
class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Long> map = new HashMap<>();

        // Step 1: Preprocessing the transactions, and ingore people with zero debt
        for (int[] transaction : transactions) {
            int person1 = transaction[0];
            int person2 = transaction[1];
            int curDebt = transaction[2];

            long debt1 = map.getOrDefault(person1, 0L);
            long debt2 = map.getOrDefault(person2, 0L);

            map.put(person1, debt1 - curDebt);
            map.put(person2, debt2 + curDebt);
        }

        List<Long> debts = new ArrayList<>();

        for (long debt : map.values()) {
            if (debt != 0) {
                debts.add(debt);
            }
        }

        // Step 2： Enumerate all possible combinations to settle the debt
        int[] res = {Integer.MAX_VALUE};
        getMinimumTransaction(0, 0, debts, res);
        return res[0];
    }

    public void getMinimumTransaction(int index, int count, List<Long> debts, int[] res) {
        // Skip settled debt
        while (index < debts.size() && debts.get(index) == 0) ++index;

        if (index == debts.size()) {
            res[0] = Math.min(res[0], count);
            return;
        }

        for (int i = index + 1; i < debts.size(); i++) {
            // Only settle debt when the debts[i] has different sign with debts[index]
            if (debts.get(i) * debts.get(index) < 0) {
                debts.set(i, debts.get(i) + debts.get(index));
                getMinimumTransaction(index + 1, count + 1, debts, res);
                debts.set(i, debts.get(i) - debts.get(index));
            }
        }
    }
}
```

**(2) HashMap + Two Pointers + Backtracking**

思路: 这里和上面解法唯一的不同的是在第二步里，我们进行进一步的预处理，用two pointers的方法去除掉可以直接match的debt

```java
class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Long> map = new HashMap<>();

        // Step 1: Preprocessing the transactions, and ingore people with zero debt
        for (int[] transaction : transactions) {
            int person1 = transaction[0];
            int person2 = transaction[1];
            int curDebt = transaction[2];

            long debt1 = map.getOrDefault(person1, 0L);
            long debt2 = map.getOrDefault(person2, 0L);

            map.put(person1, debt1 - curDebt);
            map.put(person2, debt2 + curDebt);
        }

        List<Long> debts = new ArrayList<>();

        for (long debt : map.values()) {
            if (debt != 0) {
                debts.add(debt);
            }
        }

        // Step 2: use two pointers to cancel out debts that match with each other
        Collections.sort(debts);

        int start = 0, end = debts.size() - 1;
        int matchCount = 0;
        while (start < end) {
            if (debts.get(start) + debts.get(end) == 0) {
                debts.remove(start);
                //due to start has been removed: right-1 is correct index
                debts.remove(end - 1);
                // adjust end with end - 2 since two elements have been removed
                end -= 2;
                ++matchCount;
            }
            else if (debts.get(start) + debts.get(end) < 0) {
                ++start;
            }
            else {
                --end;
            }
        }

        // Step 3： Enumerate all possible combinations to settle the debt
        int[] res = {Integer.MAX_VALUE};
        getMinimumTransaction(0, 0, debts, res);
        return matchCount + res[0];
    }

    public void getMinimumTransaction(int index, int count, List<Long> debts, int[] res) {
        // Skip settled debt
        while (index < debts.size() && debts.get(index) == 0) ++index;

        if (index == debts.size()) {
            res[0] = Math.min(res[0], count);
            return;
        }

        for (int i = index + 1; i < debts.size(); i++) {
            // Only settle debt when the debts[i] has different sign with debts[index]
            if (debts.get(i) * debts.get(index) < 0) {
                debts.set(i, debts.get(i) + debts.get(index));
                getMinimumTransaction(index + 1, count + 1, debts, res);
                debts.set(i, debts.get(i) - debts.get(index));
            }
        }
    }
}
```

## 3. Time & Space Complexity

**(1)** **Hash Table + Backtracking:** 时间复杂度O(n!), n是debt不为0的个数，空间复杂度O(m + n), m是人的个数

**(2) HashMap + Two Pointers + Backtracking：**&#x65F6;间复杂度O(n!), 空间复杂度O(m + n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/google/465-optimal-account-balancing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.