Maximum transactions without negative balance

Array Greedy Heap (Priority Queue)

46.2% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;

impl Solution {
  pub fn max_transactions(transactions: Vec<i32>) -> i32 {
    let mut balance: i64 = 0;
    let mut count = 0i32;
    let mut heap = BinaryHeap::new();
    
    for &t in &transactions {
      if t >= 0 {
        balance += t as i64;
        count += 1;
      } else {
        let abs_t = -(t as i64);
        if balance >= abs_t {
          balance -= abs_t;
          count += 1;
          heap.push(abs_t);
        } else if let Some(&worst) = heap.peek() {
          if worst > abs_t {
            balance += worst;
            balance -= abs_t;
            heap.pop();
            heap.push(abs_t);
          }
        }
      }
    }
    count
  }
}