LC: 465. Optimal Account Balancing
https://leetcode.com/problems/optimal-account-balancing/
465. Optimal Account Balancing
You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.
Return the minimum number of transactions required to settle the debt.
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.Example 2:
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 <= 8transactions[i].length == 30 <= fromi, toi <= 20fromi != toi1 <= amounti <= 100
465. Optimal Account Balancing:
The Essence: This quote by Erdem, will make it clear to understand the intuition:
If someone gives me
$10and I give that person$10back, it would mean that there are0 transactions needed.If I give that person only
$8back, the situation is equivalent to me getting only$2from the person.If someone comes and gives the person that
$2deficit, the situation is now equivalent to the new person giving me $2.So, we calculate how much each person is in deficit/surplus. If their accounts are balanced with a $0 change, we don't include them in the debts list, as no transactions will be done with them. Some debts will directly cancel each other.
Details:
You can find the detailed explanation and the implementations in our corresponding PR:
Solutions:
Default Code:
Last updated