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

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