Quick Overview

Given a year's transactions in order, with income as positive values, expenses as negative values and a non-negative total, find the fewest expenses to move to the end of the year so the running balance never drops below zero. It tests reasoning over prefix sums for inputs of up to 100,000 transactions.

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

Company: DRW

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

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 ```python 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** ```text 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** ```text 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** ```text 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.

Overview: Given a year's transactions in order, with income as positive values, expenses as negative values and a non-negative total, find the fewest expenses to move to the end of the year so the running balance never drops below zero. It tests reasoning over prefix sums for inputs of up to 100,000 transactions.

Read the full DRW Software Engineer interview experience this question came from

A company's transactions for one year are given in chronological order as an integer 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. 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 as an integer. Running balances can reach `10^14` in absolute value, which exceeds the 32-bit signed integer maximum `2^31 - 1`. Use 64-bit integers for the elements and the balance (`long` in Java, `long long` in C++). The returned count is at most `len(A)`, so it fits in a 32-bit `int`. Example 1: Input: A = [5, -3, -4, 6, -1] Output: 1 Explanation: 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 Explanation: 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. 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.

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

Input: ([5, -3, -4, 6, -1],)

Expected Output: 1

Explanation: Source Example 1: balances 5, 2, -2 force one move; moving -4 gives 5, 2, 8, 7.

Input: ([-2, 3, -1, -5, 4, 2],)

Expected Output: 2

Explanation: Source Example 2: the leading -2 must move, then -5 drives the balance to -3 and must be moved too; 2 moves.

Hints

  1. Moving an expense only raises the balances that come after its original position, so the moments that matter are those where the running balance would drop below 0.
  2. When that happens, any expense processed so far that has not been moved is a candidate, not only the current one.
  3. Balances can reach 10^14 in absolute value, beyond the 32-bit range: choose the accumulator type accordingly.

Loading coding console...

Show the approach

Approach

Greedy scan with a min-heap. Keep a running balance of the transactions not moved so far and a min-heap of the expenses currently kept in place. For each value x, add it to the balance and, if x < 0, push it onto the heap. If the balance is now negative, pop the most negative kept expense (the largest in magnitude, possibly x itself), add its magnitude back to the balance, and count one move. The balance was >= 0 before x and the popped expense is at least as large in magnitude as x, so a single pop always restores a non-negative balance, and the heap is never empty when popped.

Invariant: after the first i values, the move count is the minimum number of moves that keeps every balance over those i values non-negative, and among all valid choices with that many moves the greedy's balance is the largest possible. Induction step: if adding x keeps the greedy balance >= 0, both properties carry over. If it goes negative, no choice with the old count works: one that moves x has too few moves for the earlier prefix, and one that keeps x has a balance no higher than the greedy's, which is now negative. So one more move is required, and with exactly one more move the highest balance comes from additionally moving the largest kept expense, which is what the greedy pops. Moving an expense only raises the balances after its original position, so it never breaks an earlier prefix. The moved expenses are paid at the end, and sum(A) >= 0 keeps the balance non-negative while paying them, so only the in-order phase constrains the answer.

Edge cases: zeros never move; a singleton (necessarily non-negative) returns 0; a balance of exactly 0 is allowed; a leading expense is always moved. Balances can reach 10^14 in absolute value, so Java uses long and C++ uses long long; the result is at most len(A) and fits in int.

Time complexity:
O(n log n)
Space complexity:
O(n)