Minimum Money Required Before Transactions solution and explanation
4 more videos on this problem
2412. Minimum Money Required Before Transactions | Biweekly Contest 87 | LeetCode 2412Bro Coders · 14:00 · 1K views
Leetcode BiWeekly contest 87 - Hard - Minimum Money Required Before TransactionsPrakhar Agrawal · 11:18 · 724 views
2412. Minimum Money Required Before Transactions || Leetcode DSA || C++ Code || Think then CodeThink then Code · 19:34 · 723 views
2412. Minimum Money Required Before Transactions (Leetcode Hard)Programming Live with Larry · 1:26:07 · 494 views
【每日一题】LeetCode 2412. Minimum Money Required Before TransactionsHuifeng Guan · 23:08 · 482 views
The problem
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 <= 109
Approach overview
Problem 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 1: Approach 1: Greedy Selection Based on Net Cost
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.
def minMoneyRequired(transactions):
transactions.sort(key=lambda x: x[0] - x[1], reverse=True)
total_cost = 0
min_money = 0
for cost, cashback in transactions:
total_cost += cost
min_money = max(min_money, total_cost - cashback)
return min_money
transactions = [[2, 1], [5, 0], [4, 2]]
print(f"Minimum money required: {minMoneyRequired(transactions)}")import java.util.Arrays;
public class Main {
public static int minMoneyRequired(int[][] transactions) {
Arrays.sort(transactions, (a, b) -> (b[0] - b[1]) - (a[0] - a[1]));
int totalCost = 0;
int minMoney = 0;
for (int[] transaction : transactions) {
totalCost += transaction[0];
minMoney = Math.max(minMoney, totalCost - transaction[1]);
}
return minMoney;
}
public static void main(String[] args) {
int[][] transactions = {{2, 1}, {5, 0}, {4, 2}};
System.out.println("Minimum money required: " + minMoneyRequired(transactions));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minMoneyRequired(vector<vector<int>>& transactions) {
sort(transactions.begin(), transactions.end(), [](const vector<int>& a, const vector<int>& b) {
return (a[0] - a[1]) > (b[0] - b[1]);
});
int totalCost = 0;
int minMoney = 0;
for (auto& transaction : transactions) {
totalCost += transaction[0];
minMoney = max(minMoney, totalCost - transaction[1]);
}
return minMoney;
}
int main() {
vector<vector<int>> transactions = {{2, 1}, {5, 0}, {4, 2}};
cout << "Minimum money required: " << minMoneyRequired(transactions) << endl;
return 0;
}function minMoneyRequired(transactions) {
transactions.sort((a, b) => (b[0] - b[1]) - (a[0] - a[1]));
let totalCost = 0;
let minMoney = 0;
for (let transaction of transactions) {
totalCost += transaction[0];
minMoney = Math.max(minMoney, totalCost - transaction[1]);
}
return minMoney;
}
let transactions = [[2, 1], [5, 0], [4, 2]];
console.log(`Minimum money required: ${minMoneyRequired(transactions)}`);#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int *tx1 = (int *)a;
int *tx2 = (int *)b;
int netCost1 = tx1[0] - tx1[1];
int netCost2 = tx2[0] - tx2[1];
return netCost2 - netCost1; // sort descending by net cost
}
int minMoneyRequired(int transactions[][2], int size) {
qsort(transactions, size, sizeof(transactions[0]), cmp);
int totalCost = 0;
int minMoney = 0;
for (int i = 0; i < size; i++) {
totalCost += transactions[i][0];
minMoney = totalCost - transactions[i][1] > minMoney ? totalCost - transactions[i][1] : minMoney;
}
return minMoney;
}
int main() {
int transactions[][2] = {{2, 1}, {5, 0}, {4, 2}};
int size = sizeof(transactions) / sizeof(transactions[0]);
printf("Minimum money required: %d\n", minMoneyRequired(transactions, size));
return 0;
}using System;
class Program {
static int MinMoneyRequired(int[][] transactions) {
Array.Sort(transactions, (a, b) => (b[0] - b[1]).CompareTo(a[0] - a[1]));
int totalCost = 0;
int minMoney = 0;
foreach (var transaction in transactions) {
totalCost += transaction[0];
minMoney = Math.Max(minMoney, totalCost - transaction[1]);
}
return minMoney;
}
static void Main() {
int[][] transactions = new int[][] { new int[] { 2, 1 }, new int[] { 5, 0 }, new int[] { 4, 2 } };
Console.WriteLine("Minimum money required: " + MinMoneyRequired(transactions));
}
}The Python solution sorts and processes the transactions in a way that each transaction is evaluated based on its net cost. The minimum starting money is determined by accumulating total cost and deducting with cashback optimally.
Time Complexity: O(n log n), for sorting.
Space Complexity: O(1), extra space is minimal.
Approach 2: Approach 2: Dynamic Programming with State Representation
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.
def minMoneyRequired(transactions):
min_money = 0
running_cost = 0
for cost, cashback in transactions:
running_cost += (cost - cashback)
min_money = max(min_money, running_cost)
return min_money
transactions = [[3, 0], [0, 3]]
print(f"Minimum money required: {minMoneyRequired(transactions)}")public class Main {
public static int minMoneyRequired(int[][] transactions) {
int minMoney = 0, runningCost = 0;
for (int[] transaction : transactions) {
runningCost += (transaction[0] - transaction[1]);
minMoney = Math.max(runningCost, minMoney);
}
return minMoney;
}
public static void main(String[] args) {
int[][] transactions = {{3, 0}, {0, 3}};
System.out.println("Minimum money required: " + minMoneyRequired(transactions));
}
}#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int minMoneyRequired(vector<vector<int>>& transactions) {
int minMoney = 0, runningCost = 0;
for (auto& transaction : transactions) {
runningCost += (transaction[0] - transaction[1]);
if (runningCost > minMoney) {
minMoney = runningCost;
}
}
return minMoney;
}
int main() {
vector<vector<int>> transactions = {{3, 0}, {0, 3}};
cout << "Minimum money required: " << minMoneyRequired(transactions) << endl;
return 0;
}function minMoneyRequired(transactions) {
let minMoney = 0;
let runningCost = 0;
for (let [cost, cashback] of transactions) {
runningCost += (cost - cashback);
minMoney = Math.max(minMoney, runningCost);
}
return minMoney;
}
let transactions = [[3, 0], [0, 3]];
console.log(`Minimum money required: ${minMoneyRequired(transactions)}`);#include <stdio.h>
#include <limits.h>
int minMoneyRequired(int transactions[][2], int size) {
int money = 0, possibleCost = 0;
for (int i = 0; i < size; i++) {
possibleCost += (transactions[i][0] - transactions[i][1]);
if (possibleCost > money) {
money += possibleCost - money;
}
}
return money;
}
int main() {
int transactions[][2] = {{3, 0}, {0, 3}};
int size = sizeof(transactions) / sizeof(transactions[0]);
printf("Minimum money required: %d\n", minMoneyRequired(transactions, size));
return 0;
}using System;
class Program {
static int MinMoneyRequired(int[][] transactions) {
int minMoney = 0, runningCost = 0;
foreach (var transaction in transactions) {
runningCost += (transaction[0] - transaction[1]);
minMoney = Math.Max(minMoney, runningCost);
}
return minMoney;
}
static void Main() {
int[][] transactions = new int[][] { new int[] { 3, 0 }, new int[] { 0, 3 } };
Console.WriteLine("Minimum money required: " + MinMoneyRequired(transactions));
}
}Implementing in Python utilizes similar logic, identifying cumulative costs with cashback reductions to evaluate the maximum necessary upfront money value from differential state propagation.
Time Complexity: O(n), as we iterate once.
Space Complexity: O(1), since only a few additional variables are used.
Approach 3: Greedy
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).
function minimumMoney(transactions: number[][]): number {
const s = transactions.reduce((acc, [a, b]) => acc + Math.max(0, a - b), 0);
let ans = 0;
for (const [a, b] of transactions) {
if (a > b) {
ans = Math.max(ans, s + b);
} else {
ans = Math.max(ans, s + a);
}
}
return ans;
}func minimumMoney(transactions [][]int) int64 {
s, ans := 0, 0
for _, e := range transactions {
s += max(0, e[0]-e[1])
}
for _, e := range transactions {
if e[0] > e[1] {
ans = max(ans, s+e[1])
} else {
ans = max(ans, s+e[0])
}
}
return int64(ans)
}impl Solution {
pub fn minimum_money(transactions: Vec<Vec<i32>>) -> i64 {
let mut s: i64 = 0;
for transaction in &transactions {
let (a, b) = (transaction[0], transaction[1]);
s += (a - b).max(0) as i64;
}
let mut ans = 0;
for transaction in &transactions {
let (a, b) = (transaction[0], transaction[1]);
if a > b {
ans = ans.max(s + b as i64);
} else {
ans = ans.max(s + a as i64);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Selection Based on Net Cost | Time Complexity: O(n log n), for sorting. |
| Approach 2: Dynamic Programming with State Representation | Time Complexity: O(n), as we iterate once. |
| Greedy | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Money Required Before Transactions easy or hard?
The problem is classified as Hard on LeetCode because the greedy insight is not immediately obvious. Many developers initially try simulation or dynamic programming before recognizing the optimal ordering strategy. Once the loss vs profit observation is clear, the implementation becomes straightforward.
Minimum Money Required Before Transactions Python/Java solution
The greedy algorithm can be implemented easily in Python, Java, C++, C#, or JavaScript. Sort transactions based on their net loss characteristics, iterate through them, and track the maximum required balance before executing each transaction. The core logic is only a few lines once the ordering rule is defined.
How to solve Minimum Money Required Before Transactions in O(n)?
A linear scan solution is possible by separating loss transactions and profitable ones. Sum the total losses from transactions where cost > cashback and track the maximum cost requirement among them. Combine that with the largest upfront requirement from profitable transactions to compute the minimum starting money. This reasoning reduces sorting overhead and works in O(n) time.
What is the best approach for Minimum Money Required Before Transactions?
The greedy strategy based on net transaction loss is the most efficient approach. Separate transactions where cost exceeds cashback and process the worst losses first while delaying profitable ones. This ensures you reserve enough money for the most expensive requirement. The typical implementation runs in O(n log n) time due to sorting.
Is Minimum Money Required Before Transactions asked at Google/Amazon/Meta?
Problems involving transaction ordering, greedy optimization, and minimum starting balance appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this problem test whether candidates can recognize greedy patterns and reason about worst-case ordering scenarios.
What data structure is used in Minimum Money Required Before Transactions?
The solution primarily uses arrays to store transactions and optionally sorting to reorder them. No complex data structures are required. The algorithm relies on greedy reasoning and simple iteration to track the maximum required balance.
What is the time complexity of Minimum Money Required Before Transactions?
The optimal greedy solution runs in O(n log n) time because transactions are sorted based on their cost and cashback relationship. After sorting, a single pass calculates the maximum required upfront money. Space complexity is O(1) apart from the input storage.