Leetcode 465 Solution

This article provides solution to leetcode question 465 (optimal-account-balancing)
Categories:
Tags:
Access this page by simply typing in "lcs 465" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/optimal-account-balancing

Solution

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        m = collections.defaultdict(int)
        for src, dst, amount in transactions:
            m[src] -= amount
            m[dst] += amount



        acnts = []
        for i, asset in m.items():
            if asset == 0:
                continue
            acnts.append(asset)



        ans = float("inf")
        def pay(i, res):
            nonlocal acnts
            nonlocal ans



            if i == len(acnts):
                ans = min(ans, res)
                return



            if acnts[i] == 0:
                pay(i + 1, res)
                return



            for j in range(i + 1, len(acnts)):
                if acnts[i] * acnts[j] < 0:
                    acnts[j] += acnts[i]
                    pay(i + 1, res + 1)
                    acnts[j] -= acnts[i]



        pay(0, 0)



        return ans