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.

Difficulty: interview

Starter code:

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        

Solutions:
class Transaction:
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city
        
    def array(self):
        return f\"{self.name},{self.time},{self.amount},{self.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 <= t_index 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(t.array())
                        break

        return res


class Transaction:
    
    def __init__(self, s):
        params = s.split(',')
        
        self.name, self.time, self.amount, self.city = params[0], int(params[1]), int(params[2]), params[3]
        
    def __str__(self):
        return ','.join([self.name, str(self.time), str(self.amount), self.city])
    
    

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        #sort transactions by the time, least to great
        transactions = [Transaction(t) for t in transactions]
        
        transactions.sort(key = lambda t: t.time)
        
        #map name to list of idx that use that anem
        trans_idxs = defaultdict(list)
        
        for i, t in enumerate(transactions):
            trans_idxs[t.name].append(i)
            
        invalid = []
        
        #for each name, loop over the  associated transactions 
        # keep pointers left and right that start at 0
        # for each transation move left pointer while trans[idxs[left]].time < t.time - 60
        # do same for right
        for name, idxs in list(trans_idxs.items()):
            left = right = 0
            
            for trans_idx in idxs:
                t = transactions[trans_idx]
                if t.amount > 1000:
                    invalid.append(str(t))
                    continue
                
                while left <= len(idxs) - 2 and transactions[idxs[left]].time < t.time - 60:
                    left += 1
                    
                # right = left
                while right <= len(idxs) - 2 and transactions[idxs[right+1]].time < t.time + 60:
                    right += 1
                
                for j in range(left, right+1):
                    if transactions[idxs[j]].city != t.city:
                        invalid.append(str(t))
                        break
                        
        return invalid
                    
                


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        record, res = collections.defaultdict(list), set()
        for trans in transactions:
            name, time, amount, city = trans.split(',')
            amount, time = int(amount), int(time)
            if amount > 1000:
                res.add(trans)
            if name in record:
                i, j = bisect.bisect_left(record[name], (time-60, '', 0)), bisect.bisect_right(record[name], (time+61, '', 0))
                valid = True
                for item in record[name][i:j]:
                    if item[1] != city:
                        valid = False
                        res.add(','.join([name, str(item[0]), str(item[2]), item[1]]))
                if not valid:
                    res.add(trans)
            bisect.insort(record[name], (time, city, amount))
        return list(res)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        track = [] # (time, city, name)
        ret = set()
        
        for t in transactions:
            name, time, amt, city = t.split(\",\")
            time = int(time)
            if int(amt) > 1000:
                ret.add(t)
                track.append((time, city, name, t))
                # continue
            
            # i = len(track) - 1
            # while i >= 0:
            # print(track, t)
            for i in range(0, len(track)):
                cmp = track[i]
                # if cmp[0] >= max(time - 60, 0) and cmp[1] != city and cmp[2] == name:
                # print(track, t, cmp[3])
                if abs(cmp[0] - time) <= 60 and cmp[1] != city and cmp[2] == name:
                    ret.add(t)
                    ret.add(cmp[3])
                    # break
                # i -= 1
            
            track.append((time, city, name, t))
        return ret

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid_idxes = set()
        dct = {}
        tracs = []
        for idx, trc in enumerate(transactions):
            name, time, amount, location = trc.split(\",\")
            time = int(time)
            amount = int(amount)
            tracs.append((name, time, location, idx, amount))
        # print(sorted(tracs))
            
        for name, time, location, idx, amount in tracs:
            # if name == 'lee' and time == 152:
            #     print(name, time, location, idx, amount )
            #     print(dct['lee'])
            if amount > 1000:
                invalid_idxes.add(idx)
                # continue
            for prev_name, prev_time, prev_location, prev_idx, _ in tracs:
                # prev_idx, prev_time, prev_location = dct[name]
                if prev_name == name and abs(time - prev_time) <= 60 and prev_location != location:
                    invalid_idxes.add(idx)
                    invalid_idxes.add(prev_idx)
            # dct[name] = (idx, time, location)
            
        return [transactions[idx] for idx in invalid_idxes]
            

import collections

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        def parse(S):
            fields = S.split(',')
            return [fields[0],int(fields[1]),int(fields[2]),fields[3]]
        
        hashMap = defaultdict(list)
        for S in transactions:
            fields = parse(S)
            hashMap[fields[0]].append(fields[1:])
            
        invalid = set([])
        for key in hashMap:
            vals = hashMap[key]
            
                
                
            for i,val1 in enumerate(vals):
                if val1[1] >= 1000:
                    invalid = invalid.union(set([','.join([key,str(val1[0]),str(val1[1]),val1[2]])]))
                if len(vals) <= 1:
                    continue
                for j,val2 in enumerate(vals[i+1:]):
                    if abs(val1[0] - val2[0]) <= 60 and val1[2] != val2[2]:
                        invalid = invalid.union(set([','.join([key,str(val1[0]),str(val1[1]),val1[2]])]))
                        invalid = invalid.union(set([','.join([key,str(val2[0]),str(val2[1]),val2[2]])]))
            
        return list(invalid)
            


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        temp=[]       
        for t in transactions:
            temp.append(t.split(','))
        temp=sorted(temp, key=lambda x: x[0])  
        
        res=set()
        for i in range(len(temp)):
            if int(temp[i][2])>1000:
                res.add(','.join(temp[i]))
            for j in range(i+1, len(temp)):
                if temp[i][0]==temp[j][0] and temp[i][3]!=temp[j][3] and abs(int(temp[i][1])-int(temp[j][1]))<=60:
                            res.add(','.join(temp[i]))
                            res.add(','.join(temp[j]))
                
                
        return res
            


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        temp=[]       
        for t in transactions:
            temp.append(t.split(','))
            
        res=set()
        for i in range(len(temp)):
            if int(temp[i][2])>1000:
                res.add(','.join(temp[i]))
            for j in range(i+1, len(temp)):
                if temp[i][0]==temp[j][0] and temp[i][3]!=temp[j][3]:
                    if abs(int(temp[i][1])-int(temp[j][1]))<=60:
                            res.add(','.join(temp[i]))
                            res.add(','.join(temp[j]))
        return res
            


from collections import defaultdict


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        out_idx = set()
        q = []
        bkt_max = -inf

        for idx, transaction in enumerate(transactions):
            name, time, amount, city = transaction.split(',')
            time = int(time)
            amount = int(amount)
            
            if amount > 1000:
                out_idx.add(idx)
                
            bkt_max = max(bkt_max, time + 30)
            
            q.append((max(time - 30, 0), time + 30, name, city, idx))
        
        bkt = [None] * (bkt_max + 1)
        for time_lower_bound, time_upper_bound, name, city, idx in q:
            for i in range(time_lower_bound, time_upper_bound + 1):
                if bkt[i] is None:
                    bkt[i] = defaultdict(lambda: defaultdict(lambda: set()))
                # if i == 676 - 60:
                #     print(i, time_lower_bound, time_upper_bound, name, city, idx)
                bkt[i][name][city].add(idx)
                                
        for b in bkt:
            if b is not None:
                for k, v in list(b.items()):
                    if len(v) > 1:
                        for v1 in list(v.values()):
                            out_idx.update(v1)
        
        out = []
        for idx in out_idx:
            out.append(transactions[idx])
        
        return out


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        LIMIT_AMOUNT = 1000
        LIMIT_TIME = 60
        
        invalid_list = set()
        t_parsed = [x.split(\",\") for x in transactions]
        
        for t in t_parsed:
            t[1] = int(t[1])
            t[2] = int(t[2])
        
        for i in range(len(t_parsed)):
            exceeding = t_parsed[i][2] > LIMIT_AMOUNT
            if exceeding:
                invalid_list.add(i)
                
            for j in range(i+1, len(t_parsed)):
                if i != j and \\
                        abs(t_parsed[i][1]-t_parsed[j][1]) <= LIMIT_TIME and \\
                        t_parsed[i][0] == t_parsed[j][0] and \\
                        t_parsed[i][3] != t_parsed[j][3]:
                    invalid_list.add(i)
                    invalid_list.add(j)
                    
        return [transactions[x] for x in invalid_list]
            

class Solution:
    from heapq import heappush, heappop
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:
            return []
        
        memo = collections.defaultdict(list)    #create a dictionary to keep track of previous transaction 
        invalid_tran = set()                    #to store invalid transaction / I use set to avoid duplication
        for i in range(len(transactions)):
            
            name, time, amount, city = (int(i) if i.isnumeric() else i for i in transactions[i].split(','))
            
            if amount > 1000:                   #if the amount is greater than 1000 add it to the invalid_tran
                invalid_tran.add(transactions[i])               
                 
            if name in memo:                    # if there is any other previous transaction done by similar person , check it from the memo
                for tran in memo[name]:         # bring all previous transaction done by similar person (iterate over the memo)
                    _, prev_time, _, prev_city =(int(i) if i.isnumeric() else i for i in  tran.split(','))
                    if abs(time-prev_time) <= 60 and prev_city != city:  #check if the absolute time difference is less than 60 and the city is the same
                        invalid_tran.add(tran) 
                        invalid_tran.add(transactions[i])                    
            
            memo[name].append(transactions[i])  # add the transaction to the dictionary (memo) - always keep track of previous transaction 
        return invalid_tran

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        parsed_ts = []
        invalid_ts = set()
        for t in transactions:
            t_list = t.split(',')
            # print(t_list)
            t_dict={}
            t_dict['str'] = t
            t_dict['name'] = t_list[0]
            t_dict['time'] = int(t_list[1])
            t_dict['amount'] = int(t_list[2])
            t_dict['city'] = t_list[3]
            
            if t_dict['amount']>1000:
                invalid_ts.add(t)
            for t2 in parsed_ts:
                if abs(t_dict['time']-t2['time'])<=60 and t_dict['city']!=t2['city'] and t_dict['name']==t2['name']:
                    invalid_ts.add(t_dict['str'])
                    invalid_ts.add(t2['str'])
            parsed_ts.append(t_dict)
        
        return list(invalid_ts)


class Transaction: 
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city
        
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        # convert each into object Transaction 
        for i in range(len(transactions)): 
            transact = transactions[i].split(',')
            transactions[i] = Transaction(transact[0], transact[1], transact[2], transact[3])
    
        invalid = set()
        transactions.sort(key=lambda t: t.time)
        
        for i, t in enumerate(transactions): 
            if t.amount > 1000: 
                invalid.add(self.toString(t))
            for j in range(i+1, len(transactions)):
                s = transactions[j]
                if t.name == s.name and t.city != s.city and s.time - t.time <= 60:
                    invalid.add(self.toString(s))
                    invalid.add(self.toString(t))
        return invalid
                
                
    def toString(self, s):
        return ('%s,%d,%d,%s' % (s.name, s.time, s.amount, s.city))
        
        


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        watch_set = set([])
        prev_user = {}
        # Loop once through transactions
        for idx, trans in enumerate(transactions):
            name, time, amt, city = trans.split(\",\")
            time = int(time)
            amt = int(amt)
            if amt > 1000:
                watch_set.add(idx)
            if name in prev_user:
                for p_idx, p_time, p_city in prev_user[name]:
                    if abs(p_time - time) <= 60 and p_city != city:
                        watch_set.add(idx)
                        watch_set.add(p_idx)
                prev_user[name].append((idx, time, city))
            else:
                prev_user[name] = [(idx, time, city)]
        return [transactions[idx] for idx in watch_set]

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ts = []
        for t in transactions:
            name, stamp, amount, city = t.split(\",\")
            ts.append([name, int(stamp), int(amount), city, t])
        
        s = set()
        
        for t in ts:
            if t[2] > 1000: s.add(t[4])
            for v in ts:
                if t[0] == v[0] and abs(t[1] - v[1]) <= 60 and t[3] != v[3]: s.add(v[4])
    
        return list(s)
                
                     
           
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        n=len(transactions)

        invalid=[]
        hashtime={}
        hashcity={}
        hashindex={}
        
        for i in range(n):
            t=transactions[i].split(',')
            n=t[0]
            ti=int(t[1])
            a=int(t[2])
            c=t[3]

            if hashtime.get(n) is None:
                hashtime[n]=[ti]
                hashcity[n]=[c]
                hashindex[n]=[i]
                
            else:
                for h in range(len(hashindex[n])):
                    li=hashtime[n][h]
                    lc=hashcity[n][h]
                    in1=hashindex[n][h]
                    if abs(li-ti)<=60 and not lc == c:
                        if transactions[in1] not in invalid:
                            invalid.append(transactions[in1])
                        if transactions[i] not in invalid:
                            invalid.append(transactions[i])
                        
                    
            if a>1000:
                if transactions[i] not in invalid:
                    invalid.append(transactions[i])
            
            hashtime[n].append(ti)
            hashcity[n].append(c)
            hashindex[n].append(i)

                            
            # print(invalid, t)

        return invalid
                
            
        
        


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        temp=[]       
        for t in transactions:
            temp.append(t.split(','))
            
        res=set()
        for i in range(len(temp)):
            if int(temp[i][2])>1000:
                res.add(','.join(temp[i]))
            for j in range(i+1, len(temp)):
                if temp[i][0]==temp[j][0] and temp[i][3]!=temp[j][3] and abs(int(temp[i][1])-int(temp[j][1]))<=60:
                            res.add(','.join(temp[i]))
                            res.add(','.join(temp[j]))
                
        return res
            


class Solution:
    def combineString(self,lis):
        ans=\"\"
        for i in range(len(lis)):
            ans=ans+lis[i]
        return ans
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ftran=[]
        findex=set()
        name=[]
        time=[]
        amt=[]
        city=[]
        for i in range(len(transactions)):
            a,b,c,d=transactions[i].split(\",\")
            name.append(self.combineString(a))
            e=int(self.combineString(b))
            time.append(e)
            amt.append(self.combineString(c))
            city.append(self.combineString(d))
        for i in range(len(transactions)):
            s=self.combineString(amt[i])
            t=int(s)
            if t>1000:
                findex.add(i)
        for i in range(len(name)):
            for j in range(len(name)):
                if i==j:
                    continue
                if name[i]==name[j] and abs(time[i]-time[j])<=60 and city[i]!=city[j]:
                    findex.add(i)
                    findex.add(j)
        findexl=list(findex)
        for i in range(len(findexl)):
            ftran.append(transactions[findexl[i]])
        return ftran
                    
            
            
                
            
        
    


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        def formated(ob):
            return ob['name']+\",\"+str(ob['time'])+\",\"+str(ob['amount'])+\",\"+ob['city']
        l=[]
        res=[]
        for i in range(len(transactions)):
            store=dict()
            n,t,amount,city = transactions[i].split(\",\")
            store['name']=n
            store['time']=int(t)
            store['amount']=int(amount)
            store['city']=city
            l.append(store)

        sortedList= sorted(l, key = lambda i: i['time'])
        
        for i in range(len(sortedList)):
            for j in range(len(sortedList)):
                if i==j:
                    continue
                    
                elif sortedList[i]['name']==sortedList[j]['name'] and abs(sortedList[i]['time'] - sortedList[j]['time'])<=60 and sortedList[i]['city']!=sortedList[j]['city']:
                    res.append(formated(sortedList[i]))
                    break

                elif sortedList[i]['amount']>1000:
                    res.append(formated(sortedList[i]))
                    break
                    
                elif sortedList[j]['time'] - sortedList[i]['time']>60:
                    break
                    
        return res
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        dic = defaultdict(list)
        res = []
        def helper(s):
            sl = s.split(\",\")
            name = sl[0]
            time = sl[1]
            amount = sl[2]
            city = sl[3]
            return name,time,amount,city
        
        for i in transactions:
            name,time,amount,city = helper(i)
            
            if int(amount) > 1000:
                res.append(i)
                
            for j in dic[name]:
                if abs(int(j[0])-int(time))<=60 and j[2] != city:
                    if name+','+\",\".join(j) not in res:
                        res.append(name+','+\",\".join(j))
                    if i not in res:
                        res.append(i)
                
            dic[name].append([time,amount,city])
            
        return res

class Solution:
    
    def invalidTransactions(self, transactions):
        if not transactions: return []
        n = len(transactions)
        splits = [trans.split(',') for trans in transactions]
        valid = [True] * n

        for i in range(n):   #   rule 1
            if int(splits[i][2]) > 1000:
                valid[i] = False

        for i in range(n):       #   rule 2
            for j in range(i+1, n):                
                if valid[i] or valid[j]:
                    name1, time1, city1 = splits[i][0], int(splits[i][1]), splits[i][3]
                    name2, time2, city2 = splits[j][0], int(splits[j][1]), splits[j][3]
                    if name1 == name2 and city1 != city2 and abs(time1-time2)<=60:
                        valid[i], valid[j] = False, False

        return [transactions[i] for i in range(n) if not valid[i]]
    
#     def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
# #         def asPerTime(string):
# #             return string.split(',')[1]
            
        
# #         transactions.sort(key=asPerTime)
        
#         #dictionary
#         personDict = dict()
        
#         #outputList
#         outSet = set()
        
#         for transaction in transactions:
#             name, time, amount, city = transaction.split(',')
#             if int(amount) > 1000:
#                 outSet.add(transaction)
                
#             if name in personDict:
#                 cityDict = personDict[name]
#                 cityDict[city].append((time, amount))
                
#                 for key in cityDict:
#                     if key != city:
#                         for pair in cityDict[key]:
#                             prevTime, prevAmount = pair
#                             timeDiff = abs(int(time) - int(prevTime)) 
#                             if timeDiff <= 60:
#                                 outSet.add(transaction)
#                                 outSet.add(','.join([name, prevTime, prevAmount, key]))
            
            
#             else:
#                 personDict[name] = defaultdict(list)
#                 personDict[name][city].append((time, amount)) 
        
        
#         return outSet
        
        
        '''
        sort the transaction list as per the time
        
        a dictionary where key is the name of the person and the the value is a dictionary where the key is the city and the value is time and amount        
        
        
        
        iterate over the transactions:
            if the amount is greater than 1000:
                add it to the list
            
            if that same person has done a transaction before
                are the cities different:
                    get the time of the latest transaction
                    if difference is <60:
                        add the latest transaction as well as this transaction
                        update the latest transaction with this transaction info
                        continue
                        
                 
        '''
        
        


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        hash_table={}
        invalid=[]
        index=-1
        lindex=[]
        for trans in transactions:
            count_coma=0
            word=''
            name=''
            dl=[]
            index+=1
            lenght=0
            ind=0
            for l in trans:
                lenght+=1
                if l==',' or lenght==len(trans):
                    count_coma+=1
                    if count_coma==1:
                        name=word
                    elif count_coma==2:
                        tl=[int(word)]
                        dl.append(tl)
                    elif count_coma==3:
                        if int(word)>1000:
                            ind=1
                    else:
                        cl=[word]
                        dl.append(cl)
                        dl.append([index])
                        if name not in hash_table:
                            hash_table[name]=dl
                            if ind==1:
                                invalid.append(trans)
                                lindex.append(index)
                        else:
                            if ind==1:
                                invalid.append(trans)
                                lindex.append(index)
                            for i in range(0,len(hash_table.get(name)[0])):
                                if abs(hash_table.get(name)[0][i]-dl[0][0])<61 and hash_table.get(name)[1][i]!=dl[1][0]:
                                    if index not in lindex:
                                        invalid.append(trans)
                                        lindex.append(index)
                                    if hash_table.get(name)[2][i] not in lindex:
                                        invalid.append(transactions[hash_table.get(name)[2][i]])
                                        lindex.append(hash_table.get(name)[2][i])
                            hash_table.get(name)[0].append(dl[0][0])
                            hash_table.get(name)[1].append(dl[1][0])
                            hash_table.get(name)[2].append(index)
                    word=''
                else:
                    word+=l
        return invalid


class Transaction:
    
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city
        
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
            
        tr = [Transaction(*t.split(',')) for t in transactions]
        transactions = sorted(tr, key=lambda x : x.time)
        
        invalid = set()
        for t in transactions:
            if t.amount > 1000:
                invalid.add(\"{},{},{},{}\".format(t.name, t.time, t.amount, t.city))
            for o in transactions:
                if t.name == o.name and abs(t.time - o.time) <= 60 and t.city != o.city:
                    invalid.add(\"{},{},{},{}\".format(t.name, t.time, t.amount, t.city))
                    invalid.add(\"{},{},{},{}\".format(o.name, o.time, o.amount, o.city))
        return list(invalid)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transactions_by_name = {}
        suspicious_transactions = set()
        for transaction in transactions:
            name, time, amount, city = transaction.split(',')
            if name not in transactions_by_name:
                transactions_by_name[name] = [[name, time, amount, city]]
            else:
                transactions_by_name[name].append([name, time, amount, city])
        for key in transactions_by_name.keys():
            for transaction in transactions_by_name[key]:
                for other_transaction in transactions_by_name[key]:
                    if int(transaction[2]) >= 1000 and ','.join(transaction) not in suspicious_transactions:
                        # over 1k
                        suspicious_transactions.add(','.join(transaction))
                        continue
                    if transaction == other_transaction:
                        continue
                    time_diff = abs(int(transaction[1]) - int(other_transaction[1]))
                    print(time_diff)
                    if time_diff <= 60 and transaction[3] != other_transaction[3]:
                        suspicious_transactions.add(','.join(transaction))
        return list(suspicious_transactions)

class Solution(object):
    def invalidTransactions(self, transactions):
        NAME, TIME, AMOUNT, CITY = list(range(4))
        
        txrows = []
        for row in transactions:
            name, time, amount, city = row.split(',')
            time = int(time)
            amount = int(amount)
            txrows.append((name, time, amount, city))
        
        ans = []
        for i, tx1 in enumerate(txrows):
            if tx1[AMOUNT] >= 1000:
                ans.append(transactions[i])
                continue
            for j, tx2 in enumerate(txrows):
                if (i != j and abs(tx1[TIME] - tx2[TIME]) <= 60 and
                        tx1[NAME] == tx2[NAME] and tx1[CITY] != tx2[CITY]):
                    ans.append(transactions[i])
                    break
        
        return ans


from collections import defaultdict
class Transaction:
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city
    
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = []
        trans_index = defaultdict(list)
        trans = []
        for t in transactions:
            name, time, amount, city = t.split(',')
            trans.append(Transaction(name, time, amount, city))
        trans.sort(key = lambda x: x.time)
        
        s = set()
        for i in range(len(trans)):
            t1 = trans[i]
            if t1.amount > 1000:
                s.add(\"{},{},{},{}\".format(t1.name, t1.time, t1.amount, t1.city))
            for j in range(i + 1, len(trans)):
                t2 = trans[j]
                if t2.time - t2.time > 60:
                    break
                if t2.name == t1.name and t2.time - t1.time <= 60 and t1.city != t2.city:
                    s.add(\"{},{},{},{}\".format(t1.name, t1.time, t1.amount, t1.city))
                    s.add(\"{},{},{},{}\".format(t2.name, t2.time, t2.amount, t2.city))
        return list(s)
            
        
            
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        mapping = {}
        result = []
        for trans in transactions:
            info = trans.split(\",\")  
            if int(info[2]) > 1000:
                result.append(trans)
            if info[0] not in mapping:
                mapping[info[0]] = [info[1:]]
            else:
                
                for mapTransaction in mapping[info[0]]:
                    if (mapTransaction[2] != info[3]) and (abs(int(mapTransaction[0]) - int(info[1])) <= 60):
                        trans1 = ','.join([info[0]] + mapTransaction[:])
                        if trans1 not in result:
                            result.append(trans1)
                        if trans not in result:
                            result.append(trans)        
                mapping[info[0]].append(info[1:])
            
        return result
            

                

        
                    
            
                
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        temp = []
        for transaction in transactions:
            name, time, amount, city = transaction.split(\",\")
            temp.append([name, int(time), int(amount), city, transaction])
        
        ans = set()
        for transaction1 in temp:
            if transaction1[2] > 1000:
                ans.add(transaction1[4])
            for transaction2 in temp:
                if transaction1[0] == transaction2[0] and abs(transaction1[1] - transaction2[1]) <= 60 and transaction1[3] != transaction2[3]:
                    ans.add(transaction2[4])
        return list(ans)
                
                     
           
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ts = []
        for t in transactions:
            name, stamp, amount, city = t.split(\",\")
            ts.append([name, int(stamp), int(amount), city, t])
        
        s = set()
        
        for t in ts:
            if t[2] > 1000: s.add(t[4])
            for v in ts:
                if t[0] == v[0] and abs(t[1] - v[1]) <= 60 and t[3] != v[3]: s.add(v[4])
    
        return list(s)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ts = []
        for t in transactions:
            name, stamp, amount, city = t.split(\",\")
            ts.append([name, int(stamp), int(amount), city, t])
        
        s = set()
        
        for t in ts:
            if t[2] > 1000: s.add(t[4])
            for v in ts:
                if t[0] == v[0] and abs(t[1] - v[1]) <= 60 and t[3] != v[3]: s.add(v[4])
    
        return list(s)
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        poss = []
        people = {}
        for t in transactions:
            items = t.split(\",\")
            if int(items[2]) > 1000:
                poss.append(t)
           
            if items[0] in people:
                for a,b, c in people[items[0]]:
                    if abs(a - int(items[1])) <= 60 and items[3] != b:
                        if t not in poss: 
                            poss.append(t)
                        if c not in poss: 
                            poss.append(c) 
                people[items[0]].append((int(items[1]), items[3], t))
            else:
                people[items[0]] = [(int(items[1]), items[3], t)]
        return poss

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        dic = {}
        result = []
        for i, s in enumerate(transactions):
            [n,m,a,c] = s.split(\",\")
            if int(a)>1000:
                result.append(s)
            if n not in dic:
                dic[n] = [[m,c,i]]
            else:
                dic[n].append([m,c,i])
                for ml, cl, ii in dic[n]:
                    if cl!=c:
                        if abs(int(ml)-int(m))<=60:
                            if s not in result: result.append(s)
                            if transactions[ii] not in result: result.append(transactions[ii])
            # print(dic)
        return result

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        trans_map, suspect = {}, []
        
        for trans in transactions:
            name, time, amount, city = trans.split(\",\")
            
            if name not in trans_map.keys():
                trans_map[name] = [(int(time), int(amount), city, trans)]
            else:
                for prev in trans_map[name]:
                    oth_time, oth_amount, oth_city, oth_trans = prev
                
                    if city != oth_city and abs(int(time) - oth_time) <= 60:
                        if trans not in suspect:
                            suspect.append(trans)
                        
                        if oth_trans not in suspect:
                            suspect.append(oth_trans)
                        
                trans_map[name].append((int(time), int(amount), city, trans))
                    
            if int(amount) > 1000:
                if trans not in suspect:
                    suspect.append(trans)
                
        
        return suspect
            
            
                
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        def parseTransaction(t):
            vals = t.split(',')
            return vals[0], int(vals[1]), int(vals[2]), vals[3]

        
        invalid = set()
        names = {}
        for t in transactions:
            name, time, amt, city = parseTransaction(t)
            if amt > 1000:
                invalid.add(t)
            
            if name in names:
                for (other_t, other_time, other_city) in names[name]:
                    if other_city != city and abs(other_time - time) <= 60:
                        invalid.add(other_t)
                        invalid.add(t)
            else:
                names[name] = []

            names[name].append((t, time, city))
        
        return list(invalid)


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        seen={}
        final=[]
        
        for i in transactions:
            j=i.split(',')
            
            name=j[0]
            time=int(j[1])
            amount=int(j[2])
            city=j[3]
            
            if name not in seen:
                seen[name]=[[name,time,amount,city,i]]
            else:
                seen[name].append([name,time,amount,city,i])
        
        
        for key in list(seen.keys()):
            keys_by_time={}
            # print(key,len(seen[key]))
            # print(seen[key])
            for i in range(len(seen[key])):
                # print(seen[key][i][1])
                keys_by_time[seen[key][i][1]]=i
            seen[key].append(keys_by_time)
            # print(seen[key])
    
        
        for key in list(seen.keys()):
            
            for i in range(len(seen[key])-1):
                
                for j in range(i+1,len(seen[key])-1):
                    
                    current=seen[key][i]
                    nex=seen[key][j]
                    
                    # print(\"current \",current[1],\"nex \",nex[1])
                    if current[3] != nex[3] and abs(current[1]-nex[1]) <= 60:
                        # print(\"condition1\")
                        if current[4] not in final:
                            final.append(current[4])
                        if nex[4] not in final:
                            final.append(nex[4])
                        
                    
                if seen[key][i][4] not in final and seen[key][i][2] >1000:
                    # print(\"condition2\")
                    final.append(seen[key][i][4])
        return final
                



class dsu:
    def __init__(self, n):
        self.parent = [x for x in range(n)]
        self.rank = [0 for x in range(n)]
        self.valid = [True for x in range(n)]
        self.n = n
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, s, t):
        sp, tp = self.find(s), self.find(t)
        if sp == tp:
            return
        if self.rank[sp] < self.rank[tp]:
            self.parent[sp] = tp
        elif self.rank[sp] > self.rank[tp]:
            self.parent[tp] = sp
        else:
            self.parent[tp] = sp
            self.rank[sp] += 1
            
    def cluster(self):
        for x in range(self.n):
            self.find(x)



class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        arrlen = len(transactions)
        net = dsu(arrlen)
        tplist = [t.split(',') for t in transactions]
        for i in range(arrlen):
            tp = tplist[i]
            name, time, amt, city = tp[0], tp[1], tp[2], tp[3]
            if int(amt) > 1000:
                net.valid[i] = False
            for j in range(i + 1, arrlen):
                jtp = tplist[j]
                jname, jtime, jamt, jcity = jtp[0], jtp[1], jtp[2], jtp[3]
                if jname == name and jcity != city and abs(int(jtime) - int(time)) <= 60:
                    net.union(i, j)
        net.cluster()
        for i in range(arrlen):
            if net.parent[i] != i or net.rank[i] != 0:
                net.valid[i] = False
        return [transactions[i] for i in range(arrlen) if not net.valid[i]]


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid=[]
        for i in range(len(transactions)):
            name1,time1,amount1,city1=transactions[i].split(\",\")
            if int(amount1)> 1000:
                invalid.append(transactions[i])
                #continue
                
            for j in range(i+1,len(transactions)):
                name2,time2,amount2,city2=transactions[j].split(\",\")
                if name1 == name2 and abs(int(time1)-int(time2)) <= 60 and city1!=city2:
                            invalid.append(transactions[i])
                            invalid.append(transactions[j])
        return list(set(invalid))
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid=[]
        for i in range(len(transactions)):
            name1,time1,amount1,city1=transactions[i].split(\",\")
            if int(amount1)> 1000:
                invalid.append(transactions[i])
            for j in range(i+1,len(transactions)):
                name2,time2,amount2,city2=transactions[j].split(\",\")
                if name1 == name2 and abs(int(time1)-int(time2)) <= 60 and city1!=city2:
                            invalid.append(transactions[i])
                            invalid.append(transactions[j])
        return list(set(invalid))

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid=set()
        for i in range(len(transactions)):
            name1,time1,amount1,city1=transactions[i].split(\",\")
            if int(amount1)> 1000:
                invalid.add(transactions[i])
            for j in range(i+1,len(transactions)):
                name2,time2,amount2,city2=transactions[j].split(\",\")
                if name1 == name2 and abs(int(time1)-int(time2)) <= 60 and city1!=city2:
                            invalid.add(transactions[i])
                            invalid.add(transactions[j])
        return list(invalid)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        res = []
        
        for i in range(len(transactions)):
            action = transactions[i].split(',')
            person = action[0]
            time = action[1]
            amt = action[2]
            city = action[3]
            if int(amt) > 1000:
                res.append(transactions[i])
                
            for j in range(i+1, len(transactions)):
                act2 = transactions[j].split(',')
                if act2[0] == person and abs(int(act2[1]) - int(time)) <= 60 and city != act2[3]:
                    res.extend([transactions[i], transactions[j]])
        return list(set(res))

class Solution:
    def invalidTransactions(self, transactions):
        transactions = [t.split(',') for t in transactions]
        t = defaultdict(list)
        res = set()
        for x in transactions:
            t[x[0]].append([int(x[1]), int(x[2]), x[3]])
            
        # print(t)
        
        for name in t:
            t[name].sort(key = lambda x: x[0])
            
            for i in range(len(t[name])):
                
                time1, amount1, city1 = t[name][i]
                if amount1 > 1000:
                    res.add(','.join([name, str(time1), str(amount1), city1]))
                    
                for j in range(i+1, len(t[name])):
                    time2, amount2, city2 = t[name][j]
                    if amount2 > 1000:
                        res.add(','.join([name, str(time2), str(amount2), city2]))
                    if city1 == city2:
                        continue
                    if time2 - time1 <= 60:   
                        res.add(','.join([name, str(time1), str(amount1), city1]))
                        res.add(','.join([name, str(time2), str(amount2), city2]))
                    else:  
                        break 
            
        # print(t)
        return res


class Solution:
     def invalidTransactions(self, transactions):
        \"\"\"
        :type transactions: List[str]
        :rtype: List[str]
        \"\"\"
        invalid=[]
        for i in range(len(transactions)):
            name1,time1,amount1,city1=transactions[i].split(\",\")
            if int(amount1)> 1000:
                invalid.append(transactions[i])
                #continue
                
            for j in range(i+1,len(transactions)):
                name2,time2,amount2,city2=transactions[j].split(\",\")
                if name1 == name2 and abs(int(time1)-int(time2)) <= 60 and city1!=city2:
                            invalid.append(transactions[i])
                            invalid.append(transactions[j])
        return list(set(invalid))

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid=[]
        for i in range(len(transactions)):
            name1,time1,amount1,city1=transactions[i].split(\",\")
            if int(amount1)> 1000:
                invalid.append(transactions[i])
                #continue
                
            for j in range(i+1,len(transactions)):
                name2,time2,amount2,city2=transactions[j].split(\",\")
                if name1 == name2 and abs(int(time1)-int(time2)) <= 60 and city1!=city2:
                            invalid.append(transactions[i])
                            invalid.append(transactions[j])
        return list(set(invalid))

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        res = []
        records = []
        
        for t in transactions:
            rec = t.split(',')
            rec[1] = int(rec[1])
            rec[2] = int(rec[2])
            records.append(rec)
        for rec in records:
            if rec[2] > 1000:
                rec[1] = str(rec[1])
                rec[2] = str(rec[2])
                res.append(','.join(rec))
                continue
            for x in records:
                if rec[0] == x[0] and abs(rec[1] - int(x[1])) <=60 and rec[3] != x[3]:
                    rec[1] = str(rec[1])
                    rec[2] = str(rec[2])
                    res.append(','.join(rec))
                    break
        return res

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        t = [x.split(',') for x in transactions]
        t.sort(key = lambda x: int(x[1]))
        invalid = set()
        
        for r in range(len(t)):
            
            if int(t[r][2]) > 1000:
                
                invalid.add(\",\".join(t[r]))
                
            for c in range(r+1, len(t)):
                
                if (int(t[c][1]) - int(t[r][1])) <= 60 and t[c][3] != t[r][3] and t[c][0] == t[r][0]:
                    
                    invalid.add(\",\".join(t[r]))
                    invalid.add(\",\".join(t[c]))
                    
        return(invalid)
                
                
                
                
            
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        s = set()
        for i in range(0,len(transactions)):
            name,time,amount,city = transactions[i].split(\",\")
            if int(amount) > 1000:
                s.add(transactions[i])
            for j in range(i+1,len(transactions)):
                name1,time1,amount1,city1 = transactions[j].split(\",\")
        
                if name == name1 and abs(int(time)-int(time1))<=60 and city!=city1:
                
                    s.add(transactions[i])
                    s.add(transactions[j])
        return s
                

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        if not transactions:
            return []
        
        res = set()
        n = len(transactions)
        #transactions.sort()
       
        for i in range(n):
            n1, t1, a1, d1 = transactions[i].split(',')
            if int(a1) > 1000:
                res.add(transactions[i])
            for j in range(i+1, n):
                n0, t0, a0, d0 = transactions[j].split(',')
                if n0 == n1 and d1 != d0 and abs(int(t1)-int(t0)) <= 60:
                    res.add(transactions[i])
                    res.add(transactions[j])
        
        ans = []
        for t in res:
            ans.append(t)
        print(res, ans)
        return ans

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalidTct = []
        for i in range(len(transactions)):
            name1, time1, amount1, location1 = transactions[i].split(',')
            if int(amount1) > 1000:
                invalidTct.append(transactions[i])
            for j in range(i + 1, len(transactions)):
                name2, time2, amount2, location2 = transactions[j].split(',')
                if name1 == name2 and abs(int(time1) - int(time2)) <= 60 and location1 != location2:
                    invalidTct.append(transactions[i])
                    invalidTct.append(transactions[j])
        return list(set(invalidTct))

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        invalidSet = set()
        for i, transaction in enumerate(transactions):
            name1, time1, amount1, city1 = transaction.split(',')
            if int(amount1) > 1000:
                invalidSet.add(transaction)
            for j in range(i+1, len(transactions)):
                name2, time2, amount2, city2 = transactions[j].split(',')
                if name1 == name2 and abs(int(time2) - int(time1)) <= 60 and city1 != city2:
                    invalidSet.add(transactions[j])
                    invalidSet.add(transaction)
        
        return invalidSet
                


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transactions = sorted(transactions, key=lambda transaction: int(transaction.split(\",\")[1]))
        # print(transactions)
        record = {}
        invalid = []
        for transaction  in transactions:
            parse = transaction.split(',')
            if int(parse[2]) > 1000:
                invalid.append(transaction)
                
                
            
            if parse[0] in record:
                for prev in record[parse[0]]:
                    time = int(prev.split(\",\")[1])
                    loc = prev.split(\",\")[3]
                    if int(parse[1]) <= time + 60 and parse[3] != loc:

                        if prev not in invalid:
                            invalid.append(prev)
                        if transaction not in invalid:
                            invalid.append(transaction)

#                 time = record[parse[0]][\"time\"]
#                 loc = record[parse[0]][\"loc\"]
                
#                     
                    
#                 record[parse[0]][\"time\"] = int(parse[1])
#                 record[parse[0]][\"loc\"] = parse[3]
                record[parse[0]].append(transaction)

            
            else:
                record[parse[0]] = [transaction]
        
        return invalid

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        s = set()
        for i in range(0,len(transactions)):
            name,time,amount,city = transactions[i].split(\",\")
            if int(amount) > 1000:
                s.add(transactions[i])
            for j in range(i+1,len(transactions)):
                name1,time1,amount1,city1 = transactions[j].split(\",\")
        
                if name == name1 and abs(int(time)-int(time1))<=60 and city!=city1:
                
                    s.add(transactions[i])
                    s.add(transactions[j])
        return s              

class Solution:    
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        d = {}
        invalid = []
        answer = []
        for i in range(len(transactions)):
            trans = transactions[i].split(\",\")
            name,time,amt,city,ind = trans[0],int(trans[1]),int(trans[2]),trans[3],i
            
            if amt > 1000:
                invalid.append(i)
                answer.append(transactions[i])
                
            if name not in d:
                d[name] = [[name,time,amt,city,ind]]
            elif name in d:
                d[name].append([name,time,amt,city,ind])

        for k,v in d.items():
            v = sorted(v,key = lambda x: x[1])
            for i in range(len(v)):
                for j in range(len(v[i+1:])):
                    if (abs(v[i][1] - v[i+1:][j][1]) <= 60) and (v[i][3] != v[i+1:][j][3]):
                        if v[i][4] not in invalid:
                            invalid.append(v[i][4])
                            answer.append(transactions[v[i][4]])
                        if v[i+1:][j][4] not in invalid:
                            invalid.append(v[i+1:][j][4])
                            answer.append(transactions[v[i+1:][j][4]])

        
        return answer

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = []
        seen = {}
        for transaction in transactions:
            # print(transaction)
            # print(seen)
            name, time, amt, city = transaction.split(\",\")
            named_t = seen.get(name)
            if int(amt) > 1000:
                invalid.append(transaction)
                if named_t:
                    named_t.append(transaction)
                else:
                    named_t = [transaction]
                seen[name] = named_t
            if named_t:
                for ti in named_t:
                    n, t, a, c = ti.split(\",\")
                    if abs(int(time) - int(t)) <= 60 and c != city:
                        if transaction not in invalid:
                            invalid.append(transaction)
                        if ti not in invalid:
                            invalid.append(ti)
                named_t.append(transaction)
            else:
                named_t = [transaction]
            seen[name] = named_t
        return invalid
        

import collections
import bisect

class Solution:
    def invalidTransactions(self, orig: List[str]) -> List[str]:
        transactions = collections.defaultdict(lambda: [])
        
        for idx, t in enumerate(orig):
            name, time, amount, city = t.split(\",\")
            
            time = int(time)
            amount = int(amount)
            
            bisect.insort(transactions[name], [time, amount, city, idx])
            
        invalid_transactions = set([])
        
        for name in transactions:
            lst = transactions[name]
            lst = sorted(lst, key = lambda item: item[0])
            
            for idx in range(len(lst)):
                t1, a1, c1, i1 = lst[idx]
                
                if a1 > 1000:
                    invalid_transactions.add(i1)
                
                for idy in range(idx + 1, len(lst)):
                    if idx == idy:
                        continue
                        
                    t2, a2, c2, i2 = lst[idy]
                    
                    if (t2 - t1) <= 60 and c1 != c2:
                        invalid_transactions.add(i1)
                        invalid_transactions.add(i2)
                    elif (t2 - t2) > 60:
                        break
                        
        ret = []
        for index in invalid_transactions:
            ret.append(orig[index])
            
        return ret
                    

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        lenth = len(transactions)
        ans=set()
        for i in range(lenth):
            name,time,price,city=transactions[i].split(',')
            if int(price)>1000:
                ans.add(transactions[i])
                
            for j in range(i,lenth):
                    n_name,n_time,n_price,n_city=transactions[j].split(',')
                    if name==n_name and n_city !=city and abs(int(n_time)-int(time)) <=60:
                        ans.add(transactions[i])
                        ans.add(transactions[j])
        return ans 

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = set()
        # transactions = [i.split(\",\") for i in transactions]
        # transactions.sort(key = lambda x:(x[0],int(x[1])))
        # temp = transactions[0]
        # if int(temp[2])>1000:
        #     invalid.add(\",\".join(temp))
        # for i in transactions[1:]:
        #     if int(i[2])>1000:
        #         invalid.add(\",\".join(i))
        #         if i[0]==temp[0] and i[3]!=temp[3] and (int(i[1])-int(temp[1]))<=60:
        #             invalid.add(\",\".join(temp))
        #         temp = i
        #     elif i[0]==temp[0] and i[3]!=temp[3] and (int(i[1])-int(temp[1]))<=60:
        #         invalid.add(\",\".join(temp))
        #         invalid.add(\",\".join(i))
        #         temp = i
        #     else:
        #         temp = i        
        # return invalid
        
        for ind,val in enumerate(transactions):
            temp = val.split(\",\")
            if int(temp[2])>1000:
                invalid.add(val)
            for ind2 in range(ind+1, len(transactions)):
                temp2 = transactions[ind2].split(\",\")
                if temp2[0]==temp[0] and temp2[3]!=temp[3] and abs(int(temp2[1])-int(temp[1]))<=60:
                    invalid.add(transactions[ind2])
                    invalid.add(val)
        return invalid           
                
                
            
            

class Solution:    
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        d = {}
        answer = []
        for i in range(len(transactions)):
            trans = transactions[i].split(\",\")
            name,time,amt,city,ind = trans[0],int(trans[1]),int(trans[2]),trans[3],i
            
            if amt > 1000:
                answer.append(transactions[i])
                
            if name not in d:
                d[name] = [[name,time,amt,city,ind]]
            elif name in d:
                d[name].append([name,time,amt,city,ind])

        for k,v in d.items():
            v = sorted(v,key = lambda x: x[1])
            for i in range(len(v)):
                for j in range(len(v[i+1:])):
                    if (abs(v[i][1] - v[i+1:][j][1]) <= 60) and (v[i][3] != v[i+1:][j][3]):
                        if transactions[v[i][4]] not in answer:
                            answer.append(transactions[v[i][4]])
                        if transactions[v[i+1:][j][4]] not in answer:
                            answer.append(transactions[v[i+1:][j][4]])
                            
        return answer

import collections

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        output = []
        trans_dict = collections.defaultdict()
        
        for t in transactions:
            name, time, amount, city = t.split(\",\")
            if float(amount) > 1000:
                output.append(t)
            
            if name not in trans_dict.keys():
                trans_dict[name] = collections.defaultdict(list)
            
            trans_dict[name][city].append((int(time), amount))
            
            for c in trans_dict[name].keys():
                # print(t, \"t1\")
                if c != city:
                    for ta in trans_dict[name][c]:
                        t2, a2 = ta
                        # print(t, \"t2\", t2, int(time), a2)
                        if abs(t2-int(time))<=60:
                            prev_trans = name+\",\"+str(t2)+\",\"+a2+\",\"+c
                            if prev_trans not in output:
                                output.append(prev_trans)
                            if t not in output:
                                output.append(t)


        return output
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ret = []
        leng = len(transactions)
        sorted_trans = sorted(transactions, key = lambda i: int(i.split(\",\", 3)[1]))
        print(sorted_trans)
        for i, trans in enumerate(sorted_trans):
            name, time, amount, city = trans.split(\",\")
            # first check amount
            if int(amount) > 1000 and trans not in ret:
                ret.append(trans)
            # second, check 60 min of another in same city
            for i in range(i+1, leng):
                if int(sorted_trans[i].split(\",\")[1]) - int(time) <= 60:
                    if sorted_trans[i].split(\",\")[3] != city and sorted_trans[i].split(\",\")[0] == name:
                        if trans not in ret: ret.append(trans)
                        if sorted_trans[i] not in ret: ret.append(sorted_trans[i])
                    continue
                else:
                    break
        return ret

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        inv = set()
        
        for i in range(len(transactions)):
            cur = transactions[i].split(\",\")
            if (int(cur[2]) > 1000):
                inv.add(','.join(cur))
                cur_inv = True
            for j in range(i, len(transactions) - 1):
                comp = transactions[j + 1].split(\",\")
                if (comp[0] == cur[0]):
                    if (abs(int(comp[1]) - int(cur[1])) <= 60 and comp[3] != cur[3]):
                        inv.add(','.join(cur))
                        inv.add(','.join(comp))
        return inv

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        temp=[]        
        for t in transactions:
            temp.append(t.split(','))
            
        res=[]  
        for i in range(len(temp)):
            if int(temp[i][2])>1000 and ','.join(temp[i]) not in res :
                res.append(','.join(temp[i]))
            for j in range(i+1, len(temp)):
                if temp[i][0]==temp[j][0] and temp[i][3]!=temp[j][3]:
                    if abs(int(temp[i][1])-int(temp[j][1]))<=60:
                        if ','.join(temp[i]) not in res:
                            res.append(','.join(temp[i]))
                        if ','.join(temp[j]) not in res:
                            res.append(','.join(temp[j]))
        return res
            


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        arr = []
        for x in transactions:
            n, a, t, p = x.split(',')
            arr.append([n, a, t, p])
        
        inv = []
        for i in range(len(arr)):
            n, t, a, p = arr[i]
            added = False
            if int(a) > 1000:
                inv.append(arr[i])
                added = True
            for j in range(i + 1, len(arr)):
                
                nn, tt, aa, pp = arr[j]
                
                if abs(int(t) - int(tt)) <= 60 and n == nn and p != pp:
                    if not added: 
                        inv.append(arr[i])
                        added = True
                    inv.append(arr[j])
                    
        
        inv = [','.join(x) for x in inv]
        inv = list(set(inv))
        return (inv)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        arr = []
        for x in transactions:
            n, a, t, p = x.split(',')
            arr.append([n, a, t, p])
        
        inv = []
        for i in range(len(arr)):
            n, t, a, p = arr[i]
            added = False
            if int(a) > 1000:
                inv.append(arr[i])
                added = True
            for j in range(i + 1, len(arr)):
                
                nn, tt, aa, pp = arr[j]
                
                if abs(int(t) - int(tt)) <= 60 and n == nn and p != pp:
                    if not added: inv.append(arr[i])
                    inv.append(arr[j])
                    continue
        
        inv = [','.join(x) for x in inv]
        inv = list(set(inv))
        return (inv)

import collections
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        byName = collections.defaultdict(list)
        invalids = set()
        for transaction in transactions:
            name, t_min, amt, city = transaction.split(',')
            byName[name].append((int(t_min), int(amt), city, transaction))
            if int(amt) > 1000:
                invalids.add(transaction)
        for name in byName:
            trans = byName[name]
            for i in range(len(trans)):
                for j in range(i, len(trans)):
                    if abs(trans[i][0] - trans[j][0]) <= 60 and trans[i][2] != trans[j][2]: 
                        invalids.add(trans[i][3])
                        invalids.add(trans[j][3])
        return list(invalids)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transactionDict = {}
        invalid = []
        for i in transactions:
            transactionData = i.split(',')
            name, time, amount, city = transactionData[0], transactionData[1], transactionData[2], transactionData[3]
            if name in transactionDict.keys():
                transactionVal = transactionDict[name]
            else:
                transactionVal = []
            transactionVal.append([time, amount, city])
            transactionDict[name] = transactionVal
        for i in transactionDict.keys():
            for v in transactionDict[i]:
                #test if transaction over 1000
                if int(v[1]) > 1000:
                    if '{},{},{},{}'.format(i, v[0], v[1], v[2]) not in invalid:
                        invalid.append('{},{},{},{}'.format(i, v[0], v[1], v[2]))
                #test if any other transaction time within 60 in a different city
                for listd in transactionDict[i]:
                    if listd != v:
                        if abs(int(v[0]) - int(listd[0])) <= 60 and v[2] != listd[2]:
                            if '{},{},{},{}'.format(i, v[0], v[1], v[2]) not in invalid:
                                invalid.append('{},{},{},{}'.format(i, v[0], v[1], v[2]))
        return invalid

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalids = set()
        
        for i in range(len(transactions)):
            name, time, amount, city = transactions[i].split(',')
            if int(amount) > 1000:
                invalids.add(transactions[i])
            j = i +1
            while j < len(transactions):
                nameJ, timeJ, amountJ, cityJ = transactions[j].split(',')
                if nameJ == name and abs(int(timeJ) - int(time)) <= 60 and city != cityJ:
                    invalids.add(transactions[i])
                    invalids.add(transactions[j])
                j+=1
        return list(invalids)


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        name = []
        time = []
        amount = []
        city = []
        for t in transactions:
            n,t,a,c = t.split(\",\")
            name.append(n)
            time.append(int(t))
            amount.append(int(a))
            city.append(c)
        
        ans = set()
        N = len(transactions)
        for i in range(N):
            if amount[i] > 1000:
                ans.add(transactions[i])
            for j in range(N):
                if i == j: continue
                if name[i] == name[j] and abs(time[i]-time[j]) <= 60 and city[i] != city[j]:
                    ans.add(transactions[j])
        return ans

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        # { name -> {time -> amount city i} 
        invalidIdxList = set()
        transDict = {}
        for i, transaction in enumerate(transactions):
            name, time, amount, city = transaction.split(',')
            if int(amount) > 1000:
                invalidIdxList.add(i)
            j = i + 1
            while j < len(transactions):
                otherName, otherTime, otherAmount, otherCity = transactions[j].split(',')
                if name == otherName and abs(int(time) - int(otherTime)) <= 60 and city != otherCity:
                    invalidIdxList.add(i)
                    invalidIdxList.add(j)
                j = j + 1
        res = []
        for idx in invalidIdxList:
            res.append(transactions[idx])
        return res
              

                    
                    
                    
                    
            
                
            
        


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        n = len(transactions)
        invalid_check = [0]*n
        for i in range(n):
            i_info = transactions[i].split(',')
            assert(len(i_info) == 4)
            if(int(i_info[2]) >= 1000): invalid_check[i] = 1
            for j in range(i+1, n):
                j_info = transactions[j].split(',')
                assert(len(j_info) == 4)
                if(i_info[0] == j_info[0] and
                   i_info[3] != j_info[3] and
                    abs(int(i_info[1]) - int(j_info[1])) <= 60) :
                    invalid_check[i] = invalid_check[j] = 1
        ret = []
        for i in range(n):
            if(invalid_check[i]): ret.append(transactions[i])
        return ret
                


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        in_val = []
        trans = []
        for each in transactions:
            temp = each
            temp = temp.split(\",\")
            trans.append(temp)
        #print(trans)
        
        size = len(trans)
        for i in range(size):
            if int(trans[i][2]) > 1000:
                if transactions[i] not in in_val:
                    in_val.append(transactions[i])
            else:
                for j in range(size):
                    if i != j and trans[i][0] == trans[j][0] and abs(int(trans[i][1])-int(trans[j][1])) <= 60 and trans[i][3] != trans[j][3]:
                        if transactions[i] not in in_val:
                            in_val.append(transactions[i])
        return in_val
        
        
        
        
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalids = []
        val_dict = defaultdict(list)
        
        for trs in transactions:
            #print(val_dict)
            trs_list = trs.split(\",\")
            amount = int(trs_list[2])
            
            val_dict[trs_list[0]].append((int(trs_list[1]),int(trs_list[2]), trs_list[3]))

            for trans in val_dict[trs_list[0]]:
                if abs(int(trs_list[1]) - int(trans[0])) <= 60 and trs_list[3] != trans[2]:
                    if trs not in invalids:
                        invalids.append(trs)

                    if str(trs_list[0])+\",\"+str(trans[0])+\",\"+str(trans[1])+\",\"+str(trans[2]) not in invalids:
                        invalids.append(str(trs_list[0])+\",\"+str(trans[0])+\",\"+str(trans[1])+\",\"+str(trans[2]))
                
            
            if amount > 1000:
                invalids.append(trs)
                
                
        return list(set(invalids))
                
            
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ans = []
        num = len(transactions)
        added = set()
        for i in range(num):
            name1, time1, num1, city1 = transactions[i].split(',')
            if int(num1) > 1000 and i not in added:
                ans.append(transactions[i])
                added.add(i)
            for j in range(i+1, num):
                name2, time2, num2, city2 = transactions[j].split(',')
                if (name1 == name2 and 
                    abs(int(time2) - int(time1)) <= 60 
                    and city2 != city1):
                    if i not in added:
                        ans.append(transactions[i])
                        added.add(i)  
                    if j not in added:
                        ans.append(transactions[j])
                        added.add(j)  
        return ans
            
        
            


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        res = set()
        
        for i in range(len(transactions) - 1):
            t1 = transactions[i].split(',')
            # transaction over $1000
            if int(t1[2]) > 1000:
                res.add(transactions[i])
            for j in range(i + 1, len(transactions)):
                t2 = transactions[j].split(',')
                # names match, cities do not match, transactions within 60 min
                if t1[0] == t2[0] and t1[3] != t2[3] and abs(int(t2[1]) - int(t1[1])) <= 60:
                    res.add(transactions[i])
                    res.add(transactions[j])
                if int(t2[2]) > 1000:
                    res.add(transactions[j])
                    
        return list(res)
                
                    
                
                
                


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        M = collections.defaultdict(dict)
        
        ans = set()  # avoid duplicate
        for t in transactions:
            name, time, amount, city = t.split(',')
            if int(amount) > 1000:              # invalid condition 1
                ans.add(t)

            Flag = False
            if name in M:                       # have transaction under the name
                for k,v in list(M[name].items()):     # iterate all (time, transaction) pairs under this name
                    if abs(int(time)-k) <= 60 and v.split(',')[-1] != city:  # invalid condition 2
                        ans.add(v)
                        Flag = True             # add current transaction
            M[name][int(time)] = t              # add transaction to HashMap
            if Flag:
                ans.add(t)
        
        return list(ans)


class Solution:
    def isinterval(self,a,b):
        if abs(int(a)-int(b))<=60:
            return True
        return False
    def issame(self,a,b):
        if a!=b:
            return True
        return False
    
    def issamename(self,a,b):
        if a==b:
            return True
        return False
    def invalidTransactions(self, A: List[str]) -> List[str]:
        arr=[]
        index=0
        n=len(A)
        while index<n:
            arr.append(list(A[index].split(',')))
            index+=1
        
        arr=sorted(arr,key=lambda x:int(x[1]))
        visited=[True for i in range(n)]
        result=[]
        for i in range(n):
            if int(arr[i][2])>1000:
                result.append(\",\".join(arr[i]))
                visited[i]=False
            for j in range(i+1,n):    
                if self.isinterval(arr[i][1],arr[j][1]) and arr[i][3]!=arr[j][3] and arr[i][0]==arr[j][0]:
                    if visited[i]:
                        visited[i]=False
                        result.append(\",\".join(arr[i]))                    
                    if visited[j]:
                        visited[j]=False
                        result.append(\",\".join(arr[j]))                    
                    
                
        result=list(set(result))                                                       
                
        return result
            
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = set()
        for i, t in enumerate(transactions):
            name, time, amount, city = t.split(',')
            if int(amount) > 1000:
                invalid.add(i)
                continue
            for j in range(len(transactions)):
                if i == j: continue
                jname, jtime, jamount, jcity = transactions[j].split(',')
                if jname == name and jcity != city and abs(int(jtime) - int(time)) <= 60:
                    invalid.add(i)
                    invalid.add(j)
        
        return [transactions[i] for i in invalid]

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        res = []
        for i in range(len(transactions)):
            added = False
            for j in range(i + 1, len(transactions)):
                a = transactions[i].split(',')
                b = transactions[j].split(',')
                if a[0] == b[0] and a[-1] != b[-1] and abs(int(a[1]) - int(b[1])) <= 60:
                    res.append(','.join(a))
                    res.append(','.join(b))
                    added = True
            if not added:
                if int(transactions[i].split(',')[2]) > 1000:
                    res.append(transactions[i])

        return list(set(res))

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        res = set()
        for i in range(len(transactions)):
            added = False
            for j in range(i + 1, len(transactions)):
                a = transactions[i].split(',')
                b = transactions[j].split(',')
                if a[0] == b[0] and a[-1] != b[-1] and abs(int(a[1]) - int(b[1])) <= 60:
                    res.add(','.join(a))
                    res.add(','.join(b))
                    added = True
            if not added:
                if int(transactions[i].split(',')[2]) > 1000:
                    res.add(transactions[i])

        return list(res)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalids = set()
        
        
        for i in range(len(transactions)):
            name, time, amount, city = transactions[i].split(',')
            if int(amount) > 1000:
                invalids.add(transactions[i])
            j = i +1
            while j < len(transactions):
                nameJ, timeJ, amountJ, cityJ = transactions[j].split(',')
                if nameJ == name and abs(int(timeJ) - int(time)) <= 60 and city != cityJ:
                    invalids.add(transactions[i])
                    invalids.add(transactions[j])
                j+=1
        return list(invalids)
            
                
        print (invalids)
        \"\"\"
        Hashtable => NO
        
        Two Pointer yes
        
        
        
        \"\"\"
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transactions_dict = defaultdict(list)
        invalid = []
        for i in range(len(transactions)):
            details = transactions[i].split(\",\")
            if int(details[2]) > 1000:
                invalid.append(transactions[i])
            
            for j in range(i+1, len(transactions)):
                name,time, amount,city = transactions[j].split(\",\")
                if abs(int(details[1]) - int(time)) <=60 and details[0] == name :
                    if (details[3] != city):
                        invalid.append(transactions[i])
                        invalid.append(transactions[j])
                
        return list(set(invalid))
        

class Solution:
    def invalidTransactions(self, ts: List[str]) -> List[str]:
        nts = [t.split(',') for t in ts]
        nts = sorted([[a, int(b), int(c), d] for a, b, c, d in nts])
        res = set()
        for a in nts:
            if a[2] > 1000: res.add(','.join(map(str,a)))
        for i in range(len(nts)):
            for j in range(i + 1, len(nts)):
                a, b = nts[i], nts[j]
                if a[0] != b[0] or abs(a[1] - b[1]) > 60: break
                if a[3] != b[3]: 
                    res.add(','.join(map(str,a)))
                    res.add(','.join(map(str,b)))
        return list(res)

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

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transactions = [Transaction(*t.split(',')) for t in transactions]
        transactions.sort(key = lambda x: x.time)
        nameMap = collections.defaultdict(list)
        for i, t in enumerate(transactions):
            nameMap[t.name].append(i)
        invalid = []
        for name, idxLst in nameMap.items():
            left = 0
            right = 0
            for idx in idxLst:
                t = transactions[idx]
                if t.amount > 1000:
                    invalid.append(f'{t.name},{t.time},{t.amount},{t.city}')
                    continue
                while left < len(idxLst) and transactions[idxLst[left]].time < t.time-60:
                    left += 1
                while right < len(idxLst) and transactions[idxLst[right]].time <= t.time+60:
                    right += 1
                for i in range(left, right):
                    if t.city != transactions[idxLst[i]].city:
                        invalid.append(f'{t.name},{t.time},{t.amount},{t.city}')
                        break
        return invalid

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        if not transactions or len(transactions) ==0:
            return []
        
        d = collections.defaultdict(dict)
        res = set()
        
        for t in transactions:
            name,time,amount,city = t.split(',')
            
            if int(amount) > 1000:
                res.add(t)
            
            flag = False
            if name in d:
                
                for _time,_t in d[name].items():
                    
                    if abs(_time-int(time)) <= 60 and city != _t.split(',')[-1]:
                        flag = True
                        res.add(_t)
            
            if flag:
                res.add(t)
                
            d[name][int(time)] = t
        
        return list(res)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = []
        
        for i, t1 in enumerate(transactions):
            name1, time1, amount1, city1 = t1.split(',')
            if int(amount1) > 1000:
                invalid.append(t1)
                continue
            for j, t2 in enumerate(transactions):
                if i != j: 
                    name2, time2, amount2, city2 = t2.split(',')
                    if name1 == name2 and city1 != city2 and abs(int(time1) - int(time2)) <= 60:
                        invalid.append(t1)
                        break
        
        return invalid


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = []
        for ind,trn in enumerate(transactions):
            name,time,amt,city = trn.split(\",\")
            if int(amt)>1000:
                invalid.append(trn)
                continue
            for j,trn2 in enumerate(transactions):
                if ind!=j:
                    name1,time1,amt1,city1 = trn2.split(\",\")
                    if name==name1 and abs(int(time)-int(time1))<=60 and city!=city1:
                        invalid.append(trn)
                        break
        return invalid

import collections
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = []
        mapNameToTrans = collections.defaultdict(list)
        
        for t in transactions:
            name, time, amount, city = t.split(',')
            if int(amount) > 1000:
                invalid.append(t)
                did_add = True
            else:
                did_add = False
            for past in mapNameToTrans[name]:
                if abs(int(past[0]) - int(time)) <= 60 and past[1] != city:
                    if not did_add:
                        invalid.append(t)
                        did_add = True
                    if not past[2]:
                        past[2] = True
                        invalid.append(past[3])
            mapNameToTrans[name].append([time, city, did_add, t])
        return invalid


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        personalTransactions = {}
        invalidTransactions = set()
        for i in transactions:
            name, time, amount, city = i.split(',')
            if(int(amount) > 1000):
                invalidTransactions.add(i)
            if(name not in personalTransactions.keys()):
                personalTransactions[name] = [(int(time), city, amount)]
                continue
            else:
                personalTransactions[name].append((int(time), city, amount))
                for j in personalTransactions[name]:
                    if(city == j[1]):
                        continue
                    else:
                        if(abs(j[0]-int(time)) <= 60):
                            invalidTransactions.add(i)
                            invalidTransactions.add(name+','+str(j[0])+','+j[2]+','+j[1])
        return list(invalidTransactions)

class Solution:
    def invalidTransactions(self, arr: List[str]) -> List[str]:
        self.memo = collections.defaultdict(list)
        ans = set()
        for s in arr:
            name, mi, mon, place = s.split(\",\")
            if int(mon) > 1000:
                ans.add(s)
            if self.memo[name]:
                flag = False
                for a,b,c,d in self.memo[name]:
                    if d != place and abs(int(mi) - b) <= 60:
                        flag = True
                        ans.add(a + \",\" + str(b) + \",\" + str(c) + \",\" + d)
                if flag:
                    ans.add(s)
            self.memo[name] += ((name, int(mi), int(mon), place)),
        return ans

class Solution:
    def invalidTransactions(self, arr: List[str]) -> List[str]:
        self.memo = collections.defaultdict(list)
        ans = set()
        for s in arr:
            name, mi, mon, place = s.split(\",\")
            if int(mon) > 1000:
                ans.add(s)
            if self.memo[name]:
                flag = False
                for a,b,c,d in self.memo[name]:
                    if d != place and abs(int(mi) - b) <= 60:
                        flag = True
                        ans.add(a + \",\" + str(b) + \",\" + str(c) + \",\" + d)
                if flag:
                    ans.add(s)
            self.memo[name] += ((name, int(mi), int(mon), place)),
        return ans


class T:
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city
    def get_string(self):
        return self.name+\",\"+str(self.time)+\",\"+str(self.amount)+\",\"+self.city

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        # create T object
        ts = []
        for tran in transactions:
            ts.append(T(*tran.split(\",\")))
        ts.sort(key=lambda t: t.time)
        name2t = defaultdict(list)
        
        for t in ts:
            name2t[t.name].append(t)
        res = []
        for name,ts in name2t.items():
            for i,t in enumerate(ts):
                left,right = 0,0
                if t.amount > 1000: 
                    res.append(t.get_string())
                    continue
                
                while left <= len(ts)-2 and ts[left].time < t.time-60: # O(60)
                    left+=1 # 아주맨마지막까지가는거 가능
                while right <= len(ts)-2 and ts[right+1].time <= t.time+60: # O(60)
                    right+=1 # 아주맨마지막까지가는거 가능
                    
                for i in range(left, right+1): # O(120)
                    cand_t = ts[i]
                    if cand_t.city != t.city:
                        res.append(t.get_string())
                        break
        return res

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transMap = dict() # name: [time, city, t]
        invalids = set()
        
        for t in transactions:
            name, time, amount, city = t.split(',')
            if int(amount) > 1000:
                invalids.add(t)
            if name in transMap:
                for stime, scity, st in transMap[name]:
                    if abs(int(time) - int(stime)) <= 60 and city != scity:
                        invalids.add(st)
                        invalids.add(t)
            else:
                transMap[name] = []
            transMap[name].append((time, city, t))
        return list(invalids)


class Solution:
    # > 1000
    # same name, different city, <= 60 min
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
#         loop through transactions 
#             if amount is greater >= 1000 add it to invalid set
#             have another loop, check every other transactions for invalid time
         
        # { invalidtransaction}
        # {
        #     alice: [\"transaction\",\"transaction\"]
        #     bob: [\"transaction\"]
        # }
        
        # userTransactions = collections.defaultdict(list)
        invalidTransactions = set()
        
        for i,transaction in enumerate(transactions):
            [name,time,amount,city] = transaction.split(\",\")
            
            if int(amount) > 1000: invalidTransactions.add(transaction)
            # userTransactions[name].append(transaction)
            
            for j in range(len(transactions)):
                if i!=j:
                    [name2,time2,amount2,city2] = transactions[j].split(\",\")

                    if name==name2 and abs(int(time)-int(time2)) <= 60 and city!=city2:
                        invalidTransactions.add(transaction)
                        invalidTransactions.add(transactions[j])
                        break
                
                
                
                
                
                
                
                
                
                
                
                
                
                
                
                
                
            
            
            
#         for name in userTransactions:
#             userTrans = userTransactions[name]
            
#             for i in range(len(userTrans)-1):
#                 for j in range(i+1,len(userTrans)):
#                     [_,time,_,city] = userTrans[i].split(\",\")
#                     [_,time2,_,city2] = userTrans[j].split(\",\")
                    
#                     if abs(int(time)-int(time2)) <= 60 and city != city2:
#                         invalidTransactions.add(userTrans[i])
#                         invalidTransactions.add(userTrans[j])
                    
        return list(invalidTransactions)
            
                
        
        
        

class Transaction(object):
    def __init__(self, txn):
        name, time, amount, city = txn.split(',')
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city
        
    def __str__(self):
        return \"{},{},{},{}\".format(self.name, self.time, self.amount, self.city)
    
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        d = defaultdict(list)
        ans = []
        txns = list(map(Transaction, transactions))
        for i, t in enumerate(txns):
            d[t.name].append(i)
        for name, tid in d.items():    
            l = r = 0
            for t in (tid := sorted(tid, key=lambda x:txns[x].time)):
                if txns[t].amount > 1000:
                    ans.append(t)
                    continue
                while l + 1 < len(tid) and txns[tid[l]].time + 60 < txns[t].time:
                    l += 1
                while r + 1 < len(tid) and txns[tid[r+1]].time <= txns[t].time + 60:
                    r += 1
                for j in range(l, r+1):
                    if txns[tid[j]].city != txns[t].city:
                        ans.append(t)
                        break
        return [str(transactions[i]) for i in ans]      

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = set()
        seen = {}
        for i in range(len(transactions)):
            trans = transactions[i].split(\",\")
            if trans[0] in seen: 
                for old in seen[trans[0]]:
                    if old[0] != trans[3] and abs(int(old[1])-int(trans[1])) <= 60:
                        invalid.add(transactions[i])
                        invalid.add(transactions[old[2]])
            if int(trans[2]) > 1000:
                invalid.add(transactions[i])
            
            if trans[0] in seen:
                seen[trans[0]].append([trans[3],trans[1],i])
            else:
                seen[trans[0]] = [[trans[3],trans[1],i]]
        
        return invalid
            
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        res = set()
        list_transactions = []
        hash = defaultdict(list)
        for i, t in enumerate(transactions):
            temp = t.split(\",\")
            temp.append(i)
            list_transactions.append(temp)
            
        for i in range(len(list_transactions)):
            t1 = list_transactions[i]
            if int(t1[2]) > 1000:
                res.add(transactions[i])
            
            if t1[0] in hash:
                for t2 in hash[t1[0]]:
                    if t2[3] != t1[3] and abs(int(t1[1]) - int(t2[1])) <= 60:
                        res.add(transactions[t2[4]])
                        res.add(transactions[i])
            hash[t1[0]].append(t1)

                    
        return list(res)
                
                    
                
                
                
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        res = set()
        # list_transactions = []
        hash = defaultdict(list)
        # for i, t in enumerate(transactions):
        #     temp = t.split(\",\")
        #     temp.append(i)
        #     list_transactions.append(temp)
            
#         for i in range(len(list_transactions)):
#             t1 = list_transactions[i]
#             if int(t1[2]) > 1000:
#                 res.add(transactions[i])
            
#             if t1[0] in hash:
#                 for t2 in hash[t1[0]]:
#                     if t2[3] != t1[3] and abs(int(t1[1]) - int(t2[1])) <= 60:
#                         res.add(transactions[t2[4]])
#                         res.add(transactions[i])
#             hash[t1[0]].append(t1)
            
        for i in range(len(transactions)):
            t1 = transactions[i].split(\",\")
            t1.append(i)
            if int(t1[2]) > 1000:
                res.add(transactions[i])
            
            if t1[0] in hash:
                for t2 in hash[t1[0]]:
                    if t2[3] != t1[3] and abs(int(t1[1]) - int(t2[1])) <= 60:
                        res.add(transactions[t2[4]])
                        res.add(transactions[i])
            hash[t1[0]].append(t1)

                    
        return list(res)
                
                    
                
                
                
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        trans , invalid = [ ] , [ ]
        for t in transactions :
            trans += t.split( ',' ) ,
        trans.sort( key = lambda x : int( x[ 1 ] ) )
        invalid = set()
        for i in range( len( trans ) ) :
            if int( trans[ i ][ 2 ] ) > 1000 :
                invalid.add( ','.join( trans[ i ] ) )
                if i :
                    j = i
                    while j and int( trans[ i ][ 1 ] ) - int( trans[ j - 1 ][ 1 ] ) < 61 :
                        if trans[ i ][ 0 ] == trans[ j - 1 ][ 0 ] and trans[ i ][ 3 ] != trans[ j - 1 ][ 3 ] :
                            invalid.add( ','.join( trans[ j - 1 ] ) )
                        j -= 1

            elif i and int( trans[ i ][ 1 ] ) - int( trans[ i - 1 ][ 1 ] ) < 61 :
                j = i
                while j and int( trans[ i ][ 1 ] ) - int( trans[ j - 1 ][ 1 ] ) < 61 :                    
                    if trans[ i ][ 0 ] == trans[ j - 1 ][ 0 ] and trans[ i ][ 3 ] != trans[ j - 1 ][ 3 ] :
                        invalid.add( ','.join( trans[ j - 1 ] ) )
                        invalid.add( ','.join( trans[ i ] ) )
                    j -= 1
        return invalid
    #Sanyam Rajpal


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        def giddy(item):
            return item.split(',')
        
        result = set()
        seen = collections.defaultdict(list)
        transactions = list(map(giddy, transactions))
        # transactions.sort(key=lambda x: x[1])
        # print(transactions)
        for i in range(len(transactions)):
            val = transactions[i]
            if int(val[2])>1000:
                result.add(','.join(val))
            if val[0] in seen:
                # print(seen)
                for x in seen[val[0]]:
                    comp = transactions[x]
                    # print(comp)
                    if abs(int(comp[1])-int(val[1]))<=60 and comp[3] != val[3]:
                        result.add(','.join(val))
                        result.add(','.join(comp))
            seen[val[0]].append(i)
            # while seen[val[0]]:
        return result

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        mp = {}
        res = set()
        for string in transactions:
            l = string.split(',')
            person = l[0]
            time = l[1]
            amount = l[2]
            city = l[3]
            
            if int(amount)>1000:
                res.add(string)
                #continue
                
            if person in mp:
                #print(mp[person])
                for val in mp[person]:
                    time_1 = val[0]
                    if abs(int(time)-int(time_1))<=60 and val[2]!=city:
                        print(abs(int(time)-int(time_1)))
                        str1 = person+\",\"+time_1+\",\"+val[1]+\",\"+val[2]
                        res.add(str1)
                        res.add(string)
            if person not in mp:
                mp[person] = [[time,amount,city]]
            else:
                mp[person].append([time,amount,city])
            
        
        r = [x for x in res]
        return r

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        res = set()
        past_ts = {}
        for t in transactions:
            vals = t.split(\",\")
            name = vals[0]
            time = int(vals[1])
            amount = int(vals[2])
            city = vals[3]
            
            if name in past_ts:
                pre_trs = past_ts[name]
                for pre_r in pre_trs:
                    pre_t = pre_r.split(\",\")
                    pre_time = int(pre_t[1])
                    pre_city = pre_t[3]
                    if abs(time - pre_time) <= 60 and city != pre_city:
                        res.add(t)
                        res.add(pre_r)
            else:
                past_ts[name] = []
            if amount > 1000:
                if t not in res:
                    res.add(t)
                    
            past_ts[name].append(t)
        return res

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        invalid_trans = set()
        d = {}
        for transaction in transactions:
            t_list = transaction.split(',')
            person, time, amount, loc = t_list[0], int(t_list[1]), int(t_list[2]), t_list[3]
            
            if amount > 1000:
                invalid_trans.add(transaction)
            
            if person not in d:
                d[person] = []
            else:
                for t in d[person]:
                    old_t = t.split(',')
                    old_time, old_loc = int(old_t[1]), old_t[3]
                    
                    if abs(old_time-time)<=60 and old_loc != loc:
                        invalid_trans.add(transaction)
                        invalid_trans.add(t)
            
            d[person].append(transaction)
            
        
        return list(invalid_trans)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:
            return []
        invalid = set()
        past_tran = {}
        for transaction in transactions:
            tran = transaction.split(',')
            tran[2]=float(tran[2])
            tran[1]=float(tran[1])
            if tran[2]>1000:
                invalid.add(transaction)
            if tran[0] in past_tran:
                for other_transaction in past_tran[tran[0]]:
                    other_tran = other_transaction.split(',')
                    other_tran[1]=float(other_tran[1])
                    if other_tran[3]!=tran[3] and abs(tran[1]-other_tran[1])<=60:
                        invalid.add(transaction)   
                        invalid.add(other_transaction)
                past_tran[tran[0]].append(transaction)
                                                    
            else:
                past_tran[tran[0]]=[transaction]
        return list(invalid)


class Transaction:  
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city
        
    def __str__(self):
        return f'{self.name},{self.time},{self.amount},{self.city}'

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transactions = [Transaction(*t.split(',')) for t in transactions]
        transactions.sort(key = lambda x: x.time)
        nameMap = collections.defaultdict(list)
        for i, t in enumerate(transactions):
            nameMap[t.name].append(i)
        invalid = []
        for name, idxLst in nameMap.items():
            left = 0
            right = 0
            for idx in idxLst:
                t = transactions[idx]
                if t.amount > 1000:
                    invalid.append(str(t))
                    continue
                while left < len(idxLst) and transactions[idxLst[left]].time < t.time-60:
                    left += 1
                while right < len(idxLst) and transactions[idxLst[right]].time <= t.time+60:
                    right += 1
                for i in range(left, right):
                    if t.city != transactions[idxLst[i]].city:
                        invalid.append(str(t))
                        break
        return invalid

import collections
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = []
        mapNameToTrans = collections.defaultdict(list)
        
        for t in transactions:
            name, time, amount, city = t.split(',')
            did_add = False
            if int(amount) > 1000:
                invalid.append(t)
                did_add = True
            for past in mapNameToTrans[name]:
                past_name, past_time, past_amount, past_city = past[0].split(',')
                if past_city != city and abs(int(past_time) - int(time)) <= 60:
                    if not did_add:
                        invalid.append(t)
                        did_add = True
                    if not past[1]:
                        past[1] = True
                        invalid.append(past[0])
            mapNameToTrans[name].append([t, did_add])
        return invalid


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        res=[]
        for i,t1 in enumerate(transactions):
            item=t1.split(',')
            val=int(item[2])
            minute=int(item[1])
            name=item[0]
            city=item[-1]
            if(val>1000):
                res.append(t1)
                continue
            for j,t2 in enumerate(transactions):
                if(i!=j):
                    item=t2.split(',')
                    val2=int(item[2])
                    minute2=int(item[1])
                    name2=item[0]
                    city2=item[-1]
                    if(abs(minute2-minute)<=60 and name2==name and city2!=city):
                        res.append(t1)
                        break
           
        return res

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        dic = defaultdict(list)
        ans = set()
        for trans in transactions:
            name, time, amt, loc = trans.split(',')
            if int(amt) > 1000:
                ans.add(trans)
            for trans2 in dic[name]:
                other = trans2.split(',')
                if other[3] != loc and abs(int(other[1]) - int(time)) <= 60:
                    ans.add(trans)
                    ans.add(trans2)
            dic[name].append(trans)
        
        return ans

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:
            return []
        invalid = set()
        past_tran = {}
        for transaction in transactions:
            tran = transaction.split(',')
            tran[2]=float(tran[2])
            tran[1]=float(tran[1])
            if tran[2]>1000:
                invalid.add(transaction)
                # past_tran[tran[0]]=[transaction]
            if tran[0] in past_tran:
                for other_transaction in past_tran[tran[0]]:
                    other_tran = other_transaction.split(',')
                    other_tran[1]=float(other_tran[1])
                    if other_tran[3]!=tran[3] and abs(tran[1]-other_tran[1])<=60:
                        invalid.add(transaction)   
                        invalid.add(other_transaction)
                past_tran[tran[0]].append(transaction)                                
            else:
                past_tran[tran[0]]=[transaction]
        return list(invalid)

    


from collections import defaultdict
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        # occurs within 60 mins of another transaction,
        # does the previous transaction need to be valid? -> No
        invalid = set()
        records = defaultdict(list)
        for transaction in transactions:
            name, time, value, city = transaction.split(\",\")
            if int(value) > 1000:
                invalid.add(transaction)
            if name in records:
                for record in records[name]:
                    last_name, last_time, last_value, last_city = record.split(\",\")
                    if abs(int(time) - int(last_time)) <= 60 and city != last_city:
                        invalid.add(record)
                        invalid.add(transaction)
            records[name].append(transaction)
        return invalid
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        # first check : if amount > 1000 invalid
        # second check : else:
        #       if name equals with another transaction : if time_this - time_that <60 and city not equal both invalid
        #                                                 if time_this - time_that <60 and city equal both valid
        
        tr = {}
        invalids = set()
        
        for t in transactions:
            tl = t.split(',')
            
            if tl[0] not in tr:                 
                tr[tl[0]] = [t]
                if int(tl[2]) > 1000:  # amount > 1000
                    invalids.add(t)                
                    
            else:   # name equal                
                if int(tl[2]) > 1000:  # amount > 1000
                    invalids.add(t)                   
                tmp = tr[tl[0]]  # amount < 1000                 
                for temp in tmp:                        
                    tempo = temp.split(',')                        
                    if tempo[3] != tl[3]: # city not equal
                        if abs(int(tempo[1])- int(tl[1])) <= 60:  # less than 60 min
                            invalids.add(t) 
                            invalids.add(temp)
                                  
                tr[tl[0]].append(t)               
        return invalids


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        if not transactions:
            return []
        
        res = set()
        n = len(transactions)
        transactions.sort()
       
        for i in range(n):
            n1, t1, a1, d1 = transactions[i].split(',')
            if int(a1) > 1000:
                res.add(transactions[i])
            for j in range(i+1, n):
                n0, t0, a0, d0 = transactions[j].split(',')
                if n0 == n1:
                    if d1 != d0 and abs(int(t1)-int(t0)) <= 60:
                        res.add(transactions[i])
                        res.add(transactions[j])
                else:
                    break
        
        ans = []
        for t in res:
            ans.append(t)
        print(res, ans)
        return ans

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        output = []
        names = {}
        inOutput = set()
        
        for idx, trans in enumerate(transactions):
            curr = trans.split(\",\")
            print(curr)
            
            if curr[0] not in names:
                names[curr[0]] = [idx]
            else:
                for transIdx in names[curr[0]]:
                    personTrans = transactions[transIdx].split(\",\")
                    if curr[3] != personTrans[3] and abs(int(curr[1]) - int(personTrans[1])) <= 60:
                        if idx not in inOutput:
                            output.append(trans)
                            inOutput.add(idx)
                        if transIdx not in inOutput:
                            output.append(transactions[transIdx])
                            inOutput.add(transIdx)
                names[curr[0]].append(idx)
                
            if int(curr[2]) > 1000 and idx not in inOutput:
                output.append(trans)
                inOutput.add(idx)
        
        return output

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        from collections import defaultdict
        newd =defaultdict(list)
        result =set()
        for j in range(len(transactions)):
            details = transactions[j].split(\",\")
            
            if int(details[2])>1000:
                result.add(transactions[j])
                
            if newd[details[0]]:
                
                for tran in newd[details[0]]:
                    name, time,amount,city = tuple(tran.split(\",\"))
                    if abs(int(details[1])-int(time))<=60 and details[3]!=city:
                        result.add(transactions[j])
                        result.add(tran)
            
            
            newd[details[0]].append(transactions[j])

        
        return result

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = set()
        trans_list = [[x for x in trans.split(\",\")] for trans in transactions]
        transactions_by_name = collections.defaultdict(list)
        for x in trans_list:
            transactions_by_name[x[0]].append(x[1:])
        res = []
        for name, values_list in transactions_by_name.items():
            for values in values_list:
                time, amount, city = values
                if int(amount) > 1000:
                    res.append(','.join([name, time, amount, city]))
                else:
                    for other_values in values_list:
                        otime, _, ocity = other_values
                        if ocity != city and abs(int(time) - int(otime)) <= 60:
                            res.append(','.join([name, time, amount, city]))
                            break
        return res
                

class Solution:
    def invalidTransactions(self, transactions):
        
        transactions.sort()
        n = len(transactions)
        
        result = set()
        for i in range(n):
            i_name, i_time, i_amount, i_city = transactions[i].split(',')
            
            if int(i_amount) > 1000:
                result.add(transactions[i])
                
            for j in range(i + 1, n):
                j_name, j_time, j_amount, j_city = transactions[j].split(',')
            
                if j_name != i_name:
                    break
                    
                if i_city != j_city and abs(int(i_time) - int(j_time)) <= 60:
                    result.add(transactions[i])
                    result.add(transactions[j])
                    
        return list(result)

from collections import defaultdict

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transactions.sort(key=lambda t: int(t.split(',')[1]))
        recent = defaultdict(lambda: [])
        result = set()
        for transaction in transactions:
            name, time, amount, city = self.parse(transaction)
            if amount > 1000:
                result |= {transaction}
            if name in recent:
                for recent_transaction in recent[name]:
                    _, recent_time, _, recent_city = self.parse(recent_transaction)
                    if time - recent_time <= 60 and recent_city != city: 
                        result |=  {recent_transaction, transaction}
            recent[name] += [transaction]
        return result
            
    def parse(self, transaction):
        name, time, amount, city = transaction.split(',')
        return name, int(time), int(amount), city


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        trans = []
        for k in range(len(transactions)):
            trans.append(tuple(transactions[k].split(',')))
        trans.sort(key = lambda x: x[0])
        
        print(trans)
        
        store, i = set(), 0
        while i < len(trans):
            j = i+1
            while j < len(trans) and trans[j][0] == trans[i][0]:
                if abs(int(trans[i][1]) - int(trans[j][1])) <= 60:
                    if trans[i][3] != trans[j][3]:
                        store.add(\",\".join(trans[i]))
                        store.add(\",\".join(trans[j]))
                j+=1
            if int(trans[i][2]) > 1000: store.add(\",\".join(trans[i]))
            i+=1
        return list(store)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
#         transaction invalid -> > $1000 or within 60 minutes and same name and diff city
        
#         loop thru the list 
#         for each item, split the string by comma
#         set dictionary with name for key
#         list of tuple for value with time, cost, location
        
#         loop thru dictionary
#         sort the list by time / 0 index 
            
        clean = {}
        results = set()
        
        for transaction in transactions:
            item = transaction.split(',')
            name, time, money, location = item
            if name not in clean:
                clean[name] = [(int(time), int(money), location)]
            else:
                clean[name].append((int(time), int(money), location))
        
        for person, info in clean.items():
            sorted_items = sorted(info)
            for idx in range(len(sorted_items)):
                for idx_2 in range(len(sorted_items)):
                    if (abs(sorted_items[idx_2][0] - sorted_items[idx][0]) <= 60) and (sorted_items[idx_2][2] != sorted_items[idx][2]) and (idx != idx_2): 
                        invalid_1 = [person, str(sorted_items[idx][0]), str(sorted_items[idx][1]), sorted_items[idx][2]]
                        invalid_2 = [person, str(sorted_items[idx_2][0]), str(sorted_items[idx_2][1]), sorted_items[idx_2][2]]
                        results.add(\",\".join(invalid_1))
                        results.add(\",\".join(invalid_2))
                
                cost = sorted_items[idx][1]
                if cost > 1000:
                    invalid = [person, str(sorted_items[idx][0]), str(sorted_items[idx][1]), sorted_items[idx][2]]
                    results.add(\",\".join(invalid))
        
        return list(results)
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:    return []
        # transactions = sorted(transactions)
        # print(transactions)
        res=set()
        names = defaultdict(list)
        time,amt,city=[],[],[]
        for i,ele in enumerate(transactions):
            s = ele.split(',')
            names[s[0]] += [(int(s[1]), int(s[2]), s[3], s[0])]
        for k,v in list(names.items()):
            v = sorted(v)
            for i,ele in enumerate(v):
                b,c,d,a = ele
                for j,ele1 in enumerate(v):
                    if i != j:
                        f,g,h,e = ele1
                        if (abs(b-f) <= 60) and (a == e) and (d != h):   
                            res.add(a+','+str(b)+','+str(c)+','+d)
                            res.add(e+','+str(f)+','+str(g)+','+h)
                if c > 1000:
                    res.add(a+','+str(b)+','+str(c)+','+d)
                        
                # if i>=1:
                #     f,g,h,e = v[i-1]
                #     if (abs(b-f) <= 60) and (a == e) and (d != h):   
                #         res.add(a+','+str(b)+','+str(c)+','+d)
                #         res.add(e+','+str(f)+','+str(g)+','+h)
                # if c > 1000:
                #     res.add(a+','+str(b)+','+str(c)+','+d)
                    
        return res



class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ret = set()
        name = []
        time = []
        amount = []
        city = []
        for trans in transactions:
            trans = trans.split(',')
            name.append(trans[0])
            time.append(int(trans[1]))
            amount.append(int(trans[2]))
            city.append(trans[3])
        for i in range(len(transactions)):
            if(amount[i] > 1000):
                ret.add(transactions[i])
            for j in range(i+1, len(transactions)):
                if(name[i] == name[j] and abs(time[i] - time[j]) <= 60 and city[i] != city[j]):
                    ret.add(transactions[i])
                    ret.add(transactions[j])
                    
                      
            
        return ret

        
            
            


class Transaction:
    def __init__(self, transaction):
        trans_details = transaction.split(\",\")
        self.name = trans_details[0]
        self.time = int(trans_details[1])
        self.amount = int(trans_details[2])
        self.city = trans_details[3]
        
    def findAnotherTrans(self, transactions):
        for transaction in transactions:
            curTransact = Transaction(transaction)
            if(curTransact.name==self.name and curTransact.city!=self.city and abs(curTransact.time - self.time)<=60):
                return True
        return False
    
    
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        final_ans = []
        for trans in transactions:
            curTransact = Transaction(trans)
            if(curTransact.amount>1000):
                final_ans.append(trans)
            else:
                if(curTransact.findAnotherTrans(transactions)):
                    final_ans.append(trans)
                
        return final_ans
    
            
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        result = []
        
        stock = {}
        for trans in transactions:
            name, time, amount, city = trans.split(\",\")
            time = int(time)
            flg = False
            if int(amount)>=1000:
                flg = True
            if name in stock:
                for btime, bcity, btrans in stock[name]:
                    if (btime+60>=time and time>=btime-60)and bcity!=city:
                        if btrans not in result:
                            result.append(btrans)
                        flg = True
            if flg:
                result.append(trans)
                
            if name not in stock:
                stock[name] = [(time, city, trans)]
            else:
                stock[name].append((time, city, trans))
        return result

class Solution:
    # > 1000
    # same name, different city, <= 60 min
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
#         loop through transactions 
#             if amount is greater >= 1000 add it to invalid set
#             have another loop, check every other transactions for invalid time
         
        # { invalidtransaction}
        # {
        #     alice: [\"transaction\",\"transaction\"]
        #     bob: [\"transaction\"]
        # }
        
        userTransactions = collections.defaultdict(list)
        invalidTransactions = set()
        
        for transaction in transactions:
            [name,time,amount,city] = transaction.split(\",\")
            
            if int(amount) > 1000: invalidTransactions.add(transaction)
            userTransactions[name].append(transaction)
            
        for name in userTransactions:
            userTrans = userTransactions[name]
            
            for i in range(len(userTrans)-1):
                for j in range(i+1,len(userTrans)):
                    [_,time,_,city] = userTrans[i].split(\",\")
                    [_,time2,_,city2] = userTrans[j].split(\",\")
                    
                    if abs(int(time)-int(time2)) <= 60 and city != city2:
                        invalidTransactions.add(userTrans[i])
                        invalidTransactions.add(userTrans[j])
                    
        return list(invalidTransactions)
            
                
        
        
        

class Solution:
    # 0) split each element of transactions on comma
    # 1) iterate through transactions and if amount > 1000 add to ans array and transactions.pop(i)
    # 2) create dict {name:[...(time, city)...]}    # sort by time
    # 3) iterate through transactions and if within 60 minutes and diff city then add to ans array
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        # 0)
        transactions = [string.split(',') for string in transactions]
        
        # 1)
        ans, length = set(), len(transactions)
        for i in range(length):
            if int(transactions[i][2]) > 1000:
                ans.add(','.join(transactions[i]))
        
        # 2)
        dct = {}
        for i in range(length):
            name, time, city = transactions[i][0], transactions[i][1], transactions[i][-1]
            if name in dct:
                dct[name].append( (time, city) )
                dct[name].sort()
            else:
                dct[name] = [(time, city)]
        
        # 3)
        for name,time,amt,city in transactions:
            for tme,cty in dct[name]:
                if abs(int(time)-int(tme)) <= 60 and city != cty:
                    ans.add(','.join([name,time,amt,city]))
        return list(ans)
        
        


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        # time order?
        # 30 60 90 how to assess?
        
        realTransactions = collections.defaultdict(list)
        for each in transactions:
            each = each.split(',')
            realTransactions[each[0]].append(tuple(each[1:]))
        
        res = []
        for name in realTransactions.keys(): # O(n) time
            realTransactions[name].sort(key = lambda x: int(x[0]))
            for i, trans in enumerate(realTransactions[name]):
                left = right = i
                time, amt, loc = trans
                if int(amt) > 1000:
                    res.append(\"{},{},{},{}\".format(name, time, amt, loc))
                    continue
                while left - 1 >= 0 and int(realTransactions[name][left - 1][0]) + 60 >= int(time):
                    left -= 1
                while right + 1 < len(realTransactions[name]) and int(realTransactions[name][right + 1][0]) - 60 <= int(time):
                    right += 1
                #print(left, right)
                for idx in range(left, right + 1):
                    if realTransactions[name][idx][2] != loc:
                        res.append(\"{},{},{},{}\".format(name, realTransactions[name][i][0], realTransactions[name][i][1], realTransactions[name][i][2]))
                        break

        return res
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ans = []
        length = len(transactions)
        if not length: return ans
        name,time,money,city = [],[],[],[]
        add = [1]*length
        for trans in transactions:
            tran = trans.split(',')
            name.append(tran[0])
            time.append(eval(tran[1]))
            money.append(eval(tran[2]))
            city.append(tran[3])
        for i in range(length):
            if money[i] > 1000:
                add[i] = False
            for j in range(i+1,length):
                if name[i] == name[j] and abs(time[i]-time[j])<= 60 and city[i]!=city[j]:
                    add[i] = False
                    add[j] = False
        for ind,val in enumerate(add):
            if not val:
                ans.append(transactions[ind])
        return ans

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:
            return []
        l=[i.split(\",\") for i in transactions]
        n=len(transactions)
        valid=[True]*n
        for i in range(n):
            if int(l[i][2])>1000:
                valid[i]=False
        for i in range(n):
            for j in range(i+1,n):
                if valid[i] or valid[j]:
                    name1,time1,city1=l[i][0],l[i][1],l[i][3]
                    name2,time2,city2=l[j][0],l[j][1],l[j][3]
                    if name1==name2 and city1!=city2 and abs(int(time1)-int(time2))<=60:
                        valid[i],valid[j]=False,False
        return [transactions[i] for i in range(n) if not valid[i]]

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ans = []
        length = len(transactions)
        if not length: return ans
        name,time,money,city = [],[],[],[]
        add = [1]*length
        for trans in transactions:
            tran = trans.split(',')
            name.append(tran[0])
            time.append(eval(tran[1]))
            money.append(eval(tran[2]))
            city.append(tran[3])
        for i in range(length):
            if money[i] > 1000:
                add[i] = False
            for j in range(i+1,length):
                if name[i] == name[j] and abs(time[i]-time[j])<= 60 and city[i]!=city[j]:
                    add[i] = False
                    add[j] = False
        for ind,val in enumerate(add):
            if not val:
                ans.append(transactions[ind])
        return ans           


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        t = transactions.copy()
        t.sort()
        invalid = set()
        name = \"\"
        times = {}
        for transaction in t:
            vals = transaction.split(',')
            if int(vals[2]) > 1000:
                invalid.add(transaction)
            if vals[0] != name:
                name = vals[0]
                times[name] = list()
            else:
                for seen in times[name]:
                    vs = seen.split(',')
                    if vs[3] != vals[3] and abs(int(vs[1]) - int(vals[1])) <= 60:
                        invalid.add(seen)
                        invalid.add(transaction)
            times[name].append(transaction)
        
        return list(invalid)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        def reunite(temp):
            return temp[0] + \",\" + str(temp[1]) + \",\" + str(temp[2]) + \",\" + temp[3]
        new_transactions = []
        for i in range(len(transactions)):
            name, time, amount, city = transactions[i].split(\",\")
            new_transactions.append([name,int(time),int(amount),city])
            
        new_transactions.sort(key = lambda x: x[1])
        result = []
        for i in range(len(new_transactions)):
            if int(new_transactions[i][2]) > 1000:
                result.append(reunite(new_transactions[i]))
            
            for j in range(i,len(new_transactions)):
                if int(new_transactions[j][1]) - int(new_transactions[i][1]) <= 60 and new_transactions[j][3] != new_transactions[i][3] and new_transactions[j][0] == new_transactions[i][0]:
                    result.append(reunite(new_transactions[j]))
                    result.append(reunite(new_transactions[i]))
                elif int(new_transactions[j][1]) - int(new_transactions[i][1]) > 60:
                    break
        result.sort()
        new_result = [result[0]]
        for i in range(len(result)-1):
            if result[i] != result[i+1]:
                new_result.append(result[i+1])
                #print(new_result)
                
                
        return new_result
                
            
        

from collections import defaultdict
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        dic = defaultdict(list)
        res = set()
        for i in transactions: 
            i = i.split(',')
            if int(i[2]) > 1000:
                res.add(','.join(i))
            if i[0] in dic: #we only care about time and place
                    for j in dic[i[0]]:
                        j = j.split(',')
                        if i[3] != j[3] and abs(int(i[1]) - int(j[1])) <= 60:
                            res.add(','.join(i))
                            res.add(','.join(j))
            dic[i[0]].append(','.join(i))
        print(dic)
        return list(res)


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        tf_arr = [True for _ in range(len(transactions))]
        new_transactions = []
        for x in transactions:
            x = x.split(',')
            x[1] = int(x[1])
            x[2] = int(x[2])  
            new_transactions.append(x)
        def check(transaction, i, arr):
            if transaction[2]>1000:
                tf_arr[i] = False
            for j,e in enumerate(arr[i+1:]):
                if transaction[0] == e[0] and  transaction[3] != e[3] and abs(transaction[1] - e[1])<=60: 
                    tf_arr[i] = False
                    tf_arr[i+j+1] = False
        for i,t in enumerate(new_transactions):
            check(t,i,new_transactions)
        output = []
        for i,truth in enumerate(tf_arr):
            if not truth:
                output.append(transactions[i])
        return output

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ans=[]
        n=len(transactions)
        rank=[True]*n
        name=[]
        time=[]
        amount=[]
        city=[]
        for t in transactions:
            num=t.split(',')
            name.append(num[0])
            time.append(num[1])
            amount.append(num[2])
            city.append(num[3])
        
        for i in range(n):
            if int(amount[i])>1000:
                rank[i]=False
            for j in  range(i+1,n):
                if name[i]==name[j] and abs(int(time[i])-int(time[j]))<=60 and city[i]!=city[j]:
                    rank[i]=False
                    rank[j]=False
        for t in range(n):
            if not rank[t]:
                ans.append(transactions[t])
        
        return ans
        


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        \"\"\"
        There are two ways for transaction to be invalid.
        1. Exceeds 1000. -> iterate and put each into a bin
        2. Same name in a different city within a 60 second window
        \"\"\"
        invalid_transactions = set()
        trans_by_name = {}
        # For the trans_by_name, add by name, then by city
        # As a new transaction arrives, check to see if the difference 
        #   between it and the transactions under a different name which 
        #   do not have the same city name. If not, add it to the table.
        #   If so, also add it to the invalid_transactions list
        for trans in transactions:
            tname, tmin, tamt, tcity = trans.split(',')
            if int(tamt) > 1000:
                invalid_transactions.add(trans)
            if tname in trans_by_name:
                for city, time, amt in trans_by_name[tname]:
                    if tcity != city and abs(int(tmin) - int(time)) <= 60:
                        print(f'{tname} {time} {city} {amt}')
                        invalid_transactions.add(trans)
                        invalid_transactions.add(f'{tname},{time},{amt},{city}')
            if tname not in trans_by_name:
                trans_by_name[tname] = set()
            trans_by_name[tname].add((tcity, tmin, tamt))
        return invalid_transactions
        

class Solution:
    
    
    
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
#         def asPerTime(string):
#             return string.split(',')[1]
            
        
#         transactions.sort(key=asPerTime)
        
        #dictionary
        personDict = dict()
        
        #outputList
        outSet = set()
        
        for transaction in transactions:
            name, time, amount, city = transaction.split(',')
            if int(amount) > 1000:
                outSet.add(transaction)
                
            if name in personDict:
                cityDict = personDict[name]
                cityDict[city].append((time, amount))
                
                for key in cityDict:
                    if key != city:
                        for pair in cityDict[key]:
                            prevTime, prevAmount = pair
                            timeDiff = abs(int(time) - int(prevTime)) 
                            if timeDiff <= 60:
                                outSet.add(transaction)
                                outSet.add(','.join([name, prevTime, prevAmount, key]))
            
            
            else:
                personDict[name] = defaultdict(list)
                personDict[name][city].append((time, amount)) 
        
        
        return outSet
        
        
        '''
        sort the transaction list as per the time
        
        a dictionary where key is the name of the person and the the value is a dictionary where the key is the city and the value is time and amount        
        
        
        
        iterate over the transactions:
            if the amount is greater than 1000:
                add it to the list
            
            if that same person has done a transaction before
                are the cities different:
                    get the time of the latest transaction
                    if difference is <60:
                        add the latest transaction as well as this transaction
                        update the latest transaction with this transaction info
                        continue
                        
                 
        '''
        
        


class Transaction:
    
    def __init__(self, s):
        params = s.split(',')
        
        self.name, self.time, self.amount, self.city = params[0], int(params[1]), int(params[2]), params[3]
        
    def __str__(self):
        return ','.join([self.name, str(self.time), str(self.amount), self.city])
    
    

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        transactions = [Transaction(t) for t in transactions]
        
        transactions.sort(key = lambda t: t.time)
        
        #map name to transaction idx
        trans_idxs = defaultdict(list)
        
        for i, t in enumerate(transactions):
            trans_idxs[t.name].append(i)
            
        invalid = []
        
        for name, idxs in list(trans_idxs.items()):
            left = right = 0
            
            for trans_idx in idxs:
                t = transactions[trans_idx]
                if t.amount > 1000:
                    invalid.append(str(t))
                    continue
                
                while left <= len(idxs) - 2 and transactions[idxs[left]].time < t.time - 60:
                    left += 1
                    
                right = left
                while right <= len(idxs) - 2 and transactions[idxs[right+1]].time < t.time + 60:
                    right += 1
                
                for j in range(left, right+1):
                    if transactions[idxs[j]].city != t.city:
                        invalid.append(str(t))
                        break
                        
        return invalid
                    
                


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:    return []
        res=set()
        names = defaultdict(list)
        time,amt,city=[],[],[]
        for i,ele in enumerate(transactions):
            s = ele.split(',')
            names[s[0]] += [(int(s[1]), int(s[2]), s[3], s[0])]
            
        for k,v in list(names.items()):

            for i,ele in enumerate(v):
                b,c,d,a = ele
                for j in range(0, len(v)):
                    if i != j:
                        f,g,h,e = v[j]
                        if (abs(b-f) <= 60) and (a == e) and (d != h):   
                            res.add(a+','+str(b)+','+str(c)+','+d)
                            res.add(e+','+str(f)+','+str(g)+','+h)
                    if c > 1000:
                        res.add(a+','+str(b)+','+str(c)+','+d)
                    
        return res



class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:    return []
        res=set()
        names = defaultdict(list)
        time,amt,city=[],[],[]
        for i,ele in enumerate(transactions):
            s = ele.split(',')
            names[s[0]] += [(int(s[1]), int(s[2]), s[3], s[0])]
            
        for k,v in list(names.items()):

            for i,ele in enumerate(v):
                b,c,d,a = ele
                for j in range(0, len(v)):
                    if i != j:
                        f,g,h,e = v[j]
                        if (abs(b-f) <= 60) and (a == e) and (d != h):   
                            res.add(a+','+str(b)+','+str(c)+','+d)
                            res.add(e+','+str(f)+','+str(g)+','+h)
                    if c > 1000:
                        res.add(a+','+str(b)+','+str(c)+','+d)
                        
                # if i>=1:
                #     e,f,g,h = v[i-1].split(',')
                #     if (abs(int(b)-int(f)) <= 60) and (a == e) and (d != h):   
                #         res.add(a+','+str(b)+','+str(c)+','+d)
                #         res.add(e+','+str(f)+','+str(g)+','+h)
                # if int(c) > 1000:
                #     res.add(a+','+str(b)+','+str(c)+','+d)
                    
        return res



class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ans = []
        length = len(transactions)
        if not length: return ans
        name,time,money,city = [],[],[],[]
        add = [1]*length
        for trans in transactions:
            tran = trans.split(',')
            name.append(tran[0])
            time.append(eval(tran[1]))
            money.append(eval(tran[2]))
            city.append(tran[3])
        for i in range(length):
            if money[i] > 1000:
                add[i] = False
            for j in range(i+1,length):
                if name[i] == name[j] and abs(time[i]-time[j])<= 60 and city[i]!=city[j]:
                    add[i] = False
                    add[j] = False
        for ind,val in enumerate(add):
            if not val:
                ans.append(transactions[ind])
        
        
        return ans

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ans = []
        length = len(transactions)
        if not length: return ans
        name,time,money,city = [],[],[],[]
        add = [1]*length
        for trans in transactions:
            tran = trans.split(',')
            name.append(tran[0])
            time.append(eval(tran[1]))
            money.append(eval(tran[2]))
            city.append(tran[3])
        for i in range(length):
            if money[i] > 1000:
                add[i] = False
            for j in range(i+1,length):
                if name[i] == name[j] and abs(time[i]-time[j])<= 60 and city[i]!=city[j]:
                    add[i] = False
                    add[j] = False
        for ind,val in enumerate(add):
            if not val:
                ans.append(transactions[ind])
                
                
        return ans

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        data_by_time = {}
        for data in transactions:
            orig_data = data
            data = data.split(\",\")

            transaction = {\"name\": data[0], \"amount\": int(data[2]), \"city\": data[3], \"orig\": orig_data}
            if int(data[1]) not in data_by_time:
                data_by_time[int(data[1])] = [transaction]
            else:
                data_by_time[int(data[1])].append(transaction)
        result = set()
        times = sorted(data_by_time.keys())
        for time in times:
            for trans in data_by_time[time]:
                if trans[\"amount\"] > 1000:
                    result.add(trans[\"orig\"])
    
        for (t_trans, trans_list) in data_by_time.items():
            for trans in trans_list:
                for time in times:
                    if abs(t_trans - time) <= 60:
                        for other_trans in data_by_time[time]:
                            if other_trans[\"name\"] == trans[\"name\"] and other_trans[\"city\"] != trans[\"city\"]:
                                result.add(other_trans[\"orig\"])
                                #result.add(trans[\"orig\"])
                    
        return list(result)
                    
        
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        data_by_time = {}
        for data in transactions:
            orig_data = data
            data = data.split(\",\")

            transaction = {\"name\": data[0], \"amount\": int(data[2]), \"city\": data[3], \"orig\": orig_data}
            if int(data[1]) not in data_by_time:
                data_by_time[int(data[1])] = [transaction]
            else:
                data_by_time[int(data[1])].append(transaction)
        result = set()
        times = sorted(data_by_time.keys())
        for time in times:
            for trans in data_by_time[time]:
                if trans[\"amount\"] > 1000:
                    result.add(trans[\"orig\"])
    
        for (t_trans, trans_list) in data_by_time.items():
            for trans in trans_list:
                for time in times:
                    if abs(t_trans - time) <= 60:
                        for other_trans in data_by_time[time]:
                            if other_trans[\"name\"] == trans[\"name\"] and other_trans[\"city\"] != trans[\"city\"]:
                                result.add(other_trans[\"orig\"])
                                result.add(trans[\"orig\"])
                    
        #for i in range(len(times) - 1):
        #    if times[i+1] - times[i] <= 60:
        #        seen_names = {}
        #        for transaction in data_by_time[times[i]]:
        #            seen_names[transaction[\"name\"]] = transaction
        #        for transaction in data_by_time[times[i+1]]:
        #            if transaction[\"name\"] in seen_names:
        #                if transaction[\"city\"] != seen_names[transaction[\"name\"]][\"city\"]:
        #                    result.add(transaction[\"orig\"])
        #                    result.add(seen_names[transaction[\"name\"]][\"orig\"])
        #                    #result.update([seen_names[x][\"orig\"] for x in seen_names[transaction[\"name\"]]])
        return list(result)
                    
        
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        data_by_time = {}
        for data in transactions:
            orig_data = data
            data = data.split(\",\")

            transaction = {\"name\": data[0], \"amount\": int(data[2]), \"city\": data[3], \"orig\": orig_data}
            if int(data[1]) not in data_by_time:
                data_by_time[int(data[1])] = [transaction]
            else:
                data_by_time[int(data[1])].append(transaction)
        result = set()
        times = sorted(data_by_time.keys())
        for time in times:
            for trans in data_by_time[time]:
                if trans[\"amount\"] > 1000:
                    result.add(trans[\"orig\"])
    
        for (t_trans, trans_list) in data_by_time.items():
            for trans in trans_list:
                for time in times:
                    if abs(t_trans - time) <= 60:
                        for other_trans in data_by_time[time]:
                            if other_trans[\"name\"] == trans[\"name\"] and other_trans[\"city\"] != trans[\"city\"]:
                                #result.add(other_trans[\"orig\"])
                                result.add(trans[\"orig\"])
                    
        return list(result)
                    
        
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transactions = [ x.split(\",\") for x in transactions]
        transactions =[ [x[0],int(x[1]),int(x[2]),x[3]] for x in transactions]
        transactions.sort(key=lambda x:x[1])
        res=set()
        n=len(transactions)
        for i in range(n):
            nam1,tim1,amt1,city1=transactions[i]
            
            if int(amt1)>1000:
                res.add(f\"{nam1},{tim1},{amt1},{city1}\")
            for j in range(i+1,n):
                nam2,tim2,amt2,city2=transactions[j]
                if nam1==nam2 and int(tim2)-int(tim1)<=60 and city1!=city2:
                    res.add(f\"{nam1},{tim1},{amt1},{city1}\")
                    res.add(f\"{nam2},{tim2},{amt2},{city2}\")
        return list(res)
                
                
                
            
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        import collections
        if not transactions:
            return []
        
        memo = collections.defaultdict(list)    #create a dictionary to keep track of previous transaction 
        invalid_tran = set()                    #to store invalid transaction / I use set to avoid duplication
        for i,transaction  in enumerate (transactions):
            
            name, time, amount, city = (int(i) if i.isnumeric() else i for i in transaction.split(','))
            
            if amount > 1000:                   #if the amount is greater than 1000 add it to the invalid_tran
                invalid_tran.add(transaction)               
                 
            if name in memo:                    # if there is any other previous transaction done by similar person , check it from the memo
                for tran in memo[name]:         # bring all previous transaction done by similar person (iterate over the memo)
                    _, prev_time, _, prev_city =(int(i) if i.isnumeric() else i for i in  tran.split(','))
                    if abs(time-prev_time) <= 60 and prev_city != city:  #check if the absolute time difference is less than 60 and the city is the same
                        invalid_tran.add(tran) 
                        invalid_tran.add(transaction)                    
            
            memo[name].append(transaction)  # add the transaction to the dictionary (memo) - always keep track of previous transaction 
        return invalid_tran


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:
            return []
        dic=defaultdict(list)
        invalid=set()
        for i in range(len(transactions)):
            name, time, amount, city=(int(i) if i.isnumeric() else i for i in transactions[i].split(','))
            if amount>1000:
                invalid.add(transactions[i])
            if name in dic:
                for tran in dic[name]:
                    _, prev_time, _, prev_city=(int(i) if i.isnumeric() else i for i in tran.split(','))
                    if prev_city!=city and abs(prev_time-time)<=60:
                        invalid.add(tran)
                        invalid.add(transactions[i])
            dic[name].append(transactions[i])
        return list(invalid)
                    
                    
            
        
        
        
        
        
                    
            
                    
                    
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
#         import collections
#         if not transactions:
#             return []
        
#         memo = collections.defaultdict(list)    #create a dictionary to keep track of previous transaction 
#         invalid_tran = set()                    #to store invalid transaction / I use set to avoid duplication
#         for i in range(len(transactions)):
            
#             name, time, amount, city = (int(i) if i.isnumeric() else i for i in transactions[i].split(','))
            
#             if amount > 1000:                   #if the amount is greater than 1000 add it to the invalid_tran
#                 invalid_tran.add(transactions[i])               
                 
#             if name in memo:                    # if there is any other previous transaction done by similar person , check it from the memo
#                 for tran in memo[name]:         # bring all previous transaction done by similar person (iterate over the memo)
#                     _, prev_time, _, prev_city =(int(i) if i.isnumeric() else i for i in  tran.split(','))
#                     if abs(time-prev_time) <= 60 and prev_city != city:  #check if the absolute time difference is less than 60 and the city is the same
#                         invalid_tran.add(tran) 
#                         invalid_tran.add(transactions[i])                    
            
#             memo[name].append(transactions[i])  # add the transaction to the dictionary (memo) - always keep track of previous transaction 
#         return invalid_tran


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        def giddy(item):
            return item.split(',')
        
        result = set()
        seen = collections.defaultdict(collections.deque)
        transactions = list(map(giddy, transactions))
        transactions.sort(key=lambda x: int(x[1]))
        # print(transactions)
        for i in range(len(transactions)):
            val = transactions[i]
            if int(val[2])>1000:
                result.add(','.join(val))
            if val[0] in seen:
                # print(seen)
                for x in seen[val[0]]:
                    comp = transactions[x]
                    # print(comp)
                    if abs(int(comp[1])-int(val[1]))<=60 and comp[3] != val[3]:
                        result.add(','.join(val))
                        result.add(','.join(comp))
            seen[val[0]].append(i)
            # print(seen[val[0]], 'before pop')
            while abs(int(transactions[seen[val[0]][0]][1])-int(val[1]))>60:
                seen[val[0]].popleft()
                # print(seen[val[0]], 'after pop')
        return result

from collections import defaultdict

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        if not transactions:
            return []
        
        d = defaultdict(list)
        result = set()
        
        for i in range(len(transactions)):
            name, time, amount, city = (int(i) if i.isnumeric() else i for i in transactions[i].split(\",\"))
            
            if amount > 1000:
                result.add(transactions[i])
                
            if name in d:
                for tran in d[name]:
                    _, prev_time, _, prev_city = (int(i) if i.isnumeric() else i for i in tran.split(\",\"))
                    if abs(time - prev_time) <= 60 and prev_city != city:
                        result.add(tran)
                        result.add(transactions[i])
            
            d[name].append(transactions[i])
        
        return result


class Solution(object):
    def invalidTransactions(self, transactions):
        \"\"\"
        :type transactions: List[str]
        :rtype: List[str]
        
        memo = dictionary --> create a dictionary to keep track of previous transaction 
        invalid_tran = set --> to store invalid transaction / I use set to avoid duplication 
        
        Iterate over transactions:
            -> if the amount is greater than 1000 add it to the invalid_tran
            -> if there is any other previous transaction done by similar person , check it from the memo
                    -> bring all previous transaction done by similar person (iterate over the memo)
                            -> check if the absolute time difference is less than 60 and the city is the same 
                                    -> if that is true add it to the invalid transaction 
            -> add the transaction to the dictionary (memo) - always keep track of previous transaction 
        \"\"\"
        import collections
        if not transactions:
            return []
        
        memo = collections.defaultdict(list)    #create a dictionary to keep track of previous transaction 
        invalid_tran = set()                    #to store invalid transaction / I use set to avoid duplication
        for i,transaction  in enumerate (transactions):
            
            name, time, amount, city = (int(i) if i.isnumeric() else i for i in transaction.split(','))
            
            if amount > 1000:                   #if the amount is greater than 1000 add it to the invalid_tran
                invalid_tran.add(transaction)               
                 
            if name in memo:                    # if there is any other previous transaction done by similar person , check it from the memo
                for tran in memo[name]:         # bring all previous transaction done by similar person (iterate over the memo)
                    _, prev_time, _, prev_city =(int(i) if i.isnumeric() else i for i in  tran.split(','))
                    if abs(time-prev_time) <= 60 and prev_city != city:  #check if the absolute time difference is less than 60 and the city is the same
                        invalid_tran.add(tran) 
                        invalid_tran.add(transaction)                    
            
            memo[name].append(transaction)  # add the transaction to the dictionary (memo) - always keep track of previous transaction 
        return invalid_tran

import collections
class Solution(object):
    def invalidTransactions(self, transactions):
        if not transactions:
            return []
        
        memo = collections.defaultdict(list)    #create a dictionary to keep track of previous transaction 
        invalid_tran = set()                    #to store invalid transaction / I use set to avoid duplication
        for i,transaction  in enumerate (transactions):
            
            name, time, amount, city = (int(i) if i.isnumeric() else i for i in transaction.split(','))
            
            if amount > 1000:                   #if the amount is greater than 1000 add it to the invalid_tran
                invalid_tran.add(transaction)               
                 
            if name in memo:                    # if there is any other previous transaction done by similar person , check it from the memo
                for tran in memo[name]:         # bring all previous transaction done by similar person (iterate over the memo)
                    _, prev_time, _, prev_city =(int(i) if i.isnumeric() else i for i in  tran.split(','))
                    if abs(time-prev_time) <= 60 and prev_city != city:  #check if the absolute time difference is less than 60 and the city is the same
                        invalid_tran.add(tran) 
                        invalid_tran.add(transaction)                    
            
            memo[name].append(transaction)  # add the transaction to the dictionary (memo) - always keep track of previous transaction 
        return invalid_tran


import collections
class Solution(object):
    def invalidTransactions(self, transactions):
        if not transactions:
            return []
        
#        memo = collections.defaultdict(list)    #create a dictionary to keep track of previous transaction 
        memo = {}
        invalid_tran = set()                    #to store invalid transaction / I use set to avoid duplication
        for i,transaction  in enumerate (transactions):
            
            name, time, amount, city = (int(i) if i.isnumeric() else i for i in transaction.split(','))
            
            if amount > 1000:                   #if the amount is greater than 1000 add it to the invalid_tran
                invalid_tran.add(transaction)               
                 
            if name in memo:                    # if there is any other previous transaction done by similar person , check it from the memo
                for tran in memo[name]:         # bring all previous transaction done by similar person (iterate over the memo)
                    _, prev_time, _, prev_city =(int(i) if i.isnumeric() else i for i in  tran.split(','))
                    if abs(time-prev_time) <= 60 and prev_city != city:  #check if the absolute time difference is less than 60 and the city is the same
                        invalid_tran.add(tran) 
                        invalid_tran.add(transaction)                    
            if name not in memo:
                memo[name] = []
            memo[name].append(transaction)  # add the transaction to the dictionary (memo) - always keep track of previous transaction 
        return invalid_tran


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        
        transactionsByName = {}
        invalidTransactions = set()
        for t in transactions:
            name, time, amount, city = t.split(\",\")
            if int(amount) > 1000:
                
                invalidTransactions.add(t)
                
            item = {
                \"name\": name,
                \"time\": time,
                \"amount\": amount,
                \"city\": city,
            }
            
            if name not in transactionsByName:
                transactionsByName[name] = [item]
            else:
                transactionsByName[name].append(item)
        
        for key, values in transactionsByName.items():
            # values.sort(key = lambda v: v[\"time\"]) 
            for i in range(len(values)):
                for k in range(len(values)):
                    if values[i][\"city\"] != values[k][\"city\"] and abs(int(values[i][\"time\"]) - int(values[k][\"time\"])) <=60:
                        invalidTransactions.add(\",\".join(values[i].values()))
                        invalidTransactions.add(\",\".join(values[k].values()))

        return list(invalidTransactions)
        # same name -> go through list 
        # sort by time
        # if each one is next to other, put first into list if last, put that to list too
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:
            return []
        dic=defaultdict(list)
        invalid=set()
        for i in range(len(transactions)):
            name, time, amount, city=(int(i) if i.isnumeric() else i for i in transactions[i].split(','))
            if amount>1000:
                invalid.add(transactions[i])
            if name in dic:
                for tran in dic[name]:
                    _, prev_time, _, prev_city=(int(i) if i.isnumeric() else i for i in tran.split(','))
                    if prev_city!=city and abs(prev_time-time)<=60:
                        invalid.add(transactions[i])
                        invalid.add(tran)
            dic[name].append(transactions[i])
        return invalid
                    
            
                    
                    
            
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
#         import collections
#         if not transactions:
#             return []
        
#         memo = collections.defaultdict(list)    #create a dictionary to keep track of previous transaction 
#         invalid_tran = set()                    #to store invalid transaction / I use set to avoid duplication
#         for i in range(len(transactions)):
            
#             name, time, amount, city = (int(i) if i.isnumeric() else i for i in transactions[i].split(','))
            
#             if amount > 1000:                   #if the amount is greater than 1000 add it to the invalid_tran
#                 invalid_tran.add(transactions[i])               
                 
#             if name in memo:                    # if there is any other previous transaction done by similar person , check it from the memo
#                 for tran in memo[name]:         # bring all previous transaction done by similar person (iterate over the memo)
#                     _, prev_time, _, prev_city =(int(i) if i.isnumeric() else i for i in  tran.split(','))
#                     if abs(time-prev_time) <= 60 and prev_city != city:  #check if the absolute time difference is less than 60 and the city is the same
#                         invalid_tran.add(tran) 
#                         invalid_tran.add(transactions[i])                    
            
#             memo[name].append(transactions[i])  # add the transaction to the dictionary (memo) - always keep track of previous transaction 
#         return invalid_tran


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

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        def formatRes(t):
            return \"{},{},{},{}\".format(t.name, t.time, t.amount, t.city)
        l = []
        res = set()
        for transaction in transactions:
            name, time, amount, city = transaction.split(\",\")
            l.append(Transaction(name, int(time), int(amount), city))
        l.sort(key=lambda t: t.time)
        
        for i in range(len(l)):
            t1 = l[i]
            if t1.amount > 1000:
                res.add(formatRes(t1))
            for j in range(i+1, len(l)):
                t2 = l[j]
                if t1.name == t2.name and t2.time-t1.time <= 60 and t2.city != t1.city:
                    res.add(formatRes(t1))
                    res.add(formatRes(t2))
        res = list(res)
        return res

from collections import defaultdict
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        if not transactions:
            return []
        previous = defaultdict(list)
        ans = set()
        
        for transaction in transactions:
            
            
            name, time, amount, city = (int(i) if i.isnumeric() else i for i in transaction.split(','))
            
            if amount > 1000:
                ans.add(transaction)
                
            for tran in previous[name]:
                _, prev_time, _, prev_city = (int(i) if i.isnumeric() else i for i in tran.split(','))
                
                if abs(time - prev_time) <= 60 and city != prev_city:
                    ans.add(tran)
                    ans.add(transaction)
            previous[name].append(transaction)
        return ans
                
                                            


class Solution:
    def invalidTransactions(self, arr: List[str]) -> List[str]:
        b = [0]*len(arr)
        a = [0]*len(arr)
        c = []
        for i in range(len(arr)):
            b[i] = arr[i].split(\",\")
            if int(b[i][2]) > 1000:
                a[i] = 1
        for i in range(len(arr)):
            for j in range(i+1, len(arr)):
                if b[i][0] == b[j][0] and b[i][3] != b[j][3]:
                    if abs(int(b[i][1]) - int(b[j][1])) <= 60:
                        a[i] = a[j] = 1
        for i in range(len(arr)):
            if a[i] == 1:
                c.append(arr[i])
        return(c)
        

from collections import defaultdict
class Transaction:
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city
    
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = []
        trans_index = defaultdict(list)
        trans = []
        for t in transactions:
            name, time, amount, city = t.split(',')
            trans.append(Transaction(name, time, amount, city))
        trans.sort(key = lambda x: x.time)
        
        s = set()
        for i in range(len(trans)):
            t1 = trans[i]
            if t1.amount > 1000:
                s.add(\"{},{},{},{}\".format(t1.name, t1.time, t1.amount, t1.city))
            for j in range(i + 1, len(trans)):
                t2 = trans[j]
                if t2.name == t1.name and t2.time - t1.time <= 60 and t1.city != t2.city:
                    s.add(\"{},{},{},{}\".format(t1.name, t1.time, t1.amount, t1.city))
                    s.add(\"{},{},{},{}\".format(t2.name, t2.time, t2.amount, t2.city))
        return list(s)
            
        
            
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        splits = [t.split(',') for t in transactions]
        lists = {}
        res = set()
        for time, p, v, loc, t in sorted([[int(sp[1]),sp[0],int(sp[2]),sp[3], t] for sp, t in zip(splits, transactions)]):
            if v>1000:
                res.add(t)

            tk = time%61
            if p not in lists:
                lists[p] = [None]*61
            
            lst = lists[p]
            for i in range(61):
                if lst[i] and abs(lst[i][0]-time)<=60 and lst[i][1]!=loc:
                    res.add(t)
                    res.add(lists[p][i][2])

            lst[tk] = [time, loc, t]

        return res
            


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transactions = [ x.split(\",\") for x in transactions]
        transactions =[ [x[0],int(x[1]),int(x[2]),x[3]] for x in transactions]
        transactions.sort(key=lambda x:x[1])
        #print (transactions)
        res=set()
        n=len(transactions)
        for i in range(n):
            nam1,tim1,amt1,city1=transactions[i]
            
            if int(amt1)>1000:
                res.add(f\"{nam1},{tim1},{amt1},{city1}\")
            for j in range(i+1,n):
                nam2,tim2,amt2,city2=transactions[j]
                if nam1==nam2 and int(tim2)-int(tim1)<=60 and city1!=city2:
                    print (nam1,tim1,amt1,city1, \"   \",nam2,tim2,amt2,city2)
                    res.add(f\"{nam1},{tim1},{amt1},{city1}\")
                    res.add(f\"{nam2},{tim2},{amt2},{city2}\")
        return list(res)
                
                
                
            
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        records = []
        for transaction in transactions:
            name, time, amount, city = transaction.split(\",\")
            records.append((name, int(time), int(amount), city, transaction))
        answer = set()
        for record in records:
            if record[2] > 1000:
                answer.add(record[4])
                continue
            for other in records:
                if record[0] == other[0] and record[3] != other[3] and abs(record[1] - other[1]) <= 60:
                    answer.add(record[4])
                    answer.add(other[4])
        return list(answer)
            

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

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        transact = []
        for t in transactions:
            t = t.split(',')
            obj = Transactions(t[0], int(t[1]), int(t[2]), t[3])
            transact.append(obj)
        transact.sort(key=lambda t: t.time)
        invalid = set() 
        for i in range(len(transact)):
            first = transact[i]
            if first.amount > 1000:
                invalid.add(self.returnString(first))
            for j in range(i+1, len(transact)):
                second = transact[j]
                if first.name == second.name and first.city != second.city and second.time - first.time <= 60:
                    invalid.add(self.returnString(first))
                    invalid.add(self.returnString(second))
                    
        return list(invalid)
    
    def returnString(self, first):
        return first.name + ',' + str(first.time) + ',' + str(first.amount) + ',' + first.city


class Transaction: 
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city
        
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        # convert each into object Transaction 
        for i in range(len(transactions)): 
            transact = transactions[i].split(',')
            transactions[i] = Transaction(transact[0], transact[1], transact[2], transact[3])
    
        invalid = set()
        def sortByTime(x):
            return x.time
        transactions.sort(key=sortByTime)
        
        for i, t in enumerate(transactions): 
            if t.amount > 1000: 
                invalid.add(self.toString(t))
            for j in range(i+1, len(transactions)):
                s = transactions[j]
                if t.name == s.name and t.city != s.city and s.time - t.time <= 60:
                    invalid.add(self.toString(s))
                    invalid.add(self.toString(t))
        return invalid
                
                
    def toString(self, s):
        return ('%s,%d,%d,%s' % (s.name, s.time, s.amount, s.city))
        
        


class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        invalid = set()
        trans = [i.split(\",\") for i in transactions]
        for i in range(len(transactions)):
            if int(trans[i][2]) > 1000:
                invalid.add(transactions[i])
            for j in range (i, len(transactions)):
                if trans[i][0] == trans[j][0] and trans[i][3] != trans[j][3] and abs(int(trans[i][1]) - int(trans[j][1])) <= 60:
                    invalid.add(transactions[i])
                    invalid.add(transactions[j])
        return list(invalid)

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        # brute force
        invalid = set()
        arr = [trans.split(',') for trans in transactions] 
        arr.sort(key = lambda t: int(t[1]))
        print(arr)
        for i in range(len(arr)):
            if int(arr[i][2]) > 1000: invalid.add(','.join(arr[i]))
            for j in range(i, len(transactions)):
                if arr[j][0] == arr[i][0] and int(arr[j][1]) - int(arr[i][1]) <= 60 and arr[i][3] != arr[j][3]:
                    print(\"together: \", ','.join(arr[j]), ','.join(arr[i]))
                    invalid.add(','.join(arr[j]))
                    invalid.add(','.join(arr[i]))
        
        return invalid
            

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        ts = []
        for t in transactions:
            name, stamp, amount, city = t.split(\",\")
            ts.append([name, int(stamp), int(amount), city, t])
        
        s = set()
        
        for t in ts:
            if t[2] > 1000: s.add(t[4])
            for v in ts:
                if t[0] == v[0] and abs(t[1] - v[1]) <= 60 and t[3] != v[3]: s.add(v[4])
    
        return list(s)
        
        
        

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        track = [] # (time, city, name)
        ret = set()
        
        for t in transactions:
            name, time, amt, city = t.split(\",\")
            time = int(time)
            if int(amt) > 1000:
                ret.add(t)
                track.append((time, city, name, t))

            # print(track, t)
            for i in range(0, len(track)):
                cmp = track[i]
                if abs(cmp[0] - time) <= 60 and cmp[1] != city and cmp[2] == name:
                    ret.add(t)
                    ret.add(cmp[3])
            
            track.append((time, city, name, t))
        return ret