Skip to content

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 Transaction {
  string name;
  int time;
  int amount;
  string city;
};

class Solution {
 public:
  vector<string> invalidTransactions(vector<string>& transactions) {
    vector<string> ans;
    unordered_map<string, vector<Transaction>> nameToTransactions;

    for (const string& t : transactions) {
      const Transaction transaction = getTransaction(t);
      nameToTransactions[transaction.name].push_back(transaction);
    }

    for (const string& t : transactions) {
      const Transaction currTransaction = getTransaction(t);
      if (currTransaction.amount > 1000) {
        ans.push_back(t);
      } else if (const auto it = nameToTransactions.find(currTransaction.name);
                 it != nameToTransactions.cend()) {
        // Iterate through all the transactions with the same name, check if
        // they're within 60 minutes in a different city.
        for (Transaction transaction : it->second)
          if (abs(transaction.time - currTransaction.time) <= 60 &&
              transaction.city != currTransaction.city) {
            ans.push_back(t);
            break;
          }
      }
    }

    return ans;
  }

 private:
  Transaction getTransaction(const string& t) {
    istringstream iss(t);
    vector<string> s(4, "");
    for (int i = 0; getline(iss, s[i++], ',');)
      ;
    return {s[0], stoi(s[1]), stoi(s[2]), s[3]};  // [name, time, amount, city]
  }
};

 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
class Solution {
  public List<String> invalidTransactions(String[] transactions) {
    List<String> ans = new ArrayList<>();
    Map<String, List<Trans>> nameToTrans = new HashMap<>();

    for (final String t : transactions) {
      Trans trans = getTrans(t);
      nameToTrans.putIfAbsent(trans.name, new ArrayList<>());
      nameToTrans.get(trans.name).add(trans);
    }

    for (final String t : transactions) {
      Trans currTrans = getTrans(t);
      if (currTrans.amount > 1000) {
        ans.add(t);
      } else if (nameToTrans.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 : nameToTrans.get(currTrans.name))
          if (Math.abs(trans.time - currTrans.time) <= 60 && !trans.city.equals(currTrans.city)) {
            ans.add(t);
            break;
          }
      }
    }

    return ans;
  }

  private record Trans(String name, int time, int amount, String city) {}

  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 = []
    nameToTrans = collections.defaultdict(list)

    for t in transactions:
      name, time, amount, city = t.split(',')
      time, amount = int(time), int(amount)
      nameToTrans[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 nameToTrans:
        for sameName in nameToTrans[name]:
          if abs(sameName['time'] - time) <= 60 and sameName['city'] != city:
            ans.append(t)
            break

    return ans