Scale Engineer

Minimum Money Required Before Transactions

Hard
#2196Time: 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.
Patterns
Greedy
Algorithms
Sorting
Data structures
Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;        }    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem