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.

class Solution(object):
    def invalidTransactions(self, transactions):
        """
        :type transactions: List[str]
        :rtype: List[str]
        """
        d = {}
        for idx,s in enumerate(transactions):
            name,time,amount,city = s.split(',')
            if name not in d: d[name]=[]
            d[name].append((idx, int(time),int(amount),city))
        for name in d:
            d[name].sort(key=lambda s:s[1])
        
        added = set()
        res = []
        for name in d:
            for i in range(len(d[name])):
                flag = False
                idx,t,a,c = d[name][i]
                for j in range(i+1, len(d[name])):
                    idx2,t2,a2,c2 = d[name][j]
                    if t2-t>60: continue
                    if c2!=c:
                        res.append(transactions[idx2])
                        added.add(idx2)
                        flag = True
                if flag or a>1000:
                    res.append(transactions[idx])
                    added.add(idx)
        return list(set(res))