465. Optimal Account Balancing

• 465. Optimal Account Balancing
  • Description
  • Intuition
  • Proof
  • Pitfall
  • Solution

Description

Here

Intuition

第一次做的时候感觉直接撸，其实还是有很多事情可以搞的。

解法很直接，就是统计所有的account的balance，然后greedily试图从之后每一个account settle掉

Proof

如果account 0 拥有100， account 1 为 -50， account 2 为-50

那么我们试的时候，

1. 直接把account 0全部给account 1，然后让account 1 settle down account 2
2. 将account 0分别给account 1 和 account 2

这两种方法花的步骤一样多的

Pitfall

Solution

52ms Solution

  public int minTransfers(int[][] transactions) {
    final Map<Integer, Long> idToBalance = new HashMap<>();
    for (final int[] t : transactions) {
      final int from = t[0], to = t[1], amount = t[2];
      idToBalance.put(from, idToBalance.getOrDefault(from, 0L) - amount);
      idToBalance.put(to, idToBalance.getOrDefault(to, 0L) + amount);
    }
    final List<Long> balances = new ArrayList<>();
    for (final Map.Entry<Integer, Long> e : idToBalance.entrySet()) {
      final long bal = e.getValue();
      if (bal != 0) {
        balances.add(bal);
      }
    }

    return dfs(balances, 0);
  }

  private static int dfs(final List<Long> balances, int start) {
    while (start < balances.size() && balances.get(start) == 0) {
      start++; // go next non zero;
    }
    int res = Integer.MAX_VALUE;
    for (int i = start + 1; i < balances.size(); i++) {
      if (balances.get(i) * balances.get(start) < 0) {
        balances.set(i, balances.get(i) + balances.get(start));
        res = Math.min(res, 1 + dfs(balances, start + 1));
        balances.set(i, balances.get(i) - balances.get(start));
      }
    }

    return res == Integer.MAX_VALUE ? 0 : res;
  }

3 ms Solution

public int minTransfers(int[][] transactions) {

    int max = 0;
    for (final int[] t : transactions) {
      final int from = t[0], to = t[1];
      max = Math.max(from, max);
      max = Math.max(to, max);
    }

    final long[] idToBalance = new long[max + 1];
    for (final int[] t : transactions) {
      final int from = t[0], to = t[1], amount = t[2];
      idToBalance[from] -= amount;
      idToBalance[to] += amount;
    }
    final List<Long> balances = new ArrayList<>();
    for (final long bal : idToBalance) {
      if (bal != 0) {
        balances.add(bal);
      }
    }

    return reduceExactMath(balances) + dfs(balances, 0);
  }

  private static int reduceExactMath(final List<Long> balances) {
    Collections.sort(balances);
    int res = 0;
    for (int i = 0, j = balances.size() - 1; i < j; ) {
      final long sum = balances.get(i) + balances.get(j);
      if (sum == 0) {
        balances.set(i, 0L);
        balances.set(j, 0L);
        i++;
        j--;
        res++;
      } else if (sum < 0) {
        i++;
      } else {
        j--;
      }
    }
    return res;
  }

  private static int dfs(final List<Long> balances, int start) {
    while (start < balances.size() && balances.get(start) == 0) {
      start++; // go next non zero;
    }
    int res = Integer.MAX_VALUE;
    for (int i = start + 1; i < balances.size(); i++) {
      if (balances.get(i) * balances.get(start) < 0) {
        balances.set(i, balances.get(i) + balances.get(start));
        res = Math.min(res, 1 + dfs(balances, start + 1));
        balances.set(i, balances.get(i) - balances.get(start));
      }
    }

    return res == Integer.MAX_VALUE ? 0 : res;
  }