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.
In this approach, we'll consider each transaction and compute a net cost that incorporates the cost and cashback. The net cost is calculated as the difference between the cost and cashback. The key idea is to sort transactions in a way where those with potentially high net cost go first. We'll then simulate each transaction and ensure we have sufficient money at the start to successfully complete all transactions.
The code first sorts the transactions by their net cost in descending order. Each transaction's net cost is calculated as cost minus cashback. After sorting, iterate through the sorted transactions and calculate the minimum money required cumulatively.
Time Complexity: O(n log n), where n is the number of transactions due to sorting.
Space Complexity: O(1), aside from input storage.
This approach involves representing states and transitions akin to Dynamic Programming. We define possible states of transaction completion and determine the necessary cumulative funds required given all previous transactions. This uses state propagation concepts to answer combinations and record the minimum up-front funds dynamically.
In this C implementation, we focus on the idea of recording cumulative deficits represented by costs and cashbacks from transactions. We propagate a minimum fund measure per incomplete transaction sequence using a straightforward loop.
Time Complexity: O(n), as each transaction is processed exactly once.
Space Complexity: O(1), fixed space consumption.
First, we accumulate all negative profits, denoted as s. Then, we enumerate each transaction transactions[i] = [a, b] as the last transaction. If a > b, it means the current transaction is a loss, and this transaction has already been included when we accumulated the negative profits earlier. Therefore, we update the answer with s + b. Otherwise, we update the answer with s + a.
The time complexity is O(n), where n is the number of transactions. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Selection Based on Net Cost | Time Complexity: O(n log n), where n is the number of transactions due to sorting. |
| Approach 2: Dynamic Programming with State Representation | Time Complexity: O(n), as each transaction is processed exactly once. |
| Greedy | — |
| 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. |
2412. Minimum Money Required Before Transactions | Biweekly Contest 87 | LeetCode 2412 • Bro Coders • 1,650 views views
Watch 4 more video solutions →Practice Minimum Money Required Before Transactions with our built-in code editor and test cases.
Practice on FleetCode