{x}
blog image

Invalid Transactions

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.

 

Example 1:

Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output: ["alice,20,800,mtv","alice,50,100,beijing"]
Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.

Example 2:

Input: transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]
Output: ["alice,50,1200,mtv"]

Example 3:

Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]
Output: ["bob,50,1200,mtv"]

 

Constraints:

  • transactions.length <= 1000
  • Each transactions[i] takes the form "{name},{time},{amount},{city}"
  • Each {name} and {city} consist of lowercase English letters, and have lengths between 1 and 10.
  • Each {time} consist of digits, and represent an integer between 0 and 1000.
  • Each {amount} consist of digits, and represent an integer between 0 and 2000.

Solution Explanation: Invalid Transactions

This problem involves identifying invalid transactions based on two criteria: exceeding a transaction amount limit and proximity to another transaction with the same name but a different city. The optimal solution leverages a hash table (dictionary in Python) for efficient lookups.

Approach:

  1. Data Structure: We use a dictionary (d in Python, Map in Java, etc.) to store transactions keyed by the name of the person involved in the transaction. The value associated with each name is a list of tuples (or similar structures). Each tuple contains:

    • time: The transaction time.
    • city: The city where the transaction occurred.
    • index: The index of the transaction in the input array.

  2. Iteration and Checking: We iterate through the transactions array. For each transaction:

    • Amount Check: We check if the transaction amount exceeds 1000. If it does, we mark the transaction's index as invalid.
    • Time and City Check: We look up the current transaction's name in the dictionary. If the name exists, we iterate through the existing transactions for that name. For each existing transaction, we check:
      • If the cities are different.
      • If the time difference is within 60 minutes (inclusive). If both conditions are true, we mark both the current transaction and the existing transaction as invalid.

  3. Result: After processing all transactions, we collect all transactions marked as invalid and return them.

Time and Space Complexity:

  • Time Complexity: The nested loop structure leads to a time complexity of O(n^2) in the worst case, where n is the number of transactions. This is because we potentially compare each transaction with every other transaction with the same name.

  • Space Complexity: The space complexity is O(n) because, in the worst-case scenario, the dictionary could store all transactions.

Code Examples:

Python:

from collections import defaultdict
 
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        d = defaultdict(list)
        invalid = set()
        for i, transaction in enumerate(transactions):
            name, time, amount, city = transaction.split(",")
            time, amount = int(time), int(amount)
            if amount > 1000:
                invalid.add(i)
            d[name].append((time, city, i))
 
        for name, transactions_for_name in d.items():
            for i in range(len(transactions_for_name)):
                for j in range(i+1, len(transactions_for_name)):
                    time1, city1, index1 = transactions_for_name[i]
                    time2, city2, index2 = transactions_for_name[j]
                    if city1 != city2 and abs(time1 - time2) <= 60:
                        invalid.add(index1)
                        invalid.add(index2)
 
        result = [transactions[i] for i in invalid]
        return result

Java: (Uses a similar approach, replacing defaultdict with HashMap and sets with HashSet)

import java.util.*;
class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        Map<String, List<Transaction>> map = new HashMap<>();
        Set<Integer> invalid = new HashSet<>();
 
        for (int i = 0; i < transactions.length; i++) {
            String[] parts = transactions[i].split(",");
            String name = parts[0];
            int time = Integer.parseInt(parts[1]);
            int amount = Integer.parseInt(parts[2]);
            String city = parts[3];
 
            if (amount > 1000) invalid.add(i);
 
            map.computeIfAbsent(name, k -> new ArrayList<>()).add(new Transaction(time, city, i));
        }
 
        for (List<Transaction> transList : map.values()) {
            for (int i = 0; i < transList.size(); i++) {
                for (int j = i + 1; j < transList.size(); j++) {
                    Transaction t1 = transList.get(i);
                    Transaction t2 = transList.get(j);
                    if (!t1.city.equals(t2.city) && Math.abs(t1.time - t2.time) <= 60) {
                        invalid.add(t1.index);
                        invalid.add(t2.index);
                    }
                }
            }
        }
 
        List<String> result = new ArrayList<>();
        for (int index : invalid) {
            result.add(transactions[index]);
        }
        return result;
    }
 
    class Transaction {
        int time;
        String city;
        int index;
 
        Transaction(int time, String city, int index) {
            this.time = time;
            this.city = city;
            this.index = index;
        }
    }
}

Other languages (C++, Javascript, Go, etc.) would follow a very similar structure. Remember to handle potential errors like invalid input formats appropriately in a production setting.