We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Invalid Transactions

Difficulty: Medium

Problem Description

A transaction is possibly invalid if:

  • the amount exceeds $1000, or;
  • if it occurs within (and including) 60 minutes of another transaction with the same name in a different city.

You are given an array of strings transaction where transactions[i] consists of comma-separated values representing the name, time (in minutes), amount, and city of the transaction.

Return a list of transactions that are possibly invalid. You may return the answer in any order.

Key Insights

  • A transaction is invalid if its amount is greater than $1000.
  • A transaction is also invalid if there is another transaction with the same name within 60 minutes in a different city.
  • We need to compare each transaction with others based on the name and city, making it necessary to store transactions in a way that allows easy access and comparison.

Space and Time Complexity

Time Complexity: O(n^2), where n is the number of transactions, since we may need to compare each transaction against all others. Space Complexity: O(n), for storing the transactions and potentially the results.

Solution

To solve the problem, we can use a hash table to store transactions indexed by name. We will iterate through each transaction, checking for two conditions of invalidity:

  1. If the amount exceeds $1000, we add it to the invalid list.
  2. If there's another transaction with the same name within 60 minutes in a different city, we also add it to the invalid list.

By storing transactions in a hash table grouped by name, we can efficiently check for conditions that lead to invalid transactions.

Code Solutions

def invalidTransactions(transactions):
    invalid = set()
    transaction_list = []

    for transaction in transactions:
        name, time, amount, city = transaction.split(',')
        time = int(time)
        amount = int(amount)
        
        # Check if amount exceeds $1000
        if amount > 1000:
            invalid.add(transaction)
        
        transaction_list.append((name, time, amount, city))
    
    # Check for transactions within 60 minutes in different cities
    n = len(transaction_list)
    for i in range(n):
        name1, time1, amount1, city1 = transaction_list[i]
        for j in range(i + 1, n):
            name2, time2, amount2, city2 = transaction_list[j]
            if name1 == name2 and city1 != city2 and abs(time1 - time2) <= 60:
                invalid.add(transactions[i])
                invalid.add(transactions[j])
    
    return list(invalid)
← Back to All Questions