Constraints

• 1 <= len(commands) <= 50000
• Keys and values are single tokens with no spaces
• Transaction nesting can be arbitrarily deep within the command count limit
• All commands are valid and use one of: SET, GET, BEGIN, ROLLBACK, COMMIT

Examples

Solution

def solution(commands):
    current = {}
    transactions = []
    output = []

    for command in commands:
        parts = command.split()
        op = parts[0]

        if op == "SET":
            key, value = parts[1], parts[2]
            if transactions:
                log = transactions[-1]
                if key not in log:
                    if key in current:
                        log[key] = (True, current[key])
                    else:
                        log[key] = (False, None)
            current[key] = value

        elif op == "GET":
            key = parts[1]
            output.append(current.get(key, "NULL"))

        elif op == "BEGIN":
            transactions.append({})

        elif op == "ROLLBACK":
            if not transactions:
                output.append("NO TRANSACTION")
            else:
                log = transactions.pop()
                for key, (had_value, old_value) in log.items():
                    if had_value:
                        current[key] = old_value
                    else:
                        current.pop(key, None)

        elif op == "COMMIT":
            if not transactions:
                output.append("NO TRANSACTION")
            else:
                transactions.clear()

    return output

Time complexity: SET, GET, BEGIN, and COMMIT are O(1) average time. ROLLBACK is O(k), where k is the number of distinct keys changed in the most recent transaction.. Space complexity: O(U + C), where U is the number of currently visible keys and C is the number of distinct key changes recorded across all open transactions..

Hints

1. Keep one dictionary for the currently visible values so GET can be answered in O(1) average time.
2. For each transaction, record a key's old value only the first time that key is changed inside that transaction.