Maximum Transactions Without Negative Balance - Solution & Explanation

Problem 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.