Simplified Balances algorithm

video locked
Enroll to watch

5 mins

We discusse the problem of settling balances between six users and designing a payment graph to minimize the number of transactions.

The approach involves taking the largest positive and negative balances and eliminating them by making a transaction between them.

The data structure used is a heap, and the greedy approach is not optimal but has some advantages. We also show that a simple approach may not always be the best solution with an example.