Easy backtracking + greedy solution with explanation (Python, Accepted)


  • 2
    A

    Just to share a backtracking + greedy solution. The Python implementation was accepted.

    First, compute net profit for every person.

    For transactions:
    [0, 1, 10]
    [2, 0, 5]
    
    Person, netProfit
    0,         -5
    1,         10
    2,         -5
    

    Then, preserve unsettled people only whose net profit != 0.

    Now backtrack to maintain the unsettled range [startIdx :]. Person X is settled means that X's net profit becomes 0 after one transaction with another unsettled person Y. Obviously, the amount of this transaction must be equal to X's net profit in their absolute values for X to be settled.

    Note that there may be some settled people within the unsettled range [startIdx :]. For instance, if someone within this unsettled range happened to be precisely closed out by someone else in the settled range.

    The greedy condition is precise closing-out (two people's net profit sum = 0). Since precise closing-out reduces number of unsettled people by 2 rather than 1, it is in fact the optimal condition.

    If greedy condition cannot be found, try non-greedy solutions.

    Comments can be found in the following implementation.

    class Solution(object):
        def minTransfers(self, transactions):
            # Compute net profit for every person.
            personNetProfit = dict()
            for lender, borrower, amount in transactions:
                personNetProfit[lender] = personNetProfit.get(lender, 0) - amount
                personNetProfit[borrower] = personNetProfit.get(borrower, 0) + amount
            # Preserve unsettled people only.
            netProfit = []
            for amount in personNetProfit.values():
                if amount != 0:
                    netProfit.append(amount)
            return self.traverse(netProfit, 0, 0)
        
        def traverse(self, netProfit, startIdx, numTrans):
            # Skip settled people.
            while startIdx < len(netProfit) and netProfit[startIdx] == 0:
                startIdx += 1
            if startIdx + 1 >= len(netProfit):
                return numTrans
            else:
                for i in range(startIdx + 1, len(netProfit)):
                    # Greedy condition.
                    if netProfit[startIdx] + netProfit[i] == 0:
                        netProfit[i] += netProfit[startIdx]
                        minNumTrans = self.traverse(netProfit, startIdx + 1, numTrans + 1)
                        netProfit[i] -= netProfit[startIdx]
                        return minNumTrans
                minNumTrans = sys.maxint
                for i in range(startIdx + 1, len(netProfit)):
                    # Non-greedy condition for possible closing out in the future.
                    if netProfit[startIdx] * netProfit[i] < 0:
                        netProfit[i] += netProfit[startIdx]
                        minNumTrans = min(minNumTrans, self.traverse(netProfit, startIdx + 1, numTrans + 1))
                        netProfit[i] -= netProfit[startIdx]
                return minNumTrans
    

  • 0
    R

    Thanks for the idea of greedy shortcut. This is my shorter version:

    def minTransfers(self, transactions):
        counter = collections.Counter()
        for f, t, m in transactions:
            counter[f] -= m
            counter[t] += m
        balances = counter.values()
        def dfs(b):
            if not b:
                return 0
            if not b[0]:
                return dfs(b[1:])
            for i in range(1, len(b)):
                if b[i] == -b[0]:
                    return 1 + dfs(b[1:i] + [0] + b[i+1:])
            ret = []
            for i in range(1, len(b)):
                if b[i] * b[0] < 0:
                    ret.append(dfs(b[1:i] + [b[i]+b[0]] + b[i+1:]))
            return 1+min(ret)
        
        return dfs(balances)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.