[Google Question][LeetCode] Optimal Account Balancing

Problem: 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:

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.

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.

Approach: This is complex problem to solve. Basically first we need to get all the debts (negative or positive) on every person. Once we get all the debts, we need to find every settlement combination and then we need to find the combination with minimum length among these combinations.

Getting debts on every person is easy, we can use hashing to get it but to get all the combinations and then get the minimum of those we need to use backtracking / DFS.

Implementation in C#:

    public int MinTransfers(int[][] transactions) 

    {

        Dictionary<int, int> debtsMap = new Dictionary<int, int>();

        foreach(int[] transaction in transactions)

        {

            int sender = transaction[0], receiever = transaction[1], amount = transaction[2];

            if (!debtsMap.ContainsKey(sender))

            {

                debtsMap[sender] = 0;

            }

            if (!debtsMap.ContainsKey(receiever))

            {

                debtsMap[receiever] = 0;

            }

            debtsMap[sender] -= amount;

            debtsMap[receiever] += amount;

        }

        List<int> debtsList = debtsMap.Values.Where(am => am != 0).ToList();

        return this.GetMinTransactionsToSettle(debtsList, 0);

    }

    

    private int GetMinTransactionsToSettle(List<int> debtsList, int currIndex)

    {

        // No point in processing with 0 debt   

        while (currIndex < debtsList.Count && debtsList[currIndex] == 0)

        {

            ++currIndex;

        }

        // Done here, we get one of the combination

        if (currIndex == debtsList.Count)

        {

            return 0;

        }

        int currAmount = debtsList[currIndex];

        int minTransactions = int.MaxValue;

        for (int i = currIndex + 1; i < debtsList.Count; ++i)

        {

            int nextAmount = debtsList[i];

            // An optimization: there is no point in process '+' and  '+' or '-' and '-'

            if (currAmount * nextAmount < 0)

            {

                debtsList[i] = currAmount + nextAmount;

                minTransactions = Math.Min(minTransactions, this.GetMinTransactionsToSettle(debtsList, currIndex + 1) + 1);

                debtsList[i] = nextAmount;

                // This is an optimization

                if (currAmount + nextAmount == 0)

                {

                    break;

                }

            }

        }

        return minTransactions;

    }

Complexity: O(n^2)