2412. Min Required Money

Minimum Money Required Before Transactions

The reason this problem is labeled hard, I eventually noticed, is that the key to solving it is actually a reading comprehension test.

"Regardless of the order" of the transactions

We are asked to find the minimum amount of money such that

no matter what order the transactions are executed, money will always be enough for upcoming transactions at each time step.

That is, this amount guarantees we won't be unable to afford the next transaction.

Let's think: in what situation is it most likely that

after a transaction, our remaining money can't cover the next one?

It must be... a streak of losing transactions,

steadily draining initial funds, bit by bit.

The Protection at Absolute Security 🪖

From the above, we must at least withstand total net loss of all losing transactions.

We must collect all transactions where $cashback_i < cost_i$ and sum up their losses: $L = \Sigma_i (cost_i - cashback_i)$.

Nevertheless, we also need to add the maximum cashback $x$ among all losing transactions.

Why? If we execute all losing transactions consecutively from the start,

and the last losing transaction happens to have cashback $x$, the moment of maximum cumulated loss happens right before receiving $x$ back.

But What About Profitable Transactions?

A. If there are no profitable transactions

The minimum safe amount is simply $L + x$ as described above.

B. If there are profitable transactions, be a bit more careful

After losing transactions are done, we are still having profitable ones to handle.

The nature of profitable transactions is that our principal never drops after each one.

So now we only need to consider one thing:

after tortured by losing transactions, do we still have enough to cover entry cost of any profitable transaction?

After all, profitable transactions don't fall from the sky: you have to pay cost first before getting cashback.

How to Profit: 🌫️ Endure the Storm, See the Moon 🌕

By now, you've probably guessed we also need

the number $L + y$, where $y$ is the maximum cost among all profitable transactions.

The deeper meaning of such a number is:

in the worst case, all losing transactions occur first, immediately followed by the most expensive profitable transaction.

We'd need to start with $L + y$ to handle everything.

Since subsequent profitable transactions cost no more than $y$,

and profitable transactions, by definition, never reduce our capital,

now it comes down to comparing which is larger: $L + x$ or $L + y$.

The larger one is our final answer.

C++

#include <vector>
using namespace std;

long long calculateMinRequiredMoney(vector<vector<int>>& transactions) { // LeetCode Q.2412.
    long long totalAbsLoss = 0;

    int winningTradeMaxCost = -1;

    int losingTradeMaxCashback = -1;

    for (const auto& transaction : transactions) {
        int cost = transaction[0], cashback = transaction[1];

        if (cashback >= cost) {
            if (cost > winningTradeMaxCost)
                winningTradeMaxCost = cost;
            continue;
        }

        totalAbsLoss += cost - cashback;

        if (cashback > losingTradeMaxCashback)
            losingTradeMaxCashback = cashback;
    }

    long long minRequiredMoney = totalAbsLoss + losingTradeMaxCashback;

    if (winningTradeMaxCost == -1)
        return minRequiredMoney;

    if (minRequiredMoney < winningTradeMaxCost + totalAbsLoss)
        minRequiredMoney = winningTradeMaxCost + totalAbsLoss;

    return minRequiredMoney;
}

Python

def calculate_min_required_money(transactions: list[list[int]]) -> int:  # LeetCode Q.2412.
    total_abs_loss = 0

    losing_trade_max_cashback = -1
    winning_trade_max_cost = -1

    for cost, cashback in transactions:
        if cashback >= cost:
            if cost > winning_trade_max_cost:
                winning_trade_max_cost = cost
            continue

        abs_loss = cost - cashback
        total_abs_loss += abs_loss
        
        if cashback > losing_trade_max_cashback:
            losing_trade_max_cashback = cashback
    
    min_required_money = total_abs_loss + losing_trade_max_cashback
    
    if winning_trade_max_cost == -1: return min_required_money

    if min_required_money < winning_trade_max_cost + total_abs_loss:
        min_required_money = winning_trade_max_cost + total_abs_loss

    return min_required_money

Time complexity: $O(n)$, Space complexity: $O(1)$

Literally, this problem's core is understanding the phrase "Regardless of the order".