1169. Invalid Transactions (Sort by lambda + HashTable) 20.4.20 Medium

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.
Each transaction string transactions[i] consists of comma separated values representing the name, time (in minutes), amount, 
and city of the transaction.

Given a list of transactions, 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: ---------------------------------------------------- my own --------- Sort by lambda + HashTable
------------------------------------------------- O(n^2) T, O(n) T
class Solution(object):
    def invalidTransactions(self, transactions):
        """
        :type transactions: List[str]
        :rtype: List[str]
        """
        if not transactions:
            return None
        res = []
        HashTable = collections.defaultdict(list)
        for tran in transactions:
            curr = tran.split(',')
            if int(curr[2]) > 1000:
                res.append(tran)
            HashTable[curr[0]].append(curr)
        for items in HashTable.values():
            items.sort(key = lambda x: int(x[1]))
            print items
            for i in range(len(items)):
                for j in range(i + 1, len(items)):
                '''
                IMPORTANT !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                BUG takes me 30 mins to found !!!!!!!!!!!
                instead of check i and i + 1
                we must use another for loop and check i and j
                '''
                    if int(items[j][1]) - int(items[i][1]) <= 60 and items[i][3] != items[j][3]:                    
                        res.append(",".join(items[i]))       # Instead of checking if the current ",".join(items[i]) is in res everytime
                        res.append(",".join(items[j]))      
        return set(res)                                      # We should just use set() when we return



Java Version:
class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        List<String> res = new ArrayList<>();
        Set<String> contain = new HashSet<>();
        if (transactions == null || transactions.length == 0) {
            return res;
        }
        Map<String, List<String[]>> map = new HashMap<>();
        for (String transaction : transactions) {
            String[] l = transaction.split(",");
            List<String[]> currList;
            if (map.containsKey(l[0])) {
                 currList = map.get(l[0]);
            } else {
                 currList = new ArrayList<>();
            }
            currList.add(l);
            map.put(l[0], currList);
        }
        for (String name : map.keySet()) {
            List<String[]> currList = map.get(name);
            Collections.sort(currList, (o1, o2) -> Integer.valueOf(o1[1]) - Integer.valueOf(o2[1]));
            for (int i = 0; i < currList.size(); i ++) {
                if (Integer.valueOf(currList.get(i)[2]) > 1000 && ! contain.contains(String.join(",", currList.get(i)))) {
                    res.add(String.join(",", currList.get(i)));
                    contain.add(String.join(",", currList.get(i)));
                }
                for (int j = i + 1; j < currList.size(); j ++) {
                    if (Integer.valueOf(currList.get(j)[1]) - Integer.valueOf(currList.get(i)[1]) <= 60 && ! currList.get(i)[3].equals(currList.get(j)[3])) {
                        if (! contain.contains(String.join(",", currList.get(i)))) {
                            res.add(String.join(",", currList.get(i)));
                            contain.add(String.join(",", currList.get(i)));
                        }
                        if (! contain.contains(String.join(",", currList.get(j)))) {
                            res.add(String.join(",", currList.get(j)));
                            contain.add(String.join(",", currList.get(j)));
                        }
                    }
                }
            }
        }
        return res;
    }
}