← Static tasks

465. Optimal Account Balancing

leetcode medium

#array#csharp#graph#hash-table#leetcode#math#medium#recursion

Task

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

Верните минимальное количество транзакций, необходимых для урегулирования долгов.

Пример:

Input: transactions = [[0,1,10],[2,0,5]]

Output: 2

C# solution

matched/original
public class Solution {
    private List<int> creditList;
    
    public int MinTransfers(int[][] transactions) {
        var creditMap = new Dictionary<int, int>();
        foreach (var t in transactions) {
            if (!creditMap.ContainsKey(t[0])) creditMap[t[0]] = 0;
            if (!creditMap.ContainsKey(t[1])) creditMap[t[1]] = 0;
            creditMap[t[0]] += t[2];
            creditMap[t[1]] -= t[2];
        }
        
        creditList = new List<int>();
        foreach (var amount in creditMap.Values) {
            if (amount != 0) {
                creditList.Add(amount);
            }
        }
        
        int n = creditList.Count;
        return Dfs(0, n);
    }
    
    private int Dfs(int cur, int n) {
        while (cur < n && creditList[cur] == 0) {
            cur++;
        }
    
        if (cur == n) {
            return 0;
        }
        
        int cost = int.MaxValue;
        for (int nxt = cur + 1; nxt < n; nxt++) {
            if (creditList[nxt] * creditList[cur] < 0) {
                creditList[nxt] += creditList[cur];
                cost = Math.Min(cost, 1 + Dfs(cur + 1, n));
                creditList[nxt] -= creditList[cur];
            }
        }
        
        return cost;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private List<int> creditList;
    
    public int MinTransfers(int[][] transactions) {
        var creditMap = new unordered_map<int, int>();
        foreach (var t in transactions) {
            if (!creditMap.count(t[0])) creditMap[t[0]] = 0;
            if (!creditMap.count(t[1])) creditMap[t[1]] = 0;
            creditMap[t[0]] += t[2];
            creditMap[t[1]] -= t[2];
        }
        
        creditList = new List<int>();
        foreach (var amount in creditMap.Values) {
            if (amount != 0) {
                creditList.push_back(amount);
            }
        }
        
        int n = creditList.size();
        return Dfs(0, n);
    }
    
    private int Dfs(int cur, int n) {
        while (cur < n && creditList[cur] == 0) {
            cur++;
        }
    
        if (cur == n) {
            return 0;
        }
        
        int cost = int.MaxValue;
        for (int nxt = cur + 1; nxt < n; nxt++) {
            if (creditList[nxt] * creditList[cur] < 0) {
                creditList[nxt] += creditList[cur];
                cost = min(cost, 1 + Dfs(cur + 1, n));
                creditList[nxt] -= creditList[cur];
            }
        }
        
        return cost;
    }
}

Java solution

matched/original
import java.util.*;

public class Solution {
    private List<Integer> creditList;
    
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> creditMap = new HashMap<>();
        for (int[] t : transactions) {
            creditMap.put(t[0], creditMap.getOrDefault(t[0], 0) + t[2]);
            creditMap.put(t[1], creditMap.getOrDefault(t[1], 0) - t[2]);
        }
        
        creditList = new ArrayList<>();
        for (int amount : creditMap.values()) {
            if (amount != 0) {
                creditList.add(amount);
            }
        }
        
        int n = creditList.size();
        return dfs(0, n);
    }
    
    private int dfs(int cur, int n) {
        while (cur < n && creditList.get(cur) == 0) {
            cur++;
        }
    
        if (cur == n) {
            return 0;
        }
        
        int cost = Integer.MAX_VALUE;
        for (int nxt = cur + 1; nxt < n; nxt++) {
            if (creditList.get(nxt) * creditList.get(cur) < 0) {
                creditList.set(nxt, creditList.get(nxt) + creditList.get(cur));
                cost = Math.min(cost, 1 + dfs(cur + 1, n));
                creditList.set(nxt, creditList.get(nxt) - creditList.get(cur));
            }
        }
        
        return cost;
    }
}

JavaScript solution

matched/original
class Solution {
    minTransfers(transactions) {
        const creditMap = new Map();
        for (const t of transactions) {
            creditMap.set(t[0], (creditMap.get(t[0]) || 0) + t[2]);
            creditMap.set(t[1], (creditMap.get(t[1]) || 0) - t[2]);
        }
        
        const creditList = [];
        for (const amount of creditMap.values()) {
            if (amount !== 0) {
                creditList.push(amount);
            }
        }
        
        const n = creditList.length;
        
        const dfs = (cur) => {
            while (cur < n && creditList[cur] === 0) {
                cur++;
            }
            if (cur === n) {
                return 0;
            }
            let cost = Infinity;
            for (let nxt = cur + 1; nxt < n; nxt++) {
                if (creditList[nxt] * creditList[cur] < 0) {
                    creditList[nxt] += creditList[cur];
                    cost = Math.min(cost, 1 + dfs(cur + 1));
                    creditList[nxt] -= creditList[cur];
                }
            }
            return cost;
        };
        
        return dfs(0);
    }
}

Python solution

matched/original
class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        from collections import defaultdict
        
        credit_map = defaultdict(int)
        for t in transactions:
            credit_map[t[0]] += t[2]
            credit_map[t[1]] -= t[2]
        
        credit_list = [amount for amount in credit_map.values() if amount != 0]
        n = len(credit_list)
        
        def dfs(cur):
            while cur < n and credit_list[cur] == 0:
                cur += 1
            if cur == n:
                return 0
            cost = float('inf')
            for nxt in range(cur + 1, n):
                if credit_list[nxt] * credit_list[cur] < 0:
                    credit_list[nxt] += credit_list[cur]
                    cost = min(cost, 1 + dfs(cur + 1))
                    credit_list[nxt] -= credit_list[cur]
            return cost
        
        return dfs(0)

Go solution

matched/original
package main

func minTransfers(transactions [][]int) int {
    creditMap := make(map[int]int)
    for _, t := range transactions {
        creditMap[t[0]] += t[2]
        creditMap[t[1]] -= t[2]
    }
    
    creditList := []int{}
    for _, amount := range creditMap {
        if amount != 0 {
            creditList = append(creditList, amount)
        }
    }
    
    n := len(creditList)
    var dfs func(int) int
    dfs = func(cur int) int {
        for cur < n && creditList[cur] == 0 {
            cur++
        }
        if cur == n {
            return 0
        }
        cost := int(^uint(0) >> 1)
        for nxt := cur + 1; nxt < n; nxt++ {
            if creditList[nxt] * creditList[cur] < 0 {
                creditList[nxt] += creditList[cur]
                cost = min(cost, 1 + dfs(cur + 1))
                creditList[nxt] -= creditList[cur]
            }
        }
        return cost
    }
    
    return dfs(0)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Explanation

Algorithm

Создать хеш-таблицу для хранения чистого баланса каждого человека.

Собрать все ненулевые чистые балансы в массив balance_list.

Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:

Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.

Если cur = n, вернуть 0.

В противном случае установить cost на большое значение, например, inf.

Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,

Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].

Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).

Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).

Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.

Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎