Invalid Transactions
Invalid Transactions is a medium arrays & hashing problem solved with the hashing pattern.
The best approach, optimal (group by name + sliding time window), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from compare every pair up.
Problem
Each entry of transactions is a string "name,time,amount,city": who paid, at which minute, how much, and where.
A transaction is possibly invalid if its amount is greater than 1000, or if the same person made another transaction in a different city at most 60 minutes before or after it (the 60-minute boundary counts).
Return every possibly invalid transaction, as the original strings, in any order. If the same string appears several times and is invalid, include each copy.
Examples
Example 1
- Input
transactions = ["ravi,100,300,pune", "ravi,140,250,goa", "mira,500,1200,goa"]- Output
["ravi,100,300,pune", "ravi,140,250,goa", "mira,500,1200,goa"]- Why
- ravi's two transactions are 40 minutes apart in different cities, so both are flagged; mira's is over 1000.
Example 2
- Input
transactions = ["lena,10,800,oslo", "lena,71,900,bergen", "lena,200,1001,oslo"]- Output
["lena,200,1001,oslo"]- Why
- The first two are 61 minutes apart, which is outside the window; only the third exceeds 1000.
Example 3
- Input
transactions = ["tom,30,20,rome", "ann,50,20,milan", "tom,90,40,rome"]- Output
[]- Why
- tom stays in one city and the city change is by a different person, so nothing is invalid.
Constraints
1 <= transactions.length <= 1000- Each transaction has the form
"name,time,amount,city". nameandcityare 1 to 10 lowercase English letters.0 <= time <= 1000and0 <= amount <= 2000, written as integers without leading zeros.- The answer may be returned in any order.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Compare every pair | O(n²) | O(n) |
| Optimal (group by name + sliding time window) | O(n log n) | O(n) |
1Compare every pair
O(n²)All n(n - 1) / 2 pairs are compared, each in O(1) after parsing (names and cities are at most 10 characters).O(n)The parsed fields and the marks.Parse all transactions. Mark one invalid if its amount is over 1000, or if some other transaction has the same name, a different city and a time at most 60 minutes away.
- Split each string by commas into name, time, amount, city.
- For each pair (i, j): if the names match, the cities differ and |time_i - time_j| <= 60, mark both.
- Also mark every transaction with amount > 1000.
- Return the original strings of the marked transactions.
class Solution {
public List<String> invalidTransactions(String[] transactions) {
int n = transactions.length;
String[] name = new String[n], city = new String[n];
int[] time = new int[n], amount = new int[n];
for (int i = 0; i < n; i++) {
String[] p = transactions[i].split(",");
name[i] = p[0];
time[i] = Integer.parseInt(p[1]);
amount[i] = Integer.parseInt(p[2]);
city[i] = p[3];
}
boolean[] bad = new boolean[n];
for (int i = 0; i < n; i++) {
if (amount[i] > 1000) bad[i] = true;
for (int j = i + 1; j < n; j++) {
if (name[i].equals(name[j]) && !city[i].equals(city[j]) && Math.abs(time[i] - time[j]) <= 60) {
bad[i] = true;
bad[j] = true;
}
}
}
List<String> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (bad[i]) res.add(transactions[i]);
}
return res;
}
}class Solution:
def invalidTransactions(self, transactions: List[str]) -> List[str]:
parsed = []
for t in transactions:
name, time, amount, city = t.split(",")
parsed.append((name, int(time), int(amount), city))
n = len(parsed)
bad = [False] * n
for i in range(n):
if parsed[i][2] > 1000:
bad[i] = True
for j in range(i + 1, n):
a, b = parsed[i], parsed[j]
if a[0] == b[0] and a[3] != b[3] and abs(a[1] - b[1]) <= 60:
bad[i] = bad[j] = True
return [transactions[i] for i in range(n) if bad[i]]class Solution {
public:
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 part;
getline(ss, name[i], ',');
getline(ss, part, ',');
time[i] = stoi(part);
getline(ss, part, ',');
amount[i] = stoi(part);
getline(ss, city[i], ',');
}
vector<bool> bad(n, false);
for (int i = 0; i < n; i++) {
if (amount[i] > 1000) bad[i] = true;
for (int j = i + 1; j < n; j++) {
if (name[i] == name[j] && city[i] != city[j] && abs(time[i] - time[j]) <= 60) {
bad[i] = true;
bad[j] = true;
}
}
}
vector<string> res;
for (int i = 0; i < n; i++) {
if (bad[i]) res.push_back(transactions[i]);
}
return res;
}
};function invalidTransactions(transactions) {
const parsed = transactions.map((t) => {
const [name, time, amount, city] = t.split(",");
return { name, time: Number(time), amount: Number(amount), city };
});
const n = parsed.length;
const bad = new Array(n).fill(false);
for (let i = 0; i < n; i++) {
if (parsed[i].amount > 1000) bad[i] = true;
for (let j = i + 1; j < n; j++) {
const a = parsed[i], b = parsed[j];
if (a.name === b.name && a.city !== b.city && Math.abs(a.time - b.time) <= 60) {
bad[i] = true;
bad[j] = true;
}
}
}
return transactions.filter((_, i) => bad[i]);
}2Optimal (group by name + sliding time window)
O(n log n)Sorting the groups dominates; the window pointers make one forward pass per group.O(n)Parsed fields, the groups and the window counter.Only transactions of the same person can conflict, so group indices by name and sort each group by time. For the transaction at time t, the partners that matter are exactly those with time in [t - 60, t + 60]. Both ends of that window only move forward as t grows, so two pointers plus a city counter tell you in O(1) amortized whether the window holds more than one distinct city.
- Parse every transaction and group the indices by name.
- Sort each group by time. Keep pointers lo and hi and a map city -> count for the window.
- For each transaction k in the group at time t: advance hi while time[hi] <= t + 60, adding its city; advance lo while time[lo] < t - 60, removing its city.
- If the map has more than one city, mark k invalid.
- Also mark every amount > 1000, then return the marked original strings.
class Solution {
public List<String> invalidTransactions(String[] transactions) {
int n = transactions.length;
String[] city = new String[n];
int[] time = new int[n], amount = new int[n];
Map<String, List<Integer>> byName = new HashMap<>();
for (int i = 0; i < n; i++) {
String[] p = transactions[i].split(",");
time[i] = Integer.parseInt(p[1]);
amount[i] = Integer.parseInt(p[2]);
city[i] = p[3];
byName.computeIfAbsent(p[0], k -> new ArrayList<>()).add(i);
}
boolean[] bad = new boolean[n];
for (List<Integer> group : byName.values()) {
group.sort((a, b) -> Integer.compare(time[a], time[b]));
Map<String, Integer> inWindow = new HashMap<>();
int m = group.size(), lo = 0, hi = 0;
for (int k = 0; k < m; k++) {
int t = time[group.get(k)];
while (hi < m && time[group.get(hi)] <= t + 60) {
inWindow.merge(city[group.get(hi)], 1, Integer::sum);
hi++;
}
while (time[group.get(lo)] < t - 60) {
String c = city[group.get(lo)];
if (inWindow.merge(c, -1, Integer::sum) == 0) inWindow.remove(c);
lo++;
}
if (inWindow.size() > 1) bad[group.get(k)] = true;
}
}
List<String> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (bad[i] || amount[i] > 1000) res.add(transactions[i]);
}
return res;
}
}class Solution:
def invalidTransactions(self, transactions: List[str]) -> List[str]:
n = len(transactions)
time = [0] * n
amount = [0] * n
city = [""] * n
by_name = {}
for i, t in enumerate(transactions):
name, tm, am, ct = t.split(",")
time[i], amount[i], city[i] = int(tm), int(am), ct
by_name.setdefault(name, []).append(i)
bad = [False] * n
for group in by_name.values():
group.sort(key=lambda i: time[i])
in_window = {}
m, lo, hi = len(group), 0, 0
for k in range(m):
t = time[group[k]]
while hi < m and time[group[hi]] <= t + 60:
c = city[group[hi]]
in_window[c] = in_window.get(c, 0) + 1
hi += 1
while time[group[lo]] < t - 60:
c = city[group[lo]]
in_window[c] -= 1
if in_window[c] == 0:
del in_window[c]
lo += 1
if len(in_window) > 1:
bad[group[k]] = True
return [transactions[i] for i in range(n) if bad[i] or amount[i] > 1000]class Solution {
public:
vector<string> invalidTransactions(vector<string>& transactions) {
int n = transactions.size();
vector<string> city(n);
vector<int> time(n), amount(n);
unordered_map<string, vector<int>> byName;
for (int i = 0; i < n; i++) {
stringstream ss(transactions[i]);
string name, part;
getline(ss, name, ',');
getline(ss, part, ',');
time[i] = stoi(part);
getline(ss, part, ',');
amount[i] = stoi(part);
getline(ss, city[i], ',');
byName[name].push_back(i);
}
vector<bool> bad(n, false);
for (auto& entry : byName) {
vector<int>& group = entry.second;
sort(group.begin(), group.end(), [&](int a, int b) { return time[a] < time[b]; });
unordered_map<string, int> inWindow;
int m = group.size(), lo = 0, hi = 0;
for (int k = 0; k < m; k++) {
int t = time[group[k]];
while (hi < m && time[group[hi]] <= t + 60) {
inWindow[city[group[hi]]]++;
hi++;
}
while (time[group[lo]] < t - 60) {
const string& c = city[group[lo]];
if (--inWindow[c] == 0) inWindow.erase(c);
lo++;
}
if (inWindow.size() > 1) bad[group[k]] = true;
}
}
vector<string> res;
for (int i = 0; i < n; i++) {
if (bad[i] || amount[i] > 1000) res.push_back(transactions[i]);
}
return res;
}
};function invalidTransactions(transactions) {
const n = transactions.length;
const time = new Array(n), amount = new Array(n), city = new Array(n);
const byName = new Map();
for (let i = 0; i < n; i++) {
const [name, tm, am, ct] = transactions[i].split(",");
time[i] = Number(tm);
amount[i] = Number(am);
city[i] = ct;
if (!byName.has(name)) byName.set(name, []);
byName.get(name).push(i);
}
const bad = new Array(n).fill(false);
for (const group of byName.values()) {
group.sort((a, b) => time[a] - time[b]);
const inWindow = new Map();
const m = group.length;
let lo = 0, hi = 0;
for (let k = 0; k < m; k++) {
const t = time[group[k]];
while (hi < m && time[group[hi]] <= t + 60) {
const c = city[group[hi]];
inWindow.set(c, (inWindow.get(c) || 0) + 1);
hi++;
}
while (time[group[lo]] < t - 60) {
const c = city[group[lo]];
const left = inWindow.get(c) - 1;
if (left === 0) inWindow.delete(c);
else inWindow.set(c, left);
lo++;
}
if (inWindow.size > 1) bad[group[k]] = true;
}
}
return transactions.filter((_, i) => bad[i] || amount[i] > 1000);
}Edge cases to test
- Exactly 60 minutes apart counts as within the window
- Amount exactly 1000 is fine; 1001 is not
- Identical duplicate transactions: each copy is reported separately if invalid
- Same city at the same time is never a conflict
- Different names in different cities never conflict
Hints
Hint 1
Parse each string into its four fields first.
Hint 2
Checking every pair of transactions is fast enough for 1000 entries, but think about how to do better.
Hint 3
Group by name and sort each group by time. For each transaction, the others within 60 minutes form a window that only slides forward; count cities inside it.
FAQ
What is the best time complexity for Invalid Transactions?
Optimal (group by name + sliding time window) runs in O(n log n) time and O(n) extra space. Sorting the groups dominates; the window pointers make one forward pass per group.
Which pattern does Invalid Transactions use?
It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.
Is there a brute force solution for Invalid Transactions?
Yes. Compare every pair takes O(n²) time and O(n) space. Parse all transactions.
Which edge cases should I test for Invalid Transactions?
Exactly 60 minutes apart counts as within the window; Amount exactly 1000 is fine; 1001 is not; Identical duplicate transactions: each copy is reported separately if invalid; Same city at the same time is never a conflict; Different names in different cities never conflict.