We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Money Required Before Transactions

Number: 2499

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

You are given a 0-indexed 2D integer array transactions, where transactions[i] = [costᵢ, cashbackᵢ]. Every transaction must be performed exactly once in some order. At the time of performing a transaction, you must have at least costᵢ money; after the transaction your money becomes money - costᵢ + cashbackᵢ. Return the minimum amount of money required before any transaction so that no matter how an adversary orders the transactions, you can always complete all the transactions.

Key Insights

  • The “regardless of order” requirement means we have to plan for the worst‐case ordering.
  • In any ordering, there is one transaction that might be “pushed” to a point where all other transactions have already reduced your money.
  • If you simulate the worst order (i.e. one that forces you to pay the highest cost at a time when your money is lowest), you get two natural lower bounds: • You must always have at least max(costᵢ) because a transaction requiring the highest cost might come first. • If an adversary schedules the “helpful” transaction (one that returns more cashback) as late as possible, then before that transaction you would have paid all other transactions’ net “loss” (i.e. cost – cashback). In that situation your money must be at least costᵢ. Rewriting, for some transaction i the condition becomes: initial_money ≥ (total loss from all other transactions) + costᵢ. Algebra shows that, if you pick the transaction with the highest cashback to be last, the requirement is initial_money ≥ (sum over all transactions of (cost – cashback)) + max(cashback).
  • Combining these two observations, the answer is the maximum of max(costᵢ) and [sum(costᵢ – cashbackᵢ) over all transactions + max(cashbackᵢ)].

Space and Time Complexity

Time Complexity: O(n) where n is the number of transactions. Space Complexity: O(1) – only a few variables are maintained.

Solution

We use a greedy insight based on a worst-case analysis. Let total_loss be the sum of costᵢ – cashbackᵢ over all transactions. Notice that if one transaction (particularly the one with the highest cashback) is scheduled last, then before it you must cover the net “loss” of all other transactions. That would require starting money of at least total_loss plus the cashback of that last transaction. Meanwhile, if some transaction requiring a very high cost occurs first, we must have at least max(costᵢ). Therefore, the minimum starting money is:

  answer = max(max(costᵢ), total_loss + max(cashbackᵢ)).

This condition is both necessary (since an adversary could force this situation) and sufficient (because with this money you can complete any permutation).

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java. Each solution includes detailed line‐by‐line comments.

# Function to compute the minimum starting money required
def minimumMoney(transactions):
    # Initialize variables: max_cost stores the maximum cost encountered,
    # total_loss accumulates the net money reduction (cost - cashback) for all transactions,
    # max_cashback tracks the highest cashback value.
    max_cost = 0
    total_loss = 0
    max_cashback = 0
    
    # Process each transaction in the list
    for cost, cashback in transactions:
        # Update the maximum cost seen so far
        if cost > max_cost:
            max_cost = cost
        # Add (cost - cashback) to total_loss (can be negative if cashback > cost)
        total_loss += (cost - cashback)
        # Update the maximum cashback encountered
        if cashback > max_cashback:
            max_cashback = cashback
    
    # The answer is the maximum between:
    # 1. max_cost (to ensure every individual transaction can be afforded if it comes first)
    # 2. total_loss + max_cashback (worst-case when the best cashback transaction comes last)
    return max(max_cost, total_loss + max_cashback)

# Example usage:
print(minimumMoney([[2,1],[5,0],[4,2]]))  # Expected output: 10
print(minimumMoney([[3,0],[0,3]]))          # Expected output: 3
← Back to All Questions