Invalid Transactions

medium hash map string parsing grouping

Problem

Each transaction is a string "name,time,amount,city". A transaction is invalid if its amount exceeds 1000, or if there is another transaction with the same name in a different city whose time is within 60 minutes (inclusive). Return all invalid transactions in any order.

Input["alice,20,800,mtv", "alice,50,100,beijing"]

Output["alice,20,800,mtv", "alice,50,100,beijing"]

Both are alice, |20 − 50| = 30 ≤ 60, and cities differ (mtv vs beijing), so both are invalid.

transactions (one per line: name,time,amount,city)

def invalid_transactions(transactions):
    parsed = []
    for t in transactions:
        name, time, amount, city = t.split(",")
        parsed.append((name, int(time), int(amount), city))
    invalid = set()
    for i, (name, time, amount, city) in enumerate(parsed):
        if amount > 1000:
            invalid.add(i)
        for j, (n2, t2, a2, c2) in enumerate(parsed):
            if i != j and name == n2 and city != c2 and abs(time - t2) <= 60:
                invalid.add(i)
    return [transactions[i] for i in invalid]

function invalidTransactions(transactions) {
  const parsed = transactions.map(function (t) {
    const p = t.split(",");
    return { name: p[0], time: +p[1], amount: +p[2], city: p[3] };
  });
  const invalid = new Set();
  for (let i = 0; i < parsed.length; i++) {
    const a = parsed[i];
    if (a.amount > 1000) invalid.add(i);
    for (let j = 0; j < parsed.length; j++) {
      const b = parsed[j];
      if (i !== j && a.name === b.name && a.city !== b.city && Math.abs(a.time - b.time) <= 60)
        invalid.add(i);
    }
  }
  return [...invalid].map(function (i) { return transactions[i]; });
}

class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        int n = transactions.length;
        String[][] p = new String[n][];
        for (int i = 0; i < n; i++) p[i] = transactions[i].split(",");
        Set<Integer> invalid = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (Integer.parseInt(p[i][2]) > 1000) invalid.add(i);
            for (int j = 0; j < n; j++) {
                if (i != j && p[i][0].equals(p[j][0]) && !p[i][3].equals(p[j][3])
                        && Math.abs(Integer.parseInt(p[i][1]) - Integer.parseInt(p[j][1])) <= 60)
                    invalid.add(i);
            }
        }
        List<String> res = new ArrayList<>();
        for (int i : invalid) res.add(transactions[i]);
        return res;
    }
}

vector<string> invalidTransactions(vector<string>& transactions) {
    int n = transactions.size();
    vector<string> name(n), city(n);
    vector<int> time(n), amount(n);
    for (int i = 0; i < n; i++) {
        stringstream ss(transactions[i]);
        string nm, tm, am, ct;
        getline(ss, nm, ','); getline(ss, tm, ',');
        getline(ss, am, ','); getline(ss, ct, ',');
        name[i] = nm; time[i] = stoi(tm); amount[i] = stoi(am); city[i] = ct;
    }
    set<int> invalid;
    for (int i = 0; i < n; i++) {
        if (amount[i] > 1000) invalid.insert(i);
        for (int j = 0; j < n; j++)
            if (i != j && name[i] == name[j] && city[i] != city[j] && abs(time[i] - time[j]) <= 60)
                invalid.insert(i);
    }
    vector<string> res;
    for (int i : invalid) res.push_back(transactions[i]);
    return res;
}

Explanation

Each transaction is a comma-separated string, so the first step is to parse it into name, time, amount, and city. After that we just apply the two invalidity rules.

Rule one is local: any transaction with amount > 1000 is invalid on its own. Rule two is relational: a transaction is invalid if another transaction with the same name, a different city, and a time within 60 minutes exists. We collect the offending indices in a set so each is reported once.

To check rule two we compare every transaction against every other in a nested loop, flagging i whenever name == n2, city != c2, and abs(time - t2) <= 60 all hold.

Example: "alice,20,800,mtv" and "alice,50,100,beijing" — same name, |20 - 50| = 30 ≤ 60, and different cities, so both are flagged invalid.

Finally we map the flagged indices back to their original strings and return them. The pairwise comparison makes this O(n²), which is fine for the small input sizes here.

Time: O(n²) Space: O(n)