1class Solution {
2    public int maxTransactions(int[] transactions) {
3        // TreeMap to keep track of all accepted transactions,
4        // mapping transaction value -> its occurrence count.
5        // The keys are sorted in ascending order, so the smallest
6        // (most negative) transaction is always at the front.
7        TreeMap<Integer, Integer> countMap = new TreeMap<>();
8
9        // Start by assuming every transaction can be kept.
10        int maxCount = transactions.length;
11
12        // Running sum (balance) of all currently accepted transactions.
13        long runningSum = 0;
14
15        for (int amount : transactions) {
16            // Tentatively accept the current transaction.
17            runningSum += amount;
18            countMap.merge(amount, 1, Integer::sum);
19
20            // If the balance goes negative, greedily discard the
21            // smallest (most negative) transactions until the
22            // balance becomes non-negative again.
23            while (runningSum < 0) {
24                int smallest = countMap.firstKey();
25
26                // Removing the smallest value increases the balance,
27                // since subtracting a negative number adds to the sum.
28                runningSum -= smallest;
29
30                // One fewer transaction is kept.
31                --maxCount;
32
33                // Decrease its count; remove the entry entirely
34                // when no occurrences remain.
35                if (countMap.merge(smallest, -1, Integer::sum) == 0) {
36                    countMap.remove(smallest);
37                }
38            }
39        }
40
41        return maxCount;
42    }
43}
44

1class Solution {
2public:
3    int maxTransactions(vector<int>& transactions) {
4        // Min-heap-like container that keeps all currently accepted transactions sorted.
5        // A multiset is used because duplicate transaction values are allowed.
6        multiset<int> acceptedTransactions;
7
8        // Initially assume that every transaction can be kept.
9        int maxCount = transactions.size();
10
11        // Running sum of all currently accepted transactions.
12        // Use long long to avoid potential integer overflow.
13        long long runningSum = 0;
14
15        // Process transactions one by one in their original order.
16        for (int transaction : transactions) {
17            // Tentatively accept the current transaction.
18            runningSum += transaction;
19            acceptedTransactions.insert(transaction);
20
21            // If the running sum becomes negative, the current selection is invalid.
22            // Greedily remove the smallest (most negative) transaction(s)
23            // until the running sum is non-negative again.
24            while (runningSum < 0) {
25                // The smallest element is at the beginning of the multiset.
26                auto smallestIt = acceptedTransactions.begin();
27                int smallestValue = *smallestIt;
28
29                // Remove it from the selection and update the running sum.
30                acceptedTransactions.erase(smallestIt);
31                runningSum -= smallestValue;
32
33                // One fewer transaction can be kept.
34                --maxCount;
35            }
36        }
37
38        // Return the maximum number of transactions that can be kept
39        // while the running sum never stays negative.
40        return maxCount;
41    }
42};
43

1/**
2 * Inserts a value into the min-heap and restores the heap property
3 * by sifting the newly added value up toward the root.
4 */
5function heapPush(heap: number[], value: number): void {
6    heap.push(value);
7    let childIndex = heap.length - 1;
8
9    while (childIndex > 0) {
10        const parentIndex = (childIndex - 1) >> 1;
11
12        // Stop when the parent is already smaller than or equal to the child.
13        if (heap[parentIndex] <= heap[childIndex]) {
14            break;
15        }
16
17        // Swap child with parent and continue sifting up.
18        [heap[parentIndex], heap[childIndex]] = [heap[childIndex], heap[parentIndex]];
19        childIndex = parentIndex;
20    }
21}
22
23/**
24 * Removes and returns the smallest value (the root) from the min-heap,
25 * then restores the heap property by sifting the relocated value down.
26 */
27function heapPop(heap: number[]): number {
28    const smallestValue = heap[0];
29    const lastValue = heap.pop()!;
30
31    if (heap.length > 0) {
32        // Move the last element to the root and sift it down.
33        heap[0] = lastValue;
34        let parentIndex = 0;
35
36        while (true) {
37            const leftIndex = parentIndex * 2 + 1;
38            const rightIndex = leftIndex + 1;
39            let smallestIndex = parentIndex;
40
41            if (leftIndex < heap.length && heap[leftIndex] < heap[smallestIndex]) {
42                smallestIndex = leftIndex;
43            }
44            if (rightIndex < heap.length && heap[rightIndex] < heap[smallestIndex]) {
45                smallestIndex = rightIndex;
46            }
47
48            // Stop when the parent is smaller than both children.
49            if (smallestIndex === parentIndex) {
50                break;
51            }
52
53            // Swap parent with the smaller child and continue sifting down.
54            [heap[parentIndex], heap[smallestIndex]] = [heap[smallestIndex], heap[parentIndex]];
55            parentIndex = smallestIndex;
56        }
57    }
58
59    return smallestValue;
60}
61
62/**
63 * Returns the maximum number of transactions that can be kept
64 * such that the running sum of the kept transactions never stays negative.
65 */
66function maxTransactions(transactions: number[]): number {
67    // Min-heap that keeps all currently accepted transactions,
68    // with the smallest (most negative) value at the root.
69    const acceptedTransactions: number[] = [];
70
71    // Initially assume that every transaction can be kept.
72    let maxCount = transactions.length;
73
74    // Running sum of all currently accepted transactions.
75    let runningSum = 0;
76
77    // Process transactions one by one in their original order.
78    for (const transaction of transactions) {
79        // Tentatively accept the current transaction.
80        runningSum += transaction;
81        heapPush(acceptedTransactions, transaction);
82
83        // If the running sum becomes negative, the current selection is invalid.
84        // Greedily remove the smallest (most negative) transaction(s)
85        // until the running sum is non-negative again.
86        while (runningSum < 0) {
87            const smallestValue = heapPop(acceptedTransactions);
88
89            // Remove it from the selection and update the running sum.
90            runningSum -= smallestValue;
91
92            // One fewer transaction can be kept.
93            --maxCount;
94        }
95    }
96
97    // Maximum number of transactions that can be retained.
98    return maxCount;
99}
100