Invalid Transactions

Problem

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.

You are given an array of strings transaction where transactions[i] consists of comma-separated values representing the name, time (in minutes), amount, and city of the transaction.

Return a list of transactions that are possibly invalid. You may return the answer in any order.

Examples

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.

Solution

Method 1 – Brute Force with Hash Map

Intuition

We need to check two conditions for each transaction: if the amount exceeds 1000, or if there is another transaction with the same name in a different city within 60 minutes. We can use a hash map to group transactions by name and compare each pair for the second condition.

Approach

1. Parse each transaction into a tuple: (name, time, amount, city, original string).
2. For each transaction, mark as invalid if amount > 1000.
3. Group transactions by name in a hash map.
4. For each group, compare every pair of transactions:
   • If cities differ and times are within 60 minutes, mark both as invalid.
5. Collect and return all invalid transactions.

Code

C++

vector<string> invalidTransactions(vector<string>& transactions) {
    struct Txn { string name, city, orig; int time, amt; };
    vector<Txn> txns;
    for (auto& s : transactions) {
        auto p1 = s.find(','), p2 = s.find(',', p1+1), p3 = s.find(',', p2+1);
        string name = s.substr(0, p1);
        int time = stoi(s.substr(p1+1, p2-p1-1));
        int amt = stoi(s.substr(p2+1, p3-p2-1));
        string city = s.substr(p3+1);
        txns.push_back({name, city, s, time, amt});
    }
    int n = txns.size();
    vector<bool> bad(n);
    unordered_map<string, vector<int>> mp;
    for (int i = 0; i < n; ++i) {
        if (txns[i].amt > 1000) bad[i] = true;
        mp[txns[i].name].push_back(i);
    }
    for (auto& [_, idxs] : mp) {
        for (int i = 0; i < idxs.size(); ++i) {
            for (int j = i+1; j < idxs.size(); ++j) {
                auto &a = txns[idxs[i]], &b = txns[idxs[j]];
                if (a.city != b.city && abs(a.time - b.time) <= 60) {
                    bad[idxs[i]] = bad[idxs[j]] = true;
                }
            }
        }
    }
    vector<string> ans;
    for (int i = 0; i < n; ++i) if (bad[i]) ans.push_back(txns[i].orig);
    return ans;
}

Go

func invalidTransactions(transactions []string) []string {
    type Txn struct{ name, city, orig string; time, amt int }
    txns := []Txn{}
    for _, s := range transactions {
        parts := strings.Split(s, ",")
        t := Txn{parts[0], parts[3], s, atoi(parts[1]), atoi(parts[2])}
        txns = append(txns, t)
    }
    n := len(txns)
    bad := make([]bool, n)
    mp := map[string][]int{}
    for i, t := range txns {
        if t.amt > 1000 { bad[i] = true }
        mp[t.name] = append(mp[t.name], i)
    }
    for _, idxs := range mp {
        for i := 0; i < len(idxs); i++ {
            for j := i+1; j < len(idxs); j++ {
                a, b := txns[idxs[i]], txns[idxs[j]]
                if a.city != b.city && abs(a.time-b.time) <= 60 {
                    bad[idxs[i]], bad[idxs[j]] = true, true
                }
            }
        }
    }
    ans := []string{}
    for i, b := range bad {
        if b { ans = append(ans, txns[i].orig) }
    }
    return ans
}

Java

class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        class Txn { String name, city, orig; int time, amt; }
        List<Txn> txns = new ArrayList<>();
        for (String s : transactions) {
            String[] p = s.split(",");
            Txn t = new Txn();
            t.name = p[0]; t.time = Integer.parseInt(p[1]); t.amt = Integer.parseInt(p[2]); t.city = p[3]; t.orig = s;
            txns.add(t);
        }
        int n = txns.size();
        boolean[] bad = new boolean[n];
        Map<String, List<Integer>> mp = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            if (txns.get(i).amt > 1000) bad[i] = true;
            mp.computeIfAbsent(txns.get(i).name, k -> new ArrayList<>()).add(i);
        }
        for (var idxs : mp.values()) {
            for (int i = 0; i < idxs.size(); ++i) {
                for (int j = i+1; j < idxs.size(); ++j) {
                    var a = txns.get(idxs.get(i)), b = txns.get(idxs.get(j));
                    if (!a.city.equals(b.city) && Math.abs(a.time - b.time) <= 60) {
                        bad[idxs.get(i)] = bad[idxs.get(j)] = true;
                    }
                }
            }
        }
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) if (bad[i]) ans.add(txns.get(i).orig);
        return ans;
    }
}

Kotlin

class Solution {
    fun invalidTransactions(transactions: Array<String>): List<String> {
        data class Txn(val name: String, val city: String, val orig: String, val time: Int, val amt: Int)
        val txns = transactions.map {
            val p = it.split(",")
            Txn(p[0], p[3], it, p[1].toInt(), p[2].toInt())
        }
        val n = txns.size
        val bad = BooleanArray(n)
        val mp = mutableMapOf<String, MutableList<Int>>()
        for (i in 0 until n) {
            if (txns[i].amt > 1000) bad[i] = true
            mp.getOrPut(txns[i].name) { mutableListOf() }.add(i)
        }
        for (idxs in mp.values) {
            for (i in idxs.indices) {
                for (j in i+1 until idxs.size) {
                    val a = txns[idxs[i]]; val b = txns[idxs[j]]
                    if (a.city != b.city && kotlin.math.abs(a.time - b.time) <= 60) {
                        bad[idxs[i]] = true; bad[idxs[j]] = true
                    }
                }
            }
        }
        return (0 until n).filter { bad[it] }.map { txns[it].orig }
    }
}

Python

def invalid_transactions(transactions: list[str]) -> list[str]:
    txns = []
    for s in transactions:
        name, time, amt, city = s.split(',')
        txns.append((name, int(time), int(amt), city, s))
    n = len(txns)
    bad = [False] * n
    mp = {}
    for i, (name, time, amt, city, _) in enumerate(txns):
        if amt > 1000:
            bad[i] = True
        mp.setdefault(name, []).append(i)
    for idxs in mp.values():
        for i in range(len(idxs)):
            for j in range(i+1, len(idxs)):
                a = txns[idxs[i]]; b = txns[idxs[j]]
                if a[3] != b[3] and abs(a[1] - b[1]) <= 60:
                    bad[idxs[i]] = bad[idxs[j]] = True
    return [txns[i][4] for i in range(n) if bad[i]]

Rust

use std::collections::HashMap;
fn invalid_transactions(transactions: Vec<String>) -> Vec<String> {
    let mut txns = vec![];
    for s in &transactions {
        let p: Vec<&str> = s.split(',').collect();
        txns.push((p[0], p[1].parse::<i32>().unwrap(), p[2].parse::<i32>().unwrap(), p[3], s));
    }
    let n = txns.len();
    let mut bad = vec![false; n];
    let mut mp: HashMap<&str, Vec<usize>> = HashMap::new();
    for (i, (name, time, amt, city, _)) in txns.iter().enumerate() {
        if *amt > 1000 { bad[i] = true; }
        mp.entry(name).or_default().push(i);
    }
    for idxs in mp.values() {
        for i in 0..idxs.len() {
            for j in i+1..idxs.len() {
                let a = &txns[idxs[i]]; let b = &txns[idxs[j]];
                if a.3 != b.3 && (a.1 - b.1).abs() <= 60 {
                    bad[idxs[i]] = true; bad[idxs[j]] = true;
                }
            }
        }
    }
    let mut ans = vec![];
    for i in 0..n {
        if bad[i] { ans.push(txns[i].4.to_string()); }
    }
    ans
}

TypeScript

function invalidTransactions(transactions: string[]): string[] {
  const txns: [string, number, number, string, string][] = [];
  for (const s of transactions) {
    const [name, time, amt, city] = s.split(',');
    txns.push([name, +time, +amt, city, s]);
  }
  const n = txns.length;
  const bad = Array(n).fill(false);
  const mp: Record<string, number[]> = {};
  for (let i = 0; i < n; ++i) {
    if (txns[i][2] > 1000) bad[i] = true;
    if (!mp[txns[i][0]]) mp[txns[i][0]] = [];
    mp[txns[i][0]].push(i);
  }
  for (const idxs of Object.values(mp)) {
    for (let i = 0; i < idxs.length; ++i) {
      for (let j = i+1; j < idxs.length; ++j) {
        const a = txns[idxs[i]], b = txns[idxs[j]];
        if (a[3] !== b[3] && Math.abs(a[1] - b[1]) <= 60) {
          bad[idxs[i]] = bad[idxs[j]] = true;
        }
      }
    }
  }
  return txns.filter((_, i) => bad[i]).map(x => x[4]);
}

Complexity

• ⏰ Time complexity: O(n^2) — For each name, we may compare every pair of transactions with that name.
• 🧺 Space complexity: O(n) — For storing transactions and groupings.