BNPL Transaction Settlement

Overview

The goal is to calculate the final bank balances for a set of parties after a series of transactions are processed. We are given their starting balances and a list of transfers where money moves from a sender to a receiver.

The core logic involves:

1. Tracking State: Maintaining a mapping of each unique person to their current net balance.
2. Processing Updates: For every transaction, subtracting the amount from the sender and adding it to the receiver.
3. Ordering: The final output must be ordered alphabetically by the party name, but return only the integer balances.

Brute Force

In a brute force approach, we might treat the input lists literally and perform repetitive searches. For every transaction, we could iterate through the entire list of parties to find the sender and receiver to update their values. However, since we need to handle parties that might appear in transactions but not in initialBalance (and vice versa), we first collect all unique names to build our ledger.

def settle_transactions(transactions: list[list[str]], initialBalance: list[list[str]]) -> list[int]:
    # Collect all unique party names
    parties = set()
    for name, _ in initialBalance:
        parties.add(name)
    for sender, receiver, _ in transactions:
        parties.add(sender)
        parties.add(receiver)
    
    # Sort names to ensure alphabetical order for the final output
    sorted_names = sorted(list(parties))
    # Initialize balances in a list corresponding to sorted_names
    balances = [0] * len(sorted_names)
    
    # Fill initial balances
    for name, amt in initialBalance:
        idx = sorted_names.index(name)
        balances[idx] = int(amt)
        
    # Process transactions by finding indices repeatedly
    for sender, receiver, amt in transactions:
        amount = int(amt)
        s_idx = sorted_names.index(sender)
        r_idx = sorted_names.index(receiver)
        balances[s_idx] -= amount
        balances[r_idx] += amount
        
    return balances

Time complexity: O(N * M) — Where N is the number of unique parties and M is the number of transactions, due to the repeated use of .index() which performs a linear search. Space complexity: O(N) — We store the unique party names and their balances.

Optimal / Best Approach

The optimal approach uses a Hash Map (Dictionary) to achieve O(1) lookups for each party. Instead of searching through a list to find a party's index, we map the name directly to their current balance.

1. Initialize Ledger: Create a dictionary where keys are party names and values are integers. Populated this first with the initialBalance data.
2. Handle New Parties: Ensure that any party mentioned in transactions who wasn't in initialBalance is added to the dictionary with a starting balance of 0.
3. Process Transactions: Iterate through transactions once. For each [sender, receiver, amount], update the dictionary values: ledger[sender] -= amount and ledger[receiver] += amount.
4. Extract and Sort: Extract the keys (names), sort them alphabetically, and build the final list of balances based on that sorted order.

def settle_transactions(transactions: list[list[str]], initialBalance: list[list[str]]) -> list[int]:
    # Use a dictionary for O(1) balance updates
    ledger = {}
    
    # Load initial balances
    for name, balance_str in initialBalance:
        ledger[name] = int(balance_str)
        
    # Process transactions
    for sender, receiver, amount_str in transactions:
        amount = int(amount_str)
        
        # Ensure parties exist in ledger (even if they had no initial balance)
        if sender not in ledger:
            ledger[sender] = 0
        if receiver not in ledger:
            ledger[receiver] = 0
            
        ledger[sender] -= amount
        ledger[receiver] += amount
        
    # Sort the party names alphabetically
    sorted_party_names = sorted(ledger.keys())
    
    # Return balances in the sorted order of names
    return [ledger[name] for name in sorted_party_names]

Time complexity: O(B + T + N log N) — Where B is the size of initialBalance, T is the number of transactions, and N is the number of unique parties (due to sorting). Space complexity: O(N) — We store the balance of each unique party in a hash map.

Edge Cases

• Zero Balance Parties: A party might exist in the initial list but never participate in a transaction. They must still appear in the final output.
• New Parties: A party might not have an initial balance but appears in a transaction. The logic handles this by initializing them to 0.
• Negative Balances: As seen in Example 3, it is possible for a party to spend more than their initial balance, resulting in a negative integer. The problem constraints allow for this.
• Large Integers: The amounts are provided as strings; using Python's int() handles arbitrarily large integers automatically.

Fast