2412

2412. Minimum Money Required Before Transactions (Hard)

You are given a 0-indexed 2D integer array transactions, where transactions[i] = [costi, cashbacki].

The array describes transactions, where each transaction must be completed exactly once in some order. At any given moment, you have a certain amount of money. In order to complete transaction i, money >= costi must hold true. After performing a transaction, money becomes money - costi + cashbacki.

Return the minimum amount of money required before any transaction so that all of the transactions can be completed regardless of the order of the transactions.

 

Example 1:

Input: transactions = [[2,1],[5,0],[4,2]]
Output: 10
Explanation:
Starting with money = 10, the transactions can be performed in any order.
It can be shown that starting with money < 10 will fail to complete all transactions in some order.

Example 2:

Input: transactions = [[3,0],[0,3]]
Output: 3
Explanation:
- If transactions are in the order [[3,0],[0,3]], the minimum money required to complete the transactions is 3.
- If transactions are in the order [[0,3],[3,0]], the minimum money required to complete the transactions is 0.
Thus, starting with money = 3, the transactions can be performed in any order.

 

Constraints:

• 1 <= transactions.length <= 105
• transactions[i].length == 2
• 0 <= costi, cashbacki <= 109

Companies: Amazon

Related Topics:
Array, Greedy, Sorting

Solution 1.

Intuition

The worst case is that we do losing transactions first and then do winning transactions.

Algorithm

https://leetcode.com/problems/minimum-money-required-before-transactions/solutions/2588034/java-c-python-easy-and-coincise/comments/1606909

First, assume all the transactions have cost >= cashback, that is we never gain any money from any transactions.

1. for (auto& a : A) res += a[0] - a[1];, accumulate all the possible losses
   • Yet res is not the final answer. As we use up all cashback (that is, the - a[1] part), but we can't actually use the cashback of the last transaction, there's no more transactions left for us to spend it on!
2. for (auto& a : A) v = max(v, a[1]);, find max cashback, let the transaction with max cashback be the very last one
3. res + v will be the answer

Second, assume in all transactions we have cost < cashback, that is, we always gain money.

1. res = 0 (just to keep it symmetric)
2. for (auto& a : A) v = max(v, a[0]); find the max cost of any transactions, we only need enough money to do the very first transaction
3. res + v will be the answer

Finally, assume we have some transactions that we lose money and some that we gain money.

1. for (auto& a : A) res += max(a[0] - a[1], 0); accumulate all the possible losses from transactions that we lose money
2. for (auto& a : A) v = max(v, min(a[0], a[1]));, find the larger of max cashback from transactions that we lose money or max cost from transactions that we gain money, the intuition is:
   1. For the worst-case scenario, we first do all the transactions that we lose money, then we do transactions that gain money
      • To get pass all the losing transactions, v needs to be at least max cashback from transactions that we lose money, see the first scenario
      • To start the very first transactions that we can gain money, v needs to be at least max cost from transactions that we gain money, see the second scenario
   2. In the end, v should be the larger of max cashback from transactions that we lose money or max cost from transactions that we gain money, as the larger one can cover the smaller one. To get the larger one:
      • For transaction we lose money (a[0] >= a[1]), doing min(a[0], a[1]) gives a[1], that is, the cashback.
      • For transaction we gain money (a[0] < a[1]), doing min(a[0], a[1]) gives a[0], that is, the cost
      • That's where the confusing v = max(v, min(a[0], a[1])) comes from
3. res + v will be the answer

// OJ: https://leetcode.com/problems/minimum-money-required-before-transactions
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/minimum-money-required-before-transactions/solutions/2588034
class Solution {
public:
    long long minimumMoney(vector<vector<int>>& A) {
        long long ans = 0;
        int v = 0;
        for (auto &t: A) {
            v = max(v, min(t[0], t[1]));
            ans += max(t[0] - t[1], 0);
        }
        return ans + v;
    }
}