# Minimum Money Required Before Transactions
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-money-required-before-transactions)
Canonical: https://scaleengineer.com/dsa/problems/minimum-money-required-before-transactions
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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 <= 105`
* `transactions[i].length == 2`
* `0 <= costi, cashbacki <= 109`

# Approaches
## Brute-Force by Checking All Permutations
The most straightforward, albeit inefficient, way to solve this problem is to simulate every possible scenario. Since the transactions can be performed in any order, we can generate all permutations of the transactions. For each permutation, we calculate the minimum amount of money required to complete the transactions in that specific order. The final answer is the maximum of these requirements over all possible permutations, as this represents the amount needed to succeed regardless of the order.
**Time:** O(N! * N). There are N! permutations, and for each one, we iterate through N transactions to calculate its requirement. This is computationally prohibitive for N > 12. · **Space:** O(N), where N is the number of transactions. This space is used for the recursion stack during permutation generation and to store a copy of the transactions list.
**Pros:** Guaranteed to find the correct answer as it exhaustively checks every possibility.; The logic is a direct translation of the problem statement.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints (N up to 10^5).; Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
### Explanation
This method explores the entire search space of transaction orderings. We can use a backtracking algorithm to generate each of the N! permutations of the transactions. For each complete permutation, we perform a simulation. In the simulation, we track the cumulative net loss incurred from the transactions performed so far. At any step `k`, to perform transaction `T_k`, we must have enough money to cover its cost `cost_k` plus the total net loss from the previous `k-1` transactions. The peak requirement for a single permutation is the maximum such value encountered during its execution. We then take the maximum of these peak requirements over all N! permutations to find our answer.

```java
import java.util.Collections;
import java.util.ArrayList;
import java.util.List;

class Solution {
    long maxRequired = 0;

    public long minimumMoney(int[][] transactions) {
        List<int[]> transList = new ArrayList<>();
        for (int[] t : transactions) {
            transList.add(t);
        }
        permute(transList, 0);
        return maxRequired;
    }

    private void permute(List<int[]> arr, int k) {
        if (k == arr.size()) {
            calculateRequirementForPermutation(arr);
            return;
        }
        for (int i = k; i < arr.size(); i++) {
            Collections.swap(arr, i, k);
            permute(arr, k + 1);
            Collections.swap(arr, k, i); // backtrack
        }
    }

    private void calculateRequirementForPermutation(List<int[]> permutation) {
        long currentPermutationMax = 0;
        long cumulativeLoss = 0;
        for (int[] trans : permutation) {
            long cost = trans[0];
            long cashback = trans[1];
            long requiredNow = cost + cumulativeLoss;
            if (requiredNow > currentPermutationMax) {
                currentPermutationMax = requiredNow;
            }
            cumulativeLoss += (cost - cashback);
        }
        if (currentPermutationMax > maxRequired) {
            maxRequired = currentPermutationMax;
        }
    }
}
```
### Algorithm
*   Define a recursive function, say `generatePermutations`, that generates all possible orderings (permutations) of the transactions.
*   For each generated permutation:
    *   Initialize `maxRequirementForPermutation = 0` and `cumulativeLoss = 0`.
    *   Iterate through the transactions in the current permutation's order.
    *   For each transaction `[cost, cashback]`:
        *   Calculate the money needed at this step: `neededNow = cost + cumulativeLoss`.
        *   Update the maximum requirement for this specific permutation: `maxRequirementForPermutation = max(maxRequirementForPermutation, neededNow)`.
        *   Update the cumulative loss: `cumulativeLoss += cost - cashback`.
    *   After iterating through the permutation, update the overall maximum requirement: `overallMaxRequirement = max(overallMaxRequirement, maxRequirementForPermutation)`.
*   The final result is `overallMaxRequirement`.

## Greedy Approach with Sorting
A significant improvement over brute force is to identify a potential worst-case ordering and test only that. The intuition is that the financial situation is most dire when we perform transactions that result in a net loss of money first. This accumulates a large deficit that must be covered by our initial capital. Among these 'losing' transactions, it's plausible that tackling the ones with lower cashback first is worse, as they provide less of a monetary 'rebound' after paying the high cost. This leads to a greedy strategy: sort the losing transactions by cashback and place them before all 'profitable' transactions, then calculate the requirement for this specific order.
**Time:** O(N log N), dominated by the sorting of the `losingTransactions` list. In the worst case, all transactions could be losing, leading to sorting N elements. · **Space:** O(N), to store the `losingTransactions` and `profitableTransactions` lists.
**Pros:** Much more efficient than brute-force, with a polynomial time complexity.; Correctly solves the problem by identifying a valid worst-case permutation.
**Cons:** Requires O(N) extra space to store the partitioned lists.; Slower than the optimal linear-time solution due to the sorting step.
### Explanation
This approach refines the problem by hypothesizing a structure for the worst-case permutation. We segregate transactions into two categories: those that lose money (`cost > cashback`) and those that are profitable or neutral (`cost <= cashback`). The core idea is that to maximize the required starting capital, we should front-load all the net losses. The constructed worst-case permutation, therefore, consists of all losing transactions followed by all profitable ones. Within the losing group, we sort by `cashback` ascendingly. We then simulate this single, carefully constructed permutation. The maximum capital needed at any point during this simulation is the answer.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

class Solution {
    public long minimumMoney(int[][] transactions) {
        List<int[]> losing = new ArrayList<>();
        List<int[]> profitable = new ArrayList<>();

        for (int[] t : transactions) {
            if (t[0] > t[1]) {
                losing.add(t);
            } else {
                profitable.add(t);
            }
        }

        // Sort losing transactions by cashback ascending
        Collections.sort(losing, (a, b) -> Integer.compare(a[1], b[1]));

        List<int[]> worstCasePermutation = new ArrayList<>(losing);
        worstCasePermutation.addAll(profitable);

        long maxRequired = 0;
        long cumulativeLoss = 0;

        for (int[] t : worstCasePermutation) {
            long cost = t[0];
            long cashback = t[1];
            maxRequired = Math.max(maxRequired, cost + cumulativeLoss);
            cumulativeLoss += (cost - cashback);
        }

        return maxRequired;
    }
}
```
### Algorithm
*   Create two lists: `losingTransactions` for transactions where `cost > cashback`, and `profitableTransactions` for transactions where `cost <= cashback`.
*   Iterate through the input `transactions` and populate the two lists.
*   Sort the `losingTransactions` list in ascending order based on their `cashback` value.
*   Construct a new list representing the worst-case permutation by appending `profitableTransactions` to the end of the sorted `losingTransactions`.
*   Simulate this single permutation to find its maximum money requirement:
    *   Initialize `maxRequirement = 0` and `cumulativeLoss = 0` (use `long` type).
    *   For each transaction `[cost, cashback]` in the constructed list:
        *   `maxRequirement = max(maxRequirement, cost + cumulativeLoss)`.
        *   `cumulativeLoss += cost - cashback`.
*   Return `maxRequirement`.

## Optimal Single-Pass Approach
The most efficient solution involves a logical deduction about the nature of the worst-case requirement, avoiding any explicit permutation generation or sorting. We can determine the minimum required money by analyzing the two most challenging scenarios that could arise during any sequence of transactions. This allows us to calculate the result in a single pass through the input array.
**Time:** O(N), where N is the number of transactions, because we iterate through the list only once. · **Space:** O(1), as it only requires a few variables to store the aggregated values, regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Handles large inputs efficiently.
**Cons:** The logic is less intuitive than the other approaches and requires a careful derivation to understand its correctness.
### Explanation
The core insight is that the money required to perform any transaction `j`, after a set of transactions `S` has been completed, is `cost_j + sum_{i in S} (cost_i - cashback_i)`. To find the minimum initial money that covers all possibilities, we must find the maximum value of this expression across all valid `S` and `j`.

To maximize this value, the `sum` term should be as large as possible. This occurs when the set `S` contains only transactions with a net loss (`cost > cashback`), as profitable transactions would decrease the sum. This simplifies the problem into two main worst-case scenarios:

1.  **A profitable transaction `j` is performed after all losing transactions**: The set `S` contains all losing transactions. The required money is `cost_j + TotalLoss`. To find the peak requirement for this scenario, we must consider the profitable transaction with the highest cost. This gives a requirement of `max(cost_j for profitable j) + TotalLoss`.

2.  **A losing transaction `j` is performed after all *other* losing transactions**: The set `S` contains all losing transactions except `j`. The required money is `cost_j + (TotalLoss - (cost_j - cashback_j))`, which simplifies to `cashback_j + TotalLoss`. To find the peak requirement, we must consider the losing transaction with the highest cashback. This gives a requirement of `max(cashback_j for losing j) + TotalLoss`.

The overall minimum money required is the maximum of these two cases.

```java
class Solution {
    public long minimumMoney(int[][] transactions) {
        long totalLoss = 0;
        long maxCostOfProfitable = 0;
        long maxCashbackOfLosing = 0;

        for (int[] t : transactions) {
            long cost = t[0];
            long cashback = t[1];

            if (cost > cashback) { // Losing transaction
                totalLoss += (cost - cashback);
                maxCashbackOfLosing = Math.max(maxCashbackOfLosing, cashback);
            } else { // Profitable or neutral transaction
                maxCostOfProfitable = Math.max(maxCostOfProfitable, cost);
            }
        }

        // The final answer is the total loss from all losing transactions,
        // plus the additional amount needed for the single most demanding step.
        return totalLoss + Math.max(maxCashbackOfLosing, maxCostOfProfitable);
    }
}
```
### Algorithm
*   Initialize three `long` variables: `totalLoss = 0`, `maxCostOfProfitable = 0`, `maxCashbackOfLosing = 0`.
*   Iterate through each transaction `[cost, cashback]`:
    *   If `cost > cashback` (it's a losing transaction):
        *   Add the net loss to `totalLoss`: `totalLoss += cost - cashback`.
        *   Update the maximum cashback seen so far for a losing transaction: `maxCashbackOfLosing = max(maxCashbackOfLosing, cashback)`.
    *   Else (it's a profitable or neutral transaction):
        *   Update the maximum cost seen so far for a profitable transaction: `maxCostOfProfitable = max(maxCostOfProfitable, cost)`.
*   The final result is `totalLoss + max(maxCashbackOfLosing, maxCostOfProfitable)`.

# Solutions
### Java

```java
class Solution {
public
  long minimumMoney(int[][] transactions) {
    long s = 0;
    for (var e : transactions) {
      s += Math.max(0, e[0] - e[1]);
    }
    long ans = 0;
    for (var e : transactions) {
      if (e[0] > e[1]) {
        ans = Math.max(ans, s + e[1]);
      } else {
        ans = Math.max(ans, s + e[0]);
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} transactions * @return {number} */ var minimumMoney =
  function (transactions) {
    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;
  };

```

### CPP

```cpp
class Solution {
public:
  long long minimumMoney(vector<vector<int>> &transactions) {
    long long s = 0, ans = 0;
    for (auto &e : transactions) {
      s += max(0, e[0] - e[1]);
    }
    for (auto &e : transactions) {
      if (e[0] > e[1]) {
        ans = max(ans, s + e[1]);
      } else {
        ans = max(ans, s + e[0]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumMoney(self, transactions: List[List[int]]) -> int: s = sum(max(0, a - b) for a, b in transactions) ans = 0 for a, b in transactions: if a > b: ans = max(ans, s + b) else: ans = max(ans, s + a) return ans

```