Invalid Transactions LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple BloombergViews 4196

Problem Statement

Invalid Transactions LeetCode Solution – 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.

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.

Explanation

Bruteforce Approach:

The basic idea is to create a set to remove possible duplicates when looking at the two different ($1000 and within 60 minutes in a different city) invalid conditions. Then just brute force it by iteratively comparing every transaction with all the other transactions. This is extremely easy to do, but not optimal.

Optimized Approach:

  1. Create a transaction data structure so the attributes can easily be queried and stored in a transactions array
  2. Sort the transactions array-based on time
  3. Iterate through the transactions array and create a hash table/dictionary with name as the key, and an array of transaction indexes as the value.
  4. Iterate through the dictionary and loop through the name specific transaction indexes array.
    • Over 1000 dollars check: If the current transaction amount is greater than 1000, then add to the res and continue to the next transaction.
    • Within 60 minutes check: Use left, and right pointers to represent the possible neighbor transactions that are within the 60 minutes.
    • If the current transaction has any neighbors within the 60 minutes then check if the city is different. If so, add to the res and continue to the next transactions.

1 We need to sort the transactions by time, so a function convert string to a customized struct is required.
2 To reduce the effort of compare of transactions, we use unordered_map to classify them by name.
3 To generate the result easily, we add the input string and a bool flag to the struct, with other info in the transactions we get the 6-member struct design.
4 To reach better performance, we can do sort only for transactions from the same name.

Code

C++ Code for Invalid Transaction

class Solution {
public:
    struct CustomerDetail{
        string name;
        int time;
        int amount;
        string city;
    };
    CustomerDetail prepareCustomerObject(string s){
        vector<string>temp;
        string t;
        istringstream f(s);
        while(getline(f,t,',')){
            temp.push_back(t);
        }
        CustomerDetail obj =  CustomerDetail();
        obj.name=temp[0];
        obj.time=stoi(temp[1]);
        obj.amount=stoi(temp[2]);
        obj.city=temp[3];
        return obj;
    }
    vector<string> invalidTransactions(vector<string>& transactions) {
        vector<bool> invalid(transactions.size());
        vector<CustomerDetail> details;
        map<string/*name*/,vector<int>/*list of indexes*/> hashmap;
        int i=0;
        for(string s: transactions) {
            CustomerDetail obj = prepareCustomerObject(s);
            invalid[i]=obj.amount>1000;
        
            if(hashmap.find(obj.name) != hashmap.end()) {
                vector<int> indexes = hashmap[obj.name];
                
                for(int ind: indexes) {
                    if(details[ind].city != obj.city && abs(obj.time-details[ind].time)<= 60) {
                        invalid[ind]=true;
                        invalid[i]=true;
                    }
                }
            }
            hashmap[obj.name].push_back(i);
            details.push_back(obj);
            i++;
        }
        vector<string> ans;
        for(i=0;i<transactions.size();i++){
            if(invalid[i])
                ans.push_back(transactions[i]);
        }
        return ans;
    }
};

Java Code for Invalid Transaction

class Solution {
    public List<String> invalidTransactions(final String[] transactions) {
    final List<String> invalid = new ArrayList<>();
    final Map<String, List<Transaction>> map = new HashMap<>();

    /*
     * build a map with name as key and value as list of transactions for that name
     */
    for (final String transaction : transactions) {
      final Transaction tran = new Transaction(transaction);

      if (map.containsKey(tran.name)) {
        map.get(tran.name).add(tran);
      } else {
        final List<Transaction> list = new ArrayList<>();
        list.add(tran);
        map.put(tran.name, list);
      }
    }

    for (final String transaction : transactions) {
      final Transaction tran = new Transaction(transaction);

      if (!isValid(map.get(tran.name), tran)) {
        invalid.add(transaction);
      }

    }

    return invalid;
  }

  public boolean isValid(final List<Transaction> transactions, final Transaction transaction) {

    /* if there is only one transaction and the amount is less than 1000 */
    if (transactions.size() <= 1 && transaction.amount < 1000)
      return true;

    /* check against all other transaction to check it this one is valid */
    for (final Transaction tran : transactions) {
      if (transaction.invalidTransaction(tran.city, tran.time)) {
        return false;
      }
    }
    return true;
  }

  class Transaction {
    String name;
    int time;
    int amount;
    String city;

    Transaction(final String transaction) {
      final String[] t = transaction.split(",");
      this.name = t[0];
      this.time = Integer.parseInt(t[1]);
      this.amount = Integer.parseInt(t[2]);
      this.city = t[3];
    }

    /*
     * the amount exceeds $1000, or;
     * 
     * if it occurs within (and including) 60 minutes of another transaction with
     * the same name in a different city. Each transaction string transactions[i]
     * consists of comma separated values representing the name, time (in minutes),
     * amount, and city of the transaction.
     */
    public boolean invalidTransaction(final String city, final int time) {
      return invalidAmount() || differentCity(city, time);
    }

    private boolean differentCity(final String city, final int time) {
      return !this.city.equals(city) && Math.abs(this.time - time) <= 60;
    }

    private boolean invalidAmount() {
      return this.amount > 1000;
    }
  }
}

Python Code for Invalid Transaction

class Transaction:
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city

from collections import defaultdict
class Solution:
    def invalidTransactions(self, transactions):
        transactions = [Transaction(*transaction.split(',')) for transaction in transactions]
        transactions.sort(key=lambda t: t.time) # O(nlogn) time

        trans_indexes = defaultdict(list)
        for i, t in enumerate(transactions): # O(n) time
            trans_indexes[t.name].append(i)

        res = []
        for name, indexes in trans_indexes.items(): # O(n) time
            left = right = 0
            for i, t_index in enumerate(indexes):
                t = transactions[t_index]
                if (t.amount > 1000):
                    res.append("{},{},{},{}".format(t.name, t.time, t.amount, t.city))
                    continue
                while left <= len(indexes)-2 and transactions[indexes[left]].time < t.time - 60: # O(60) time
                    left += 1
                while right <= len(indexes)-2 and transactions[indexes[right+1]].time <= t.time + 60: # O(60) time
                    right += 1
                for i in range(left,right+1): # O(120) time
                    if transactions[indexes[i]].city != t.city:
                        res.append("{},{},{},{}".format(t.name, t.time, t.amount, t.city))
                        break

        return res

Complexity Analysis for Invalid Transactions LeetCode Solution

Time Complexity

O(NLogN)

Space Complexity

O(1) as we are not using any extra space.

Reference: https://en.wikipedia.org/wiki/Hash_table

Translate »