{x}
blog image

Minimum Money Required Before Transactions

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

Minimum Money Required Before Transactions

This problem asks to find the minimum initial amount of money needed to complete a series of transactions, regardless of the order in which they are performed. Each transaction has a cost and a cashback value. The key insight is understanding that the order of transactions doesn't matter if we have enough money initially.

Approach: Greedy Algorithm

The solution employs a greedy approach. The core idea is to pre-calculate the total "loss" from transactions where the cost exceeds the cashback. Then, for each transaction, we determine the maximum initial money needed considering this accumulated loss and the transaction's cost/cashback.

  1. Calculate Total Potential Loss: Iterate through the transactions. For each transaction [cost, cashback], if cost > cashback, accumulate the difference (cost - cashback) into a variable s. This s represents the total potential loss across all transactions where spending exceeds the return.

  2. Determine Maximum Initial Money: Iterate through the transactions again. For each transaction:

    • If cost > cashback (a loss-making transaction), the maximum money needed is the accumulated loss (s) plus the cashback (cashback). This ensures we can cover the accumulated losses and still complete the current transaction.
    • If cost <= cashback (a profitable transaction), the maximum money needed is the accumulated loss (s) plus the cost (cost). This guarantees we have enough to cover the potential losses and the cost of this transaction.

  3. Return the Maximum: The maximum value encountered in step 2 is the minimum initial money needed to handle all transactions regardless of their order.

Time and Space Complexity

  • Time Complexity: O(n), where n is the number of transactions. We iterate through the transactions twice.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python)

class Solution:
    def minimumMoney(self, transactions: List[List[int]]) -> int:
        s = sum(max(0, a - b) for a, b in transactions)  # Accumulate potential losses
        ans = 0
        for a, b in transactions:
            if a > b:
                ans = max(ans, s + b)  # Max money needed for loss-making transaction
            else:
                ans = max(ans, s + a)  # Max money needed for profitable transaction
        return ans

The code in other languages (Java, C++, Go, TypeScript, Rust, JavaScript) follows the same logic, only differing in syntax and data structures. The core greedy approach remains consistent across all implementations.