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 ofmoney required before any transaction so that all of the transactions can be completedregardless of the order of the transactions.

Examples

Example 1

1
2
3
4

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

1
2
3
4
5
6

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 <= 10^5
  • transactions[i].length == 2
  • 0 <= costi, cashbacki <= 10^9

Solution

Method 1 – Greedy Split by Cost and Cashback

Intuition

Transactions where cost > cashback are risky, as they always reduce your money. To guarantee all orders work, you must have enough money to cover the worst-case order: do all risky transactions first, then the rest. The minimum required is the sum of all risky costs minus their cashback, plus the maximum cost among all transactions.

Approach

  1. Split transactions into risky (cost > cashback) and safe (cost <= cashback).
  2. For risky transactions, sum up (cost - cashback) for each.
  3. Track the maximum cost among all transactions.
  4. The answer is the sum from step 2 plus the maximum cost among all transactions.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    long long minimumMoney(vector<vector<int>>& transactions) {
        long long risky = 0, ans = 0;
        for (auto& t : transactions) {
            if (t[0] > t[1]) risky += t[0] - t[1];
        }
        for (auto& t : transactions) {
            ans = max(ans, risky + (long long)t[0]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func minimumMoney(transactions [][]int) int64 {
    var risky int64
    for _, t := range transactions {
        if t[0] > t[1] {
            risky += int64(t[0] - t[1])
        }
    }
    var ans int64
    for _, t := range transactions {
        if risky+int64(t[0]) > ans {
            ans = risky+int64(t[0])
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public long minimumMoney(int[][] transactions) {
        long risky = 0, ans = 0;
        for (int[] t : transactions) {
            if (t[0] > t[1]) risky += t[0] - t[1];
        }
        for (int[] t : transactions) {
            ans = Math.max(ans, risky + t[0]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun minimumMoney(transactions: Array<IntArray>): Long {
        var risky = 0L
        for (t in transactions) {
            if (t[0] > t[1]) risky += t[0] - t[1]
        }
        var ans = 0L
        for (t in transactions) {
            ans = maxOf(ans, risky + t[0].toLong())
        }
        return ans
    }
}
1
2
3
4
5
6

def minimum_money(transactions: list[list[int]]) -> int:
    risky = 0
    for cost, cashback in transactions:
        if cost > cashback:
            risky += cost - cashback
    return max(risky + cost for cost, cashback in transactions)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn minimum_money(transactions: Vec<Vec<i32>>) -> i64 {
        let mut risky = 0i64;
        for t in &transactions {
            if t[0] > t[1] {
                risky += (t[0] - t[1]) as i64;
            }
        }
        let mut ans = 0i64;
        for t in &transactions {
            ans = ans.max(risky + t[0] as i64);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    minimumMoney(transactions: number[][]): number {
        let risky = 0;
        for (const [cost, cashback] of transactions) {
            if (cost > cashback) risky += cost - cashback;
        }
        let ans = 0;
        for (const [cost] of transactions) {
            ans = Math.max(ans, risky + cost);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of transactions. Each transaction is processed twice.
  • 🧺 Space complexity: O(1), only a few variables are used for tracking the answer.