You are given an integer array transactions, where transactions[i] represents the amount of the ith transaction:
The account starts with a balance of 0, and the balance must never become negative. Transactions must be considered in the given order, but you are allowed to skip some transactions.
Return an integer denoting the maximum number of transactions that can be performed without the balance ever going negative.
Example 1:
Input: transactions = [2,-5,3,-1,-2]
Output: 4
Explanation:
One optimal sequence is [2, 3, -1, -2], balance: 0 → 2 → 5 → 4 → 2.
Example 2:
Input: transactions = [-1,-2,-3]
Output: 0
Explanation:
All transactions are negative. Including any would make the balance negative.
Example 3:
Input: transactions = [3,-2,3,-2,1,-1]
Output: 6
Explanation:
All transactions can be taken in order, balance: 0 → 3 → 1 → 4 → 2 → 3 → 2.
Constraints:
1 <= transactions.length <= 105-109 <= transactions[i] <= 109Problem Overview: You are given a list of transactions that either add to or subtract from your balance. You can choose which transactions to execute, but the running balance must never drop below zero. The goal is to perform the maximum number of transactions while maintaining a non‑negative balance at every step.
Approach 1: Brute Force Subset Exploration (Exponential Time)
The most direct idea is to try every subset of transactions and check whether executing them in order keeps the balance non‑negative. For each subset, iterate through the chosen transactions, maintain a running balance, and discard the subset if the balance ever drops below zero. Track the largest valid subset size. This approach explores 2^n possibilities and performs an O(n) validation for each subset, giving O(n * 2^n) time and O(n) space for recursion. It quickly becomes infeasible once the input size grows, but it clarifies the constraint that the prefix sum must always stay ≥ 0.
Approach 2: Greedy + Heap / Ordered Set (O(n log n))
A greedy strategy works because negative transactions are the only ones that risk breaking the balance constraint. Iterate through the array and maintain a running balance. Every transaction is tentatively accepted. When the transaction value is negative, store it in a max structure (such as a max‑heap or ordered set) so you can quickly remove the most damaging one later.
If the running balance becomes negative, remove the transaction with the largest negative impact from the chosen set. This is done by extracting the smallest value (largest loss) from the heap and adding it back to the balance. Removing the worst transaction restores the balance while minimizing the number of removals. Continue processing the rest of the transactions.
This works because keeping smaller losses instead of larger ones maximizes how many transactions you can afford overall. Each transaction is processed once, and heap operations cost O(log n). The total complexity is O(n log n) time and O(n) space. The approach combines ideas from Greedy decision making with a Heap (Priority Queue) to efficiently track the worst negative transaction.
Since the input is simply processed sequentially, the algorithm also naturally fits problems modeled with Array traversal and prefix balance tracking.
Recommended for interviews: The Greedy + Heap solution is what interviewers expect. Brute force demonstrates understanding of the prefix constraint but does not scale. Recognizing that you only need to discard the worst negative transaction when the balance breaks shows strong algorithmic intuition and leads to the optimal O(n log n) implementation.
We use an ordered set (such as C++'s multiset, Java's TreeMap, Python's SortedList) to store the selected transaction amounts, and maintain a variable s to record the current balance. Initially s=0, and the answer ans is initialized to the number of transactions.
Then we traverse each transaction amount x:
x to the balance s and add x to the ordered set.s becomes negative at this point, it means some negative amounts among the currently selected transaction amounts have caused insufficient balance. To retain as many transactions as possible, we should remove the smallest amount among the currently selected transaction amounts (because removing the smallest amount can maximize the balance). We remove the smallest amount y from the ordered set, subtract y from the balance s, and decrement the answer ans by 1.s is no longer negative.After traversal is complete, the answer ans is the maximum number of transactions that can be performed.
The time complexity is O(n times log n), where n is the number of transactions. The space complexity is O(n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Exploration | O(n * 2^n) | O(n) | Useful only for understanding the constraint or verifying small inputs |
| Greedy + Heap (Priority Queue) | O(n log n) | O(n) | General optimal solution; efficiently removes the worst negative transaction when balance becomes negative |
| Greedy + Ordered Set | O(n log n) | O(n) | Alternative implementation when language libraries provide ordered sets or balanced BST structures |
leetcode 3711 Practice of Heap - Maximum Transactions Without Negative Balance | heap • Code-Yao • 62 views views
Practice Maximum Transactions Without Negative Balance with our built-in code editor and test cases.
Practice on FleetCode