Optimal account balancing

Array Dynamic Programming Backtracking Bit Manipulation Bitmask

50.4% acceptance

Mar 31, 2026

1531

164

No description available.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_transfers(transactions: Vec<Vec<i32>>) -> i32 {
    // Compute net balance for each person
    let mut balance = vec![0i32; 12];
    for t in &transactions {
      balance[t[0] as usize] -= t[2];
      balance[t[1] as usize] += t[2];
    }
    // Collect non-zero balances
    let debts: Vec<i32> = balance.into_iter().filter(|&x| x != 0).collect();

    let mut debts = debts;
    Self::dfs(&mut debts, 0)
  }

  fn dfs(debts: &mut Vec<i32>, start: usize) -> i32 {
    // Skip zeroes
    let mut start = start;
    while start < debts.len() && debts[start] == 0 {
      start += 1;
    }
    if start == debts.len() {
      return 0;
    }
    let mut min_txn = i32::MAX;
    let cur = debts[start];
    for i in (start + 1)..debts.len() {
      // Only settle with opposite sign to make progress
      if debts[i] * cur < 0 {
        debts[i] += cur;
        debts[start] = 0;
        let res = 1 + Self::dfs(debts, start + 1);
        if res < min_txn {
          min_txn = res;
        }
        debts[i] -= cur;
        debts[start] = cur;
        // Early termination: if debts[i] == -cur, it's fully settled (optimal for this branch)
        if debts[i] + cur == 0 {
          break;
        }
      }
    }
    if min_txn == i32::MAX { 0 } else { min_txn }
  }
}