July 5, 2022
Here is the link.
C# | Quick learner | DFS, backtracking | GraceMeng top voted
July 4, 2022
Introduction
It is ad hoc to learn one algorithm from top voted discuss posts from graceMeng. I chose to study this hard level algorithm. I just quickly read the analysis and then studied one of C# discuss post.
GraceMeng -> top voted discuss algorithms
Leetcode newly release product feature: Leetcode profile -> discuss -> Most voites -> top 15 algorithms (https://leetcode.com/GraceMeng/). I choose to study those algorithms and figure out what is the secret in the analysis to win so many up-votes.
Ideas | Analysis from graceMeng | Top-voted one
I like to learn how to write a good analysis from graceMeng - https://leetcode.com/problems/optimal-account-balancing/discuss/130895/Recursion-Logical-Thinking.
? what does it mean to settle the debt
nobody owes others
? how do we represent how much money a person owes others
We build current debt situation debt[], e.g. debt[i] = 10 means a person owes others 10
? how do we settle one's debt
assuming [0, curId - 1] has been settled,
for debt[curId],
any curId + 1 <= i <debt.length such that debt[i] * debt[curId] < 0 can settle it
state
The next account to balance, curId, can uniquely identify a state
state function
state(debt[], curId) is the minimum transactions to balance debts[curId...debtLength - 1] such that debts[0...curId-1] are balanced.
goal state
state(initial debt[], 0)
state transition
now: state(debt[], curId)
next: state (debt[] after balance curId, curId + 1)
state(debt[], curId) = 1 + min(state (debt[] after balance curId, curId + 1))
Note
- How do we decide who can balance the account of curId?
There are many people who can balance curId's account -- person i behind curId with debt[i] * debt[curId] < 0.
C# code implmentation -> backward -> Analysis
I think that it is easy for me to understand the algorithm by reading the following C# code. The DFS search and also brute force comparison among all options in order to get the minimum transaction.
I like to talk about a test case, and then discuss my concerns. Through the discussion, I can learn how to prototype the algorithm to this classical approach.
Example 1:
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.
By going through transactions, there are three people, [0, 1, 2].
Next it is to calculate debt[] for each person.
First transaction: [0, 1, 10], we have the following facts:
debt[0] = -10,
debt[1] = 10
Second transaction: [2, 0, 5], and then we have updates:
debt[2] = -5
debt[0] = -10 + 5 = 5.
So debt[] = int[]{5, 10, -5}
Next is the exercise how to apply DFS search and get minimum transaction.
It is easy to figure out one of minimum count (minimum count is 2) of transactions is to let person 1 to pay person 0 with 5 dollars, and then person 1 to pay person 2 5 dollars.
Now my suggestion is to go back to the above analysis, and then combine the test case I just warm up, and then try to figure out what is truth in the above analysis.
Leave for my practice privately if I have time.
The following C# code passes online judge.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _465_optimal_account_balancing
{
class Program
{
static void Main(string[] args)
{
var transactions = new int[2][];
transactions[0] = new int[] { 0, 1, 10 };
transactions[1] = new int[] { 2, 0, 5 };
var result = MinTransfers(transactions);
Debug.Assert(result == 2);
}
/// <summary>
/// code study
/// https://leetcode.com/problems/optimal-account-balancing/discuss/130895/recursion-logical-thinking
/// One of replies - C# solution shared by pantigalt
/// </summary>
/// <param name="transactions"></param>
/// <returns></returns>
public static int MinTransfers(int[][] transactions)
{
var debt = CreateDebtTable(transactions);
return CalculateMinTransfers(0, debt);
}
/// <summary>
/// It is hard for me to figure out, so I just learn quickly by studying GraceMeng's one
/// </summary>
/// <param name="curId"></param>
/// <param name="debt"></param>
/// <returns></returns>
private static int CalculateMinTransfers(int curId, int[] debt)
{
// skip all account with zero balance
while (curId < debt.Length && debt[curId] == 0)
{
curId++;
}
// Everyone has zero balance
if (curId == debt.Length)
{
return 0;
}
// Everyone before current person has zero balance
// current person has non-zero balance
int minTransactions = int.MaxValue;
for (int i = curId + 1; i < debt.Length; i++)
{
// check for opposite signs
if ((debt[i] ^ debt[curId]) < 0)
{
// modify debt for current person
debt[i] += debt[curId];
// recursive think -> DFS -> minimum transactions -> ?
minTransactions = Math.Min(minTransactions, CalculateMinTransfers(curId + 1, debt) + 1);
// restore debt for current person
debt[i] -= debt[curId];
}
}
return minTransactions;
}
/// <summary>
/// Lynq expression:
/// Dictionary<int, int> -> debts.Select(x => x.Value).ToArray();
/// </summary>
/// <param name="items"></param>
/// <returns></returns>
private static int[] CreateDebtTable(int[][] items)
{
// accumulate debts with original person ids
var debts = new Dictionary<int, int>();
foreach (int[] item in items)
{
if (!debts.ContainsKey(item[0]))
{
debts.Add(item[0], 0);
}
if (!debts.ContainsKey(item[1]))
{
debts.Add(item[1], 0);
}
debts[item[0]] += item[2];
debts[item[1]] -= item[2];
}
// we need to return an array with sequential person ids
return debts.Select(x => x.Value).ToArray();
}
}
}