LeetCode 3711 - Maximum Transactions Without Negative Balance

LeetCode Problem 3711

Difficulty: 🟡 Medium
Topics: Array, Greedy, Heap (Priority Queue)

Solution

Here is a complete, detailed technical solution guide for LeetCode 3711 - Maximum Transactions Without Negative Balance, following your formatting instructions precisely.

Problem Understanding

The problem provides an array transactions of integers representing sequential money movements in an account. Positive values correspond to receiving money, while negative values correspond to sending money. The account starts at a balance of zero, and we are not allowed to let the balance become negative at any point. The goal is to perform as many transactions as possible in order, skipping some if necessary, without violating the non-negative balance constraint.

The input constraints are substantial: the length of transactions can reach up to 100,000 elements, and transaction values can range from -10^9 to 10^9. This indicates that any brute-force solution that attempts all subsets of transactions will be infeasible due to exponential time complexity.

Important edge cases include arrays with only negative transactions, arrays that start with a large negative number, or alternating large negative and positive transactions. The solution must handle large sums safely without integer overflow.

The expected output is a single integer: the maximum number of transactions that can be executed without the balance dropping below zero.

Approaches

Brute Force

The brute-force approach is to consider all subsets of transactions in order, checking for each whether applying the transactions sequentially would maintain a non-negative balance. For each valid sequence, we count the number of transactions included and return the maximum. This guarantees correctness but is computationally infeasible: with n transactions, there are 2^n subsets. Given the constraints (n <= 10^5), this is completely impractical.

Optimal Approach

The key observation is that any positive transaction can always be included, since it increases the balance. The challenge lies with negative transactions: we can only include a negative transaction if the current balance is at least as large as its absolute value.

A greedy strategy emerges: process transactions in order, maintaining a running balance. Whenever we encounter a negative transaction that would make the balance negative, we can consider removing the largest previously included negative transaction to make room. To do this efficiently, we can maintain a min-heap of negative transaction magnitudes we have accepted. If a new negative transaction cannot be applied directly, we check the heap: if the new negative is smaller than the largest negative we included so far, we replace it. This ensures we maximize the number of transactions by minimizing the impact on the balance.

This approach leverages a priority queue (min-heap) and a running sum for efficient greedy selection.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Check all subsets of transactions for valid sequences
Optimal	O(n log n)	O(n)	Greedy with min-heap to track included negative transactions

Algorithm Walkthrough

1. Initialize balance = 0, count = 0, and a min-heap negatives = [] to track the included negative transactions.

2. Iterate through each transaction t in transactions.

3. If t is positive, simply add it to balance and increment count.

4. If t is negative:

5. If balance + t >= 0, include it: add t to balance, push -t into negatives (store as positive for easy heap comparison), and increment count.

6. Else, check if there is a previously included larger negative transaction (max_neg = heapq.nlargest(1, negatives) or maintain a max-heap using negative values). If such exists and -t < max_neg, replace it: remove the largest negative from heap, adjust balance accordingly, add current negative instead.

7. Continue this process until all transactions are processed.

Why it works:

The algorithm maintains the invariant that balance never drops below zero. By greedily replacing larger negative transactions with smaller ones, we ensure that every transaction included minimally impacts the balance, allowing the maximum number of transactions.

Python Solution

from typing import List
import heapq

class Solution:
    def maxTransactions(self, transactions: List[int]) -> int:
        balance = 0
        count = 0
        # Min-heap to store the negative transactions we have included (as positive values)
        heap = []

        for t in transactions:
            if t >= 0:
                balance += t
                count += 1
            else:
                if balance + t >= 0:
                    balance += t
                    heapq.heappush(heap, -t)  # store absolute value
                    count += 1
                elif heap and -heap[0] > -t:
                    # Replace the largest negative with this smaller negative
                    removed = -heapq.heappop(heap)
                    balance += removed  # undo previous large negative
                    balance += t  # apply current smaller negative
                    heapq.heappush(heap, -t)
        return count

Explanation:

The code iterates through each transaction, applying positive transactions immediately. For negative transactions, it uses a min-heap to track the absolute values of negative transactions we have included. If a new negative transaction cannot be applied due to insufficient balance, we check if replacing a previously included larger negative transaction allows inclusion, maintaining the greedy property.

Go Solution

package main

import (
    "container/heap"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // max-heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func maxTransactions(transactions []int) int {
    balance := 0
    count := 0
    h := &IntHeap{}
    heap.Init(h)

    for _, t := range transactions {
        if t >= 0 {
            balance += t
            count++
        } else {
            if balance+t >= 0 {
                balance += t
                heap.Push(h, -t)
                count++
            } else if h.Len() > 0 && (*h)[0] > -t {
                removed := heap.Pop(h).(int)
                balance += removed // undo previous large negative
                balance += t       // apply current smaller negative
                heap.Push(h, -t)
            }
        }
    }
    return count
}

Explanation:

Go uses a custom IntHeap as a max-heap to track negative transactions (stored as positive values). The rest of the logic mirrors the Python solution, adjusting for Go syntax and type safety. Using container/heap ensures efficient O(log n) operations.

Worked Examples

Example 1: transactions = [2, -5, 3, -1, -2]

Step	Transaction	Balance	Heap	Count
1	2	2	[]	1
2	-5	2-5=-3	[]	1 (skip, negative)
3	3	5	[]	2
4	-1	4	[1]	3
5	-2	2	[1,2]	4

Output: 4

Example 2: transactions = [-1, -2, -3]

All are negative, cannot apply any without going below zero.

Output: 0

Example 3: transactions = [3, -2, 3, -2, 1, -1]

Step	Transaction	Balance	Heap	Count
1	3	3	[]	1
2	-2	1	[2]	2
3	3	4	[2]	3
4	-2	2	[2,2]	4
5	1	3	[2,2]	5
6	-1	2	[2,2,1]	6

Output: 6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each transaction is processed once, heap operations for negative transactions take O(log n)
Space	O(n)	Heap may contain all negative transactions in worst case

The heap ensures we efficiently maintain the largest negative transaction seen so far for potential replacement, which is the main factor in the O(log n) term.

Test Cases

# Provided examples
assert Solution().maxTransactions([2,-5,3,-1