Constraints

• 0 <= len(payments) <= 100000
• 0 <= len(refund_allocations) <= 100000
• paymentId values are unique positive integers
• amount and refundedAmount are non-negative integers
• Every refund allocation references an existing payment and total allocations per payment do not exceed its amount

Examples

Solution

def solution(payments, refund_allocations):
    payments_by_id = {}
    remaining = {}
    payments_by_user = {}

    for payment in payments:
        payment_id, user_id, amount, timestamp = payment
        payments_by_id[payment_id] = [payment_id, user_id, amount, timestamp]
        remaining[payment_id] = amount
        payments_by_user.setdefault(user_id, []).append((timestamp, payment_id))

    for allocation in refund_allocations:
        payment_id, refunded_amount = allocation
        remaining[payment_id] -= refunded_amount

    section_payments = [payments_by_id[payment_id] for payment_id in sorted(payments_by_id)]
    section_remaining = [[payment_id, remaining[payment_id]] for payment_id in sorted(remaining)]

    section_users = []
    for user_id in sorted(payments_by_user):
        ordered_ids = [payment_id for timestamp, payment_id in sorted(payments_by_user[user_id])]
        section_users.append([user_id] + ordered_ids)

    return [section_payments, section_remaining, section_users]

Time complexity: O(P log P + R + P log P) overall, dominated by sorting payment IDs and per-user payment lists; P is number of payments and R is number of refund allocations.. Space complexity: O(P) for the payment map, remaining map, and per-user index..

Hints

1. A hash map keyed by paymentId gives direct access to original and remaining payment data.
2. For the per-user view, group payment IDs by userId and sort each group by timestamp.

Constraints

• 0 <= len(operations) <= 100000
• IDs, amounts, and timestamps are integers
• paymentId and refundId values are positive integers
• Refund amounts are non-negative
• A rejected operation must not change ledger state

Examples

Solution

def solution(operations):
    payments = {}
    remaining = {}
    balances = {}
    refund_ids = set()
    results = []

    for op in operations:
        kind = op[0]

        if kind == 1:
            _, payment_id, user_id, amount, timestamp = op
            if payment_id in payments:
                results.append(0)
            else:
                payments[payment_id] = (user_id, amount, timestamp)
                remaining[payment_id] = amount
                balances[user_id] = balances.get(user_id, 0) + amount
                results.append(1)

        elif kind == 2:
            _, refund_id, user_id, amount, timestamp, payment_ref = op
            if refund_id in refund_ids:
                results.append(0)
            elif payment_ref not in payments:
                results.append(0)
            elif payments[payment_ref][0] != user_id:
                results.append(0)
            elif amount > remaining[payment_ref]:
                results.append(0)
            else:
                refund_ids.add(refund_id)
                remaining[payment_ref] -= amount
                balances[user_id] = balances.get(user_id, 0) - amount
                results.append(1)

        else:
            _, user_id = op
            results.append(balances.get(user_id, 0))

    return results

Time complexity: O(N) total for N operations, with O(1) average time per operation using hash maps.. Space complexity: O(P + R + U), where P is accepted payments, R is accepted refund IDs tracked, and U is users with balances..

Hints

1. Keep one map from paymentId to its user and another map from paymentId to remaining refundable amount.
2. Maintaining a cached balance per user makes getUserBalance constant time.

Constraints

• 0 <= len(payments) <= 100000
• 0 <= refund amount <= 10^12
• paymentId values are unique positive integers
• remainingAmount values are non-negative integers
• If no rules are provided, default to OLDEST_FIRST then ID_ASC

Examples

Solution

def solution(payments, refund, rules):
    refund_user, refund_amount, refund_timestamp = refund

    eligible = []
    total_available = 0
    for payment in payments:
        payment_id, user_id, remaining_amount, timestamp = payment
        if user_id == refund_user and remaining_amount > 0 and timestamp <= refund_timestamp:
            eligible.append(payment)
            total_available += remaining_amount

    if refund_amount == 0:
        return []
    if total_available < refund_amount:
        return []

    effective_rules = list(rules) if rules else ['OLDEST_FIRST', 'ID_ASC']
    if 'ID_ASC' not in effective_rules and 'ID_DESC' not in effective_rules:
        effective_rules.append('ID_ASC')

    def sort_key(payment):
        payment_id, user_id, remaining_amount, timestamp = payment
        key = []
        for rule in effective_rules:
            if rule == 'RECENT_FIRST':
                key.append(-timestamp)
            elif rule == 'OLDEST_FIRST':
                key.append(timestamp)
            elif rule == 'LARGEST_REMAINING_FIRST':
                key.append(-remaining_amount)
            elif rule == 'SMALLEST_REMAINING_FIRST':
                key.append(remaining_amount)
            elif rule == 'ID_ASC':
                key.append(payment_id)
            elif rule == 'ID_DESC':
                key.append(-payment_id)
        return tuple(key)

    eligible.sort(key=sort_key)

    allocations = []
    remaining_refund = refund_amount
    for payment in eligible:
        payment_id, user_id, remaining_amount, timestamp = payment
        take = min(remaining_amount, remaining_refund)
        if take > 0:
            allocations.append([payment_id, take])
            remaining_refund -= take
        if remaining_refund == 0:
            break

    return allocations

Time complexity: O(P log P) in the worst case to sort eligible payments; P is the number of current payments.. Space complexity: O(P) for the eligible payment list..

Hints

1. Convert each priority rule into a component of a sort key.
2. After sorting eligible payments, greedily consume each payment's remaining amount until the refund is covered.

Constraints

• 0 <= len(payment_amounts) <= 100000
• 0 <= len(refund_requests) <= 100000
• paymentId values in payment_amounts are unique positive integers
• Payment and refund amounts are non-negative integers
• Rejected requests must not change remaining refundable amounts

Examples

Solution

def solution(payment_amounts, refund_requests):
    remaining = {}
    for payment_id, amount in payment_amounts:
        remaining[payment_id] = amount

    results = []
    for payment_id, amount in refund_requests:
        if payment_id not in remaining:
            results.append([-1, 0, 0])
        elif amount <= remaining[payment_id]:
            remaining[payment_id] -= amount
            results.append([1, amount, remaining[payment_id]])
        else:
            results.append([0, 0, remaining[payment_id]])

    return results

Time complexity: O(P + R), where P is number of payments and R is number of refund requests.. Space complexity: O(P) for the remaining refundable amount map..

Hints

1. Store only the remaining refundable amount for each payment; you do not need to recompute from history.
2. A refund is valid exactly when requested amount <= remaining[paymentId].

Constraints

• 0 <= len(records) <= 100000
• Payment and refund IDs are positive integers and unique within their own type
• Amounts are positive integers
• An unreferenced refund may use only payments already ingested, with the same userId, timestamp <= refund timestamp, and positive remaining amount
• If rules is empty, default to OLDEST_FIRST then ID_ASC

Examples

Solution

def solution(records, rules):
    payments = {}
    remaining = {}
    refund_outputs = []

    effective_rules = list(rules) if rules else ['OLDEST_FIRST', 'ID_ASC']
    if 'ID_ASC' not in effective_rules and 'ID_DESC' not in effective_rules:
        effective_rules.append('ID_ASC')

    def sort_key(payment):
        payment_id, user_id, remaining_amount, timestamp = payment
        key = []
        for rule in effective_rules:
            if rule == 'RECENT_FIRST':
                key.append(-timestamp)
            elif rule == 'OLDEST_FIRST':
                key.append(timestamp)
            elif rule == 'LARGEST_REMAINING_FIRST':
                key.append(-remaining_amount)
            elif rule == 'SMALLEST_REMAINING_FIRST':
                key.append(remaining_amount)
            elif rule == 'ID_ASC':
                key.append(payment_id)
            elif rule == 'ID_DESC':
                key.append(-payment_id)
        return tuple(key)

    for record in records:
        kind = record[0]

        if kind == 1:
            _, payment_id, user_id, amount, timestamp = record
            if payment_id not in payments:
                payments[payment_id] = (user_id, amount, timestamp)
                remaining[payment_id] = amount

        else:
            _, refund_id, user_id, amount, timestamp, payment_ref = record

            if payment_ref != -1:
                if payment_ref in payments and payments[payment_ref][0] == user_id and payments[payment_ref][2] <= timestamp and remaining[payment_ref] >= amount:
                    remaining[payment_ref] -= amount
                    refund_outputs.append([[payment_ref, amount]])
                else:
                    refund_outputs.append([])
                continue

            candidates = []
            total_available = 0
            for payment_id, payment_data in payments.items():
                payment_user, original_amount, payment_timestamp = payment_data
                rem = remaining[payment_id]
                if payment_user == user_id and rem > 0 and payment_timestamp <= timestamp:
                    candidates.append([payment_id, payment_user, rem, payment_timestamp])
                    total_available += rem

            if total_available < amount:
                refund_outputs.append([])
                continue

            candidates.sort(key=sort_key)
            allocation = []
            left = amount
            for payment in candidates:
                payment_id, payment_user, rem, payment_timestamp = payment
                take = min(rem, left)
                if take > 0:
                    allocation.append([payment_id, take])
                    left -= take
                if left == 0:
                    break

            for payment_id, take in allocation:
                remaining[payment_id] -= take
            refund_outputs.append(allocation)

    return refund_outputs

Time complexity: O(N * P log P) in the worst case if every unreferenced refund scans and sorts all prior payments. With per-user priority indexes this can be improved, but this direct simulator prioritizes clarity.. Space complexity: O(P + A), where P is stored payments and A is the size of the largest temporary allocation/candidate list..

Hints

1. For an unreferenced refund, first collect candidate payments and check that total remaining amount is sufficient before mutating state.
2. Use the same sort-key idea from configurable priority rules, then greedily allocate.

Constraints

• 0 <= len(operations) <= 100000
• userId values are positive integers
• For unreferenced refunds, 0 <= touchedPayments <= current number of payments for that user
• The estimator tracks payment counts only; refunds do not remove payments from the count
• All costs fit in a 64-bit signed integer

Examples

Solution

def solution(operations):
    def ceil_log2_at_least_2(x):
        x = max(2, x)
        return (x - 1).bit_length()

    payment_counts = {}
    total_payments = 0
    naive_cost = 0
    indexed_cost = 0

    for op in operations:
        kind = op[0]

        if kind == 1:
            user_id = op[1]
            before = payment_counts.get(user_id, 0)
            payment_counts[user_id] = before + 1
            total_payments += 1

            naive_cost += 1
            indexed_cost += 1 + ceil_log2_at_least_2(before + 1)

        elif kind == 2:
            user_id, has_reference, touched_payments = op[1], op[2], op[3]
            current_count = payment_counts.get(user_id, 0)

            if has_reference == 1:
                naive_cost += 1
                indexed_cost += 1
            else:
                naive_cost += 1 + current_count
                indexed_cost += 1 + touched_payments * ceil_log2_at_least_2(current_count)

        else:
            naive_cost += 1
            indexed_cost += 1

    if naive_cost < indexed_cost:
        recommendation = -1
    elif indexed_cost < naive_cost:
        recommendation = 1
    else:
        recommendation = 0

    return [naive_cost, indexed_cost, recommendation, total_payments]

Time complexity: O(N) to scan N workload operations. The modeled indexed ledger operations are addPayment O(log m), referenced addRefund O(1), unreferenced addRefund O(k log m), and getUserBalance O(1), where m is the user's payment count and k is touchedPayments.. Space complexity: O(U) for this estimator, where U is the number of users. The modeled ledger designs both require O(P) payment storage..

Hints

1. Maintain the current number of payments per user while scanning operations once.
2. ceil(log2(x)) for integer x >= 1 can be computed with bit_length.