# 1169. Invalid Transactions¶

• Time: $O(n^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 struct Trans { string name; int time; int amount; string city; }; class Solution { public: vector invalidTransactions(vector& transactions) { vector ans; unordered_map> nameToTranses; for (const string& t : transactions) { const Trans trans = getTrans(t); nameToTranses[trans.name].push_back(trans); } for (const string& t : transactions) { const Trans currTrans = getTrans(t); if (currTrans.amount > 1000) { ans.push_back(t); } else if (const auto it = nameToTranses.find(currTrans.name); it != nameToTranses.cend()) { // Iterate through all the transactions with the same name, check if // they're within 60 minutes in a different city. for (Trans trans : it->second) if (abs(trans.time - currTrans.time) <= 60 && trans.city != currTrans.city) { ans.push_back(t); break; } } } return ans; } private: Trans getTrans(const string& t) { istringstream iss(t); vector s(4, ""); for (int i = 0; getline(iss, s[i++], ',');) ; return {s[0], stoi(s[1]), stoi(s[2]), s[3]}; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 class Trans { public String name; public int time; public int amount; public String city; public Trans(String name, int time, int amount, String city) { this.name = name; this.time = time; this.amount = amount; this.city = city; } } class Solution { public List invalidTransactions(String[] transactions) { List ans = new ArrayList<>(); Map> nameToTranses = new HashMap<>(); for (final String t : transactions) { Trans trans = getTrans(t); nameToTranses.putIfAbsent(trans.name, new ArrayList<>()); nameToTranses.get(trans.name).add(trans); } for (final String t : transactions) { Trans currTrans = getTrans(t); if (currTrans.amount > 1000) { ans.add(t); } else if (nameToTranses.containsKey(currTrans.name)) { // Iterate through all the transactions with the same name, check if // they're within 60 minutes in a different city. for (Trans trans : nameToTranses.get(currTrans.name)) if (Math.abs(trans.time - currTrans.time) <= 60 && !trans.city.equals(currTrans.city)) { ans.add(t); break; } } } return ans; } private Trans getTrans(final String t) { String[] s = t.split(","); // [name, time, amount, city] return new Trans(s[0], Integer.parseInt(s[1]), Integer.parseInt(s[2]), s[3]); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution: def invalidTransactions(self, transactions: List[str]) -> List[str]: ans = [] nameToTranses = collections.defaultdict(list) for t in transactions: name, time, amount, city = t.split(',') time, amount = int(time), int(amount) nameToTranses[name].append({'time': time, 'city': city}) for t in transactions: name, time, amount, city = t.split(',') time, amount = int(time), int(amount) if amount > 1000: ans.append(t) elif name in nameToTranses: for sameName in nameToTranses[name]: if abs(sameName['time'] - time) <= 60 and sameName['city'] != city: ans.append(t) break return ans