Skip to main content
Talentd

Minimum Money Required Before Transactions - Solution & Explanation

HardArrayGreedySorting17 min readAsked at: Amazon
Practice this problem

Problem Statement

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

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), where n is the number of transactions due to sorting.
Space Complexity: O(1), aside from input storage.

Try this approach in the editor ā†’

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as each transaction is processed exactly once.
Space Complexity: O(1), fixed space consumption.

Try this approach in the editor ā†’

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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Approach 1: Greedy Selection Based on Net Cost

Time Complexity: O(n log n), where n is the number of transactions due to sorting.
Space Complexity: O(1), aside from input storage.

Approach 2: Dynamic Programming with State Representation

Time Complexity: O(n), as each transaction is processed exactly once.
Space Complexity: O(1), fixed space consumption.

Greedyā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Selection Based on Net CostO(n log n)O(1)Best general solution. Efficient for large inputs and the expected interview approach.
Dynamic Programming with State RepresentationO(nĀ²)O(n)Useful for understanding transaction ordering and verifying correctness before deriving the greedy insight.

Video Solution

2412. Minimum Money Required Before Transactions | Biweekly Contest 87 | LeetCode 2412 ā€¢ Bro Coders ā€¢ 1,672 views views

Watch 4 more video solutions ā†’

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.

Ready to solve this problem?

Practice Minimum Money Required Before Transactions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays