NeetCode #547LC-3711MediumHeap / Priority Queue
← Back to All Problems#547 · #3711 · Maximum Transactions Without Negative Balance(最大交易次数(无负余额))
📌 Problem Statement & Constraints
You are given an array
transactions of costs and an initial balance. You may process the transactions in any order, but the running balance must never become negative. Return the maximum number of transactions that can be processed. Constraints: 1 <= transactions.length <= 10^5, 1 <= transactions[i] <= 10^9, 0 <= balance <= 10^9.💡 Core Algorithmic Approaches
- Greedily process the cheapest transactions first, which maximises the count for a given budget.
- If the next cheapest transaction does not fit, try a swap: if the most expensive transaction already processed is larger, replace it.
- A max-heap of the processed costs makes the swap O(log n).
- The swap never decreases the count and frees budget, so the greedy is optimal.
💻 Benchmark Python3 Implementation
class Solution:
def maxTransactions(self, transactions: List[int], balance: int) -> int:
import heapq
h = [] # max-heap of processed costs
for cost in sorted(transactions): # cheapest first
if cost <= balance:
balance -= cost
heapq.heappush(h, -cost)
elif h and -h[0] > cost:
# swap out the most expensive processed transaction
balance += -heapq.heapreplace(h, -cost) - cost
return len(h)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort plus O(n) heap operations.
💾 Space Complexity
O(n) for the heap.
⚠️ Interview Pitfalls & Follow-ups
- Not sorting: the cheapest-first order is what makes the greedy work.
- Skipping a transaction that does not fit without trying a swap: the swap can admit a cheaper transaction while dropping a costlier one.
- Using a min-heap for the processed costs: the swap targets the largest processed cost.
- Updating the balance incorrectly on the swap: the change is
(removed - added).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.