Watch 5 video solutions for Minimum Money Required Before Transactions, a hard level problem involving Array, Greedy, Sorting. This walkthrough by Bro Coders has 1,650 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105transactions[i].length == 20 <= costi, cashbacki <= 109Problem Overview: You receive a list of transactions where each transaction requires cost money upfront and returns cashback afterward. The goal is to determine the minimum amount of money you must start with so you can perform every transaction in some order without your balance ever going negative.
Approach 1: Greedy Selection Based on Net Cost (O(n log n) time, O(1) extra space)
This approach observes that transactions where cost > cashback permanently reduce your money. Those "loss" transactions are dangerous and should be handled carefully. Sort transactions so the worst losses are processed first, ensuring you always reserve enough money for them. While iterating, track the maximum upfront requirement needed before each transaction. The key insight: profitable transactions (cashback ≥ cost) can be delayed because they never reduce your total money. This greedy ordering guarantees the minimum initial balance required. The implementation relies on iterating the array, ordering transactions with sorting, and applying a simple greedy rule to track the worst-case requirement.
Approach 2: Dynamic Programming with State Representation (O(n²) time, O(n) space)
Dynamic programming models the problem as states representing which transactions have already been completed and the minimum money required to reach that state safely. Each transition simulates performing another transaction and updates the required starting balance based on the remaining funds after paying the cost and receiving cashback. This method systematically explores possible orders while caching results to avoid recomputation. Although correct, the DP state transitions introduce higher overhead compared to the greedy insight. The approach is useful when reasoning about ordering constraints or when the greedy pattern is not immediately obvious.
Recommended for interviews: The greedy approach is what most interviewers expect. It demonstrates the key insight about separating loss-making and profitable transactions and minimizing the worst upfront requirement. Discussing the DP formulation first can show deeper understanding of ordering problems, but the greedy solution highlights strong algorithmic intuition and delivers the optimal complexity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Selection Based on Net Cost | O(n log n) | O(1) | Best general solution. Efficient for large inputs and the expected interview approach. |
| Dynamic Programming with State Representation | O(n²) | O(n) | Useful for understanding transaction ordering and verifying correctness before deriving the greedy insight. |