LeetCode Solutions Blog

Invalid Transactions

Number: 1272

Difficulty: Medium

Paid? No

Problem Description

Given an array of transactions in the form "name,time,amount,city", a transaction is possibly invalid if its amount exceeds $1000, or if it occurs within (and including) 60 minutes of another transaction with the same name in a different city. The task is to return all transactions that meet the invalid criteria.

Key Insights

Parse each transaction string into its components: name, time, amount, and city.
Immediately mark any transaction as invalid if its amount exceeds 1000.
Group transactions by the same name using a hash table.
For each group, compare transactions pairwise to check if any two with the same name occur within 60 minutes while being in different cities.
Use a set to store the results to avoid duplicates.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case due to pairwise comparisons within each name group. Space Complexity: O(n) for storing parsed transactions and grouping them by name.

Solution

The solution begins by parsing each transaction into its individual parts. A dictionary (or hash map) is used to group transactions by name, which reduces unnecessary comparisons. For each transaction, if the amount is greater than 1000, mark it as invalid. Then, for each pair of transactions with the same name, if the time difference is within 60 minutes and the cities are different, mark the involved transactions as invalid. This covers both conditions of potential invalidity.

Code Solutions

def invalidTransactions(transactions):
    # List to store parsed transactions: (name, time, amount, city, original string)
    parsed = []
    # Group transactions by name for efficient comparisons
    transactions_by_name = {}
    
    # Parse each transaction
    for transaction in transactions:
        name, t_str, amount_str, city = transaction.split(',')
        time = int(t_str)
        amount = int(amount_str)
        parsed.append((name, time, amount, city, transaction))
        if name not in transactions_by_name:
            transactions_by_name[name] = []
        transactions_by_name[name].append((time, amount, city, transaction))
    
    invalid = set()
    
    # Check each group of transactions with the same name
    for name, trans_list in transactions_by_name.items():
        n = len(trans_list)
        for i in range(n):
            time1, amount1, city1, trans_str1 = trans_list[i]
            # Check the amount condition
            if amount1 > 1000:
                invalid.add(trans_str1)
            # Compare with other transactions for the time/city criteria
            for j in range(n):
                if i == j:
                    continue
                time2, _, city2, _ = trans_list[j]
                if abs(time1 - time2) <= 60 and city1 != city2:
                    invalid.add(trans_str1)
                    break  # Once invalid, no need to check further for this transaction
    return list(invalid)

# Example usage:
print(invalidTransactions(["alice,20,800,mtv", "alice,50,100,beijing"]))