Optimal Account Balancing - Practice Coding Problems

Optimal Account Balancing - Problem

You are given an array of transactions transactions where transactions[i] = [from_i, to_i, amount_i] indicates that the person with ID = from_i gave amount_i $ to the person with ID = to_i.

Return the minimum number of transactions required to settle the debt.

A debt is settled when the net balance of each person becomes zero. Multiple transactions between the same people are allowed.

Input & Output

Example 1 — Basic Three Person Settlement

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

› Output: 2

💡 Note: Person 0 gave $10 to person 1 and received $5 from person 2. Net balances: Person 0: -$5, Person 1: +$10, Person 2: -$5. Person 1 pays $5 to person 0, and person 1 pays $5 to person 2. Minimum 2 transactions needed.

Example 2 — Already Settled

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

› Output: 1

💡 Note: Net balances: Person 0: -$5, Person 1: +$4, Person 2: $0, Person 0 (unnamed): +$1. After calculating all balances, only 1 transaction needed to settle remaining debts.

Example 3 — No Settlements Needed

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

› Output: 0

💡 Note: This forms a cycle: person 0 → person 1 → person 2 → person 0. All net balances are zero, so no additional transactions needed.

Constraints

1 ≤ transactions.length ≤ 8
transactions[i].length == 3
0 ≤ from_i, to_i < 12
from_i ≠ to_i
1 ≤ amount_i ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Initial Transactions

People make payments to each other

Calculate Net Balances

Determine who owes money and who is owed

Optimal Settlement

Find minimum transactions to settle all debts

Key Takeaway

🎯 Key Insight: Only people with non-zero balances need to make settlement transactions

Asked in

I Intuit 15 U Uber 8 P PayPal 6

The key insight is that only people with non-zero net balances need to participate in settlement transactions. We calculate each person's net balance, then use backtracking to find the minimum number of transactions needed. Best approach uses optimized backtracking with pruning. Time: O(n!), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Backtracking with Pruning	O(n!)	O(n)	Use backtracking with early pruning to reduce search space
Backtracking with All Permutations	O(n!)	O(n)	Try every possible way to settle debts between all people

Optimized Backtracking with Pruning — Algorithm Steps

Step 1: Calculate net balances and filter non-zero
Step 2: Sort debts by absolute value (largest first)
Step 3: Backtrack with pruning when path exceeds current minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Amount

Process larger debts first for better pruning

Early Pruning

Stop exploring paths that exceed current minimum

Skip Zeros

Skip settled balances during recursion

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minTxns;

int compare(const void* a, const void* b) {
    int x = *(int*)a, y = *(int*)b;
    int absX = x < 0 ? -x : x;
    int absY = y < 0 ? -y : y;
    return absY - absX; // Sort by absolute value descending
}

void backtrack(int* debts, int size, int idx, int txnCount) {
    // Early pruning: if current path already exceeds minimum, stop
    if (txnCount >= minTxns) {
        return;
    }
    
    // Skip zero balances
    while (idx < size && debts[idx] == 0) {
        idx++;
    }
    
    if (idx >= size) {
        if (txnCount < minTxns) {
            minTxns = txnCount;
        }
        return;
    }
    
    // Try pairing current person with all others
    for (int i = idx + 1; i < size; i++) {
        if (debts[i] * debts[idx] < 0) {  // Different signs
            debts[i] += debts[idx];  // Settle debt
            backtrack(debts, size, idx + 1, txnCount + 1);
            debts[i] -= debts[idx];  // Backtrack
        }
    }
}

int solution(int transactions[][3], int txnSize) {
    // Simple hash using array (assuming person IDs are small)
    int balance[1000] = {0};
    int maxId = 0;
    
    for (int i = 0; i < txnSize; i++) {
        int fromId = transactions[i][0], toId = transactions[i][1], amount = transactions[i][2];
        balance[fromId] -= amount;
        balance[toId] += amount;
        if (fromId > maxId) maxId = fromId;
        if (toId > maxId) maxId = toId;
    }
    
    // Get all non-zero balances
    int debts[1000];
    int debtCount = 0;
    for (int i = 0; i <= maxId; i++) {
        if (balance[i] != 0) {
            debts[debtCount++] = balance[i];
        }
    }
    
    // Sort by absolute value (largest first)
    qsort(debts, debtCount, sizeof(int), compare);
    
    if (debtCount == 0) {
        return 0;
    }
    
    minTxns = INT_MAX;
    backtrack(debts, debtCount, 0, 0);
    return minTxns;
}

int main() {
    // Simple parsing - read the array manually
    int transactions[100][3];
    int txnCount = 0;
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse basic format
    char* ptr = line + 1; // Skip first [
    while (*ptr && txnCount < 100) {
        if (*ptr == '[') {
            ptr++;
            transactions[txnCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            transactions[txnCount][1] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            transactions[txnCount][2] = atoi(ptr);
            txnCount++;
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(transactions, txnCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Still factorial in worst case but with significant pruning in practice

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map for balances and recursion call stack depth

⚡ Linearithmic Space

22.0K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Backtracking with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler