O(n) Rigorous Proof by Induction
If you don\'t understand why the solution by @lee215 works. \n\n\nclass Solution:\n    def minimumMoney(self, transactions: List[List[int]]) -> int:\n        re
If you don\'t understand why the [solution by @lee215](https://leetcode.com/problems/minimum-money-required-before-transactions/discuss/2588034/JavaC%2B%2BPython-Easy-and-Coincise) works. \n\n```\nclass Solution:\n    def minimumMoney(self, transactions: List[List[int]]) -> int:\n        return sum([max(0, c - b) for c, b in transactions]) + max(map(min, transactions))\n```\n**Theorem** The minimum money required for any permutation of transactions is `sum({cost[i] - cashback[i]: cost[i] >= cashback[i]}) + max(max({cashback[i]: cost[i] >= cashback[i]}), max({cost[i]: cashback[i] > cost[i]}))`\n***Proof***:\nIt\'s valid for any permutation of transactions by separating them into winning and losing streaks.\n* It\'s a valid start for any transcation, i.e., ` >= max(cost[i])`\n* If the first streak is winning, the remaining money is no smaller than any cost of the remaining transactions. \n* If the first streak is losing, the remaining money is still no smaller than any cost of the remaining transactions by Proposition 2. \n\n\n**Proposition 1** If all transactions are winning, i.e., for all `i`, `cashback[i] > cost[i]`, the minimum money required before transactions for any permutation is `max(cost[i])`, and the remaining money **must be** greater than `0`.\n***Proof***: \n* Since each transaction will increase our money, it is valid for any permutation of the winnig transactions to go through. \n* On the other hand, if the starting money is smaller than this, any permutation with the start of `max(cost[i])` will not be valid. \n\n\n**Proposition 2** If all transactions are losing, i.e., all `i`, `cost[i] >= cashback[i]`, the minimum money required before transactions for any permutation is `sum(cost[i] - cashback[i]) + max(cashback[i])`, and the remaining money **must be** `max(cashback[i])`.\n***Proof***:\n1. It is apparent when `n = 1`.\n2. Assume `P(k)` is true, let\'s consider `P(k+1)`:\nLet `m` denote the transaction with max cashback. \n\t* `sum({cost[i] - cashback[i]: i <= k+1}) + cashback[m]` is valid for any permutation of the `k+1` transactions:\n\tWithout loss of generality, assume the first transaction is `j`, the remaining money for the rest `k` transactions becomes \n\t`sum({cost[i] - cashback[i]: i <= k+1, i != j}) + cashback[m]`\n\t`>=` \n\t`sum({cost[i] - cashback[i]: i <= k+1, i != j}) + max({cashback[i]: i <= k+1, i != j})`, and it is enough by `P(k)`.\n\t* On the otherhand, the money cannot be lower than it because \n\t `sum({cost[i] - cashback[i]: i <= k+1}) + cashback[m]`  \n\t `=`\n\t `sum({cost[i] - cashback[i]: i <= k+1, i != m}) + cost[m] - cashback[m] + cashback[m]`\n\t `=`\n\t `sum({cost[i] - cashback[i]: i <= k+1, i != m}) + cost[m]`\n\t the first term can be `0`, and any value smaller than `cost[m]` won\'t be valid for the `k+1`-permutation starting with transaction `m`.\n\n\n\n\t \n\t \n
[]