What is the main strategy to solve the Minimum Money Required Before Transactions problem?

The main strategy is using a greedy approach by categorizing transactions based on whether their cashback is greater than or equal to their cost, then tracking the maximum deficit.

How does the greedy approach help in this problem?

The greedy approach ensures that transactions with cashback equal to or greater than their cost are handled first, reducing the initial money required, while tracking deficits from transactions with lower cashback.

What are common mistakes when solving this problem?

Common mistakes include not properly categorizing transactions or failing to track the maximum deficit when cashback is less than the cost.

How do I optimize for the minimum starting money?

By categorizing transactions and calculating the total deficit from the group where cashback is less than the cost, you ensure the minimum required starting money is reached.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of transactions, since we iterate through the list only once.

#2412

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

完成所有交易的初始最少钱数

给你一个下标从 0 开始的二维整数数组 transactions ，其中 transactions[i] = [cost i , cashback i ] 。数组描述了若干笔交易。其中每笔交易必须以某种顺序恰好完成一次。在任意一个时刻，你有一定数目的钱 money ，为了完成交易 i ， mo…

数组贪心排序

题目描述

给你一个下标从 0 开始的二维整数数组 transactions，其中transactions[i] = [cost_i, cashback_i] 。

数组描述了若干笔交易。其中每笔交易必须以 某种顺序 恰好完成一次。在任意一个时刻，你有一定数目的钱 money ，为了完成交易 i ，money >= cost_i 这个条件必须为真。执行交易后，你的钱数 money 变成 money - cost_i + cashback_i。

请你返回 任意一种 交易顺序下，你都能完成所有交易的最少钱数 money 是多少。

示例 1：

输入：transactions = [[2,1],[5,0],[4,2]]
输出：10
解释：
刚开始 money = 10 ，交易可以以任意顺序进行。
可以证明如果 money < 10 ，那么某些交易无法进行。

示例 2：

输入：transactions = [[3,0],[0,3]]
输出：3
解释：
- 如果交易执行的顺序是 [[3,0],[0,3]] ，完成所有交易需要的最少钱数是 3 。
- 如果交易执行的顺序是 [[0,3],[3,0]] ，完成所有交易需要的最少钱数是 0 。
所以，刚开始钱数为 3 ，任意顺序下交易都可以全部完成。

提示：

1 <= transactions.length <= 10⁵
transactions[i].length == 2
0 <= cost_i, cashback_i <= 10⁹

lightbulb

解题思路

方法一：贪心

我们先累计所有负收益，记为 $s$ 。然后枚举每个交易 $\text{transactions}[i] = [a, b]$ 作为最后一个交易，如果 $a > b$ ，说明当前的交易是亏钱的，而这个交易在此前我们累计负收益的时候，已经被计算，因此取 $s + b$ 更新答案；否则，取 $s + a$ 更新答案。

时间复杂度 $O(n)$ ，其中 $n$ 为交易数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	complexity is O(n), where n is the number of transactions, as we iterate through the list once to categorize and calculate the required money. Space complexity is O(1) because we only store a few variables to track the maximum deficit and the total cost of transactions with cashback greater than or equal to the cost.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of greedy algorithms and how to apply them to financial transaction problems.
question_mark
Candidate is able to identify the need for categorizing transactions based on cashback and cost.
question_mark
Candidate can efficiently handle the two categories of transactions and track the maximum deficit to calculate the required money.

warning

常见陷阱

外企场景

error
Not properly categorizing transactions based on cashback vs cost, leading to incorrect results.
error
Failing to track the maximum deficit across transactions where cashback is less than cost.
error
Overcomplicating the problem by trying to consider transaction order beyond the greedy approach.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider how the problem would change if there were different transaction types with additional constraints.
arrow_right_alt
How would the solution change if you were allowed to reorder the transactions yourself before processing?
arrow_right_alt
What if the problem involved adding more types of transaction attributes, such as interest rates or transaction fees?

help

常见问题

外企场景

继续练习

#2410 运动员和训练师的最大匹配数 #2406 将区间分为最少组数 #2389 和有限的最长子序列