HardArrayDynamic ProgrammingBacktrackingBit ManipulationBitmaskUpdated Sep 2026

465. Optimal Account Balancing

Asked at Salesforce, Pinterest

Difficulty

Hard

Time

O(3^n)

Space

O(2^n)

Pattern

Array

Companies

2

Problem

You get a list of transactions. Each entry [from, to, amount] means person from paid amount dollars to person to. These payments are history — they already happened.

Your job is to find the smallest number of new payments that would make everyone even. After those new payments, every person's net position must be zero: the total money they sent out equals the total money they received.

A payment can be between any two people, for any positive amount. You do not need to keep the original pairs. Return that minimum count as an integer.

Turn history into net balances

transactions[0,1,10][2,0,5]01Two past payments: 0 → 1 of 10, and 2 → 0 of 5.net balance5-105012Person 0 is +5, person 1 is -10, person 2 is +5. Theplus and minus values must cancel out.
Only the net amount each person is owed or owes matters; the individual payments do not.

Constraints

  • ●1 <= transactions.length <= 8
  • ●transactions[i].length == 3
  • ●0 <= fromi, toi < 12
  • ●fromi != toi
  • ●1 <= amounti <= 100

Examples

Example 1
Inputtransactions = [[0,1,10],[2,0,5]]
Output2
WhyPerson 0 is up 5 overall (gave 10, got 5). Person 1 is down 10. Person 2 is down 5. One payment cannot fix both 1 and 2 at once, so we need two payments: person 1 pays 5 to person 0, and person 1 pays 5 to person 2.
Example 2
Inputtransactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output1
WhyNet balances: person 0 is +4, person 1 is +4, person 2 is -8. Person 2 owes 8 total, and persons 0 and 1 are each owed 4. A single payment of 8 from person 2 to person 1 settles everyone, because person 1 can be treated as covering person 0's share.

Asked At

2 companies
CompanyDifficulty
SalesforceHardView all Salesforce questions →
PinterestHardView all Pinterest questions →

How to Think About It

1

First compute net balance for each person (sum of amounts lent minus borrowed)

2

People with zero net balance are irrelevant — remove them

3

The problem reduces to: split non-zero balances into minimum subsets that sum to zero

4

Brute force: try all 2^n subsets, check if subset sums to zero, then recurse on remaining

5

Optimize with bitmask DP: dp[mask] = min transactions to settle people in mask

Optimal Approach

Compute net balances for each person, filter out zeros. Use backtracking or bitmask DP to find the minimum number of transactions. The answer equals the minimum number of zero-sum subsets the balances can be partitioned into minus one (equivalently, min transactions = n - max number of independent zero-sum groups). With bitmask DP, dp[mask] = min(dp[mask], dp[mask ^ submask] + 1) for all submasks of mask that sum to zero.

Split balances into zero-sum groups

debtssum = 05-105012All three balances together sum to zero, but that isnot the best split.group A-10 + 5 ≠ 05-105012{1, 2} does not sum to zero, so it is not a validgroup.group {0,1,2}: sum 0 → 2 paymentsno smaller zero-sum group existsanswer = 2
Each group that sums to zero needs (size − 1) payments, so fewer groups means fewer payments.
ComplexityTime O(3^n)Space O(2^n)n is the number of people with a non-zero net balance (at most 12). The cost comes from iterating over every mask and its submasks.

What Trips People Up in Real Interviews

1

Simplify first: compute net balances, drop zeros

2

Key insight: minimum transactions = number of non-zero balances minus max zero-sum subsets

3

Backtracking with pruning: sort balances, skip duplicates

4

Bitmask approach: for each mask, try all submasks that sum to zero

5

Edge case: all balances zero means 0 transactions needed

Solution Code

O(3^n) time
class Solution:
    def minTransfers(self, transactions: list[list[int]]) -> int:
        from collections import defaultdict
        balance = defaultdict(int)
        for f, t, a in transactions:
            balance[f] -= a
            balance[t] += a
        debts = [v for v in balance.values() if v != 0]
        n = len(debts)
        if n == 0:
            return 0
        dp = [float('inf')] * (1 << n)
        dp[0] = 0
        for mask in range(1 << n):
            if dp[mask] == float('inf'):
                continue
            total = 0
            picked = []
            for i in range(n):
                if mask & (1 << i):
                    total += debts[i]
                    picked.append(i)
            if total == 0 and picked:
                dp[mask] = min(dp[mask], len(picked) - 1)
            for submask in range(mask + 1, 1 << n):
                if (submask & mask) != submask:
                    continue
                s = 0
                for i in range(n):
                    if submask & (1 << i):
                        s += debts[i]
                if s == 0:
                    dp[mask | submask] = min(dp[mask | submask], dp[mask] + bin(submask).count('1') - 1)
        return dp[(1 << n) - 1]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Optimal Account Balancing problem?

A group of friends went on a trip and borrowed/lent money from each other. Given a list of transactions where transactions[i] = [from, to, amount], find the minimum number of transactions needed to settle all debts. Each transaction involves transferring money from one person to another.

How do you solve Optimal Account Balancing?

The optimal approach runs in O(3^n) time and O(2^n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Optimal Account Balancing?

Optimal Account Balancing is asked at Salesforce, Pinterest. It is a hard difficulty problem.

What are common mistakes on Optimal Account Balancing?
  • Simplify first: compute net balances, drop zeros
  • Key insight: minimum transactions = number of non-zero balances minus max zero-sum subsets
  • Backtracking with pruning: sort balances, skip duplicates
  • Bitmask approach: for each mask, try all submasks that sum to zero
  • Edge case: all balances zero means 0 transactions needed