Fewest Expenses to Defer to Year End So the Running Balance Never Goes Negative

A company's transactions for one year are given in chronological order as an array A: a positive value is income and a negative value is an expense. The company starts the year with a balance of 0, and its balance must never be negative at any time. To achieve this, the company may move some expenses to the end of the year: a moved expense is taken out of its place and paid after all the other transactions. Return the minimum number of expenses that must be moved.

Function Signature

def min_expenses_to_move(A: list[int]) -> int:

Rules

• Only expenses (negative values) may be moved. A value of 0 changes nothing and never needs to move.
• Process the transactions that were not moved in their original order, starting from a balance of 0. After each one, the balance must be >= 0; a balance of exactly 0 is allowed.
• The moved expenses are then paid after all other transactions, in any order. The input guarantees sum(A) >= 0, so the balance stays non-negative while they are paid.
• Return the minimum number of moved expenses.

Constraints

• 1 <= len(A) <= 10^5
• -10^9 <= A[i] <= 10^9
• sum(A) >= 0
• Running balances can reach 10^14 in absolute value, beyond the 32-bit integer range; use 64-bit integers in languages with fixed-width integers.

Examples

Example 1

Input: A = [5, -3, -4, 6, -1]
Output: 1

Without moves, the balances are 5, 2, -2, ..., so at least one move is needed. Moving -4 to the end gives balances 5, 2, 8, 7 and then 3 after the moved expense.

Example 2

Input: A = [-2, 3, -1, -5, 4, 2]
Output: 2

The first expense must move, because the balance would start at -2. After that, the balances are 3, 2 and then -3 at the expense -5, so a second move is needed. Moving -2 and -5 gives balances 3, 2, 6, 8, then 6 and 1 after the moved expenses.

Example 3

Input: A = [3, -1, -2, 4]
Output: 0

The balances are 3, 2, 0, 4. A balance of 0 is allowed, so nothing needs to move.