3711. Maximum Transactions Without Negative Balance 🔒

Description

You are given an integer array transactions, where transactions[i] represents the amount of the ith transaction:

• A positive value means money is received.
• A negative value means money is sent.

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] <= 109

Solutions

Solution 1: Greedy + Ordered Set

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 \(\textit{ans}\) is initialized to the number of transactions.

Then we traverse each transaction amount \(x\):

1. Add \(x\) to the balance \(s\) and add \(x\) to the ordered set.
2. If the balance \(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 \(\textit{ans}\) by \(1\).
3. Repeat step 2 until the balance \(s\) is no longer negative.

After traversal is complete, the answer \(\textit{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)\).

Python3JavaC++Go

class Solution:
    def maxTransactions(self, transactions: List[int]) -> int:
        st = SortedList()
        s = 0
        ans = len(transactions)
        for x in transactions:
            s += x
            st.add(x)
            while s < 0:
                y = st.pop(0)
                s -= y
                ans -= 1
        return ans

class Solution {
    public int maxTransactions(int[] transactions) {
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        int ans = transactions.length;
        long s = 0;
        for (int x : transactions) {
            s += x;
            tm.merge(x, 1, Integer::sum);
            while (s < 0) {
                int y = tm.firstKey();
                s -= y;
                --ans;
                if (tm.merge(y, -1, Integer::sum) == 0) {
                    tm.remove(y);
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int maxTransactions(vector<int>& transactions) {
        multiset<int> st;
        int ans = transactions.size();
        long long s = 0;
        for (int x : transactions) {
            s += x;
            st.insert(x);
            while (s < 0) {
                auto it = st.begin();
                int y = *it;
                st.erase(it);
                s -= y;
                --ans;
            }
        }
        return ans;
    }
};

func maxTransactions(transactions []int) int {
    tm := redblacktree.New[int, int]()
    ans := len(transactions)
    var s int64

    for _, x := range transactions {
        s += int64(x)
        if cnt, ok := tm.Get(x); ok {
            tm.Put(x, cnt+1)
        } else {
            tm.Put(x, 1)
        }

        for s < 0 {
            it := tm.Iterator()
            it.Begin()
            it.Next()
            y := it.Key()
            s -= int64(y)
            ans--

            cnt, _ := tm.Get(y)
            if cnt == 1 {
                tm.Remove(y)
            } else {
                tm.Put(y, cnt-1)
            }
        }
    }
    return ans
}

Comments