Invalid Transactions — Solution in Python, Java & C++
Invalid Transactions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Invalid Transactions is a medium coding problem on arrays, strings and hash table, asked in Amazon and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Sorting
- Asked at: Amazon, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Each entry of transactions is a string "name,time,amount,city": who paid, the minute it happened, the amount and the city.
A transaction is possibly invalid if either:
- its amount is greater than
1000, or - it happens within (and including)
60minutes of another transaction with the same name in a different city.
Return every possibly invalid transaction, in the order they appear in transactions. Identical strings at different positions are separate transactions and are reported separately.
Example 1
Input: transactions = ["kai,20,800,pune","kai,75,100,delhi","ravi,30,1500,pune"]
Output: ["kai,20,800,pune","kai,75,100,delhi","ravi,30,1500,pune"]
Explanation: The two `kai` transactions are 55 minutes apart in different cities, so both are flagged; `ravi` spent more than 1000.
Example 2
Input: transactions = ["kai,20,800,pune","kai,81,100,delhi"]
Output: []
Explanation: 61 minutes apart is outside the window.
Example 3
Input: transactions = ["asha,10,1001,goa","asha,10,1000,goa"]
Output: ["asha,10,1001,goa"]
Explanation: Same city, and 1000 itself is allowed.
Constraints
1 <= transactions.length <= 1000each transactions[i] has the form "{name},{time},{amount},{city}"each {name} and {city} is 1 to 10 lowercase English letterseach {time} is an integer in [0, 1000]each {amount} is an integer in [0, 2000]
Hints for Invalid Transactions
Hint 1
Parse every string once into its four fields.
Hint 2
With at most 1000 transactions, comparing every pair is fast enough:
10^6checks.Hint 3
Transaction
iis flagged if its amount exceeds 1000, or if somejhas the same name, a different city and|time_i - time_j| <= 60. Keep the original strings so you can return them in input order.
How to solve Invalid Transactions
Both rules are local to a transaction and one other transaction, so parse once and test every pair — n <= 1000 makes the quadratic scan cheap and keeps the output in input order for free.
Approach
- Split each string on commas into
name,time,amount,city(converting the numbers). - For each
i: mark it ifamount > 1000; otherwise scan alljfor the same name, a different city and|time_i - time_j| <= 60. - Collect the original strings of the marked transactions, in index order.
Why it works
The two conditions are exactly the definition, and every transaction is checked against every other one, so nothing is missed. The j != i case is excluded automatically because a transaction never differs from itself in city.
Complexity
- Time —
O(n^2) - Space —
O(n)
Pitfalls
- Both transactions of a conflicting pair are invalid, not just the later one.
- The window is inclusive: exactly 60 minutes apart still counts.
- Do not de-duplicate — two identical strings are two transactions.
- An amount of exactly 1000 is fine; only strictly greater is invalid.
Reference solution
Python
from typing import List
def invalidTransactions(transactions: List[str]) -> List[str]:
parsed = []
for t in transactions:
name, time, amount, city = t.split(",")
parsed.append((name, int(time), int(amount), city))
res = []
for i, (name, time, amount, city) in enumerate(parsed):
bad = amount > 1000
if not bad:
for n2, t2, _, c2 in parsed:
if n2 == name and c2 != city and abs(t2 - time) <= 60:
bad = True
break
if bad:
res.append(transactions[i])
return resJava
public static String[] invalidTransactions(String[] transactions) {
int n = transactions.length;
String[] names = new String[n], cities = new String[n];
int[] times = new int[n], amounts = new int[n];
for (int k = 0; k < n; k++) {
String[] f = transactions[k].split(",");
names[k] = f[0];
times[k] = Integer.parseInt(f[1]);
amounts[k] = Integer.parseInt(f[2]);
cities[k] = f[3];
}
List<String> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
boolean bad = amounts[i] > 1000;
for (int j = 0; j < n && !bad; j++) {
if (names[j].equals(names[i]) && !cities[j].equals(cities[i]) && Math.abs(times[j] - times[i]) <= 60) bad = true;
}
if (bad) res.add(transactions[i]);
}
return res.toArray(new String[0]);
}C++
vector<string> invalidTransactions(vector<string>& transactions) {
int n = transactions.size();
vector<string> names(n), cities(n);
vector<int> times(n), amounts(n);
for (int k = 0; k < n; k++) {
stringstream ss(transactions[k]);
string part;
getline(ss, names[k], ',');
getline(ss, part, ',');
times[k] = stoi(part);
getline(ss, part, ',');
amounts[k] = stoi(part);
getline(ss, cities[k], ',');
}
vector<string> res;
for (int i = 0; i < n; i++) {
bool bad = amounts[i] > 1000;
for (int j = 0; j < n && !bad; j++) {
if (names[j] == names[i] && cities[j] != cities[i] && abs(times[j] - times[i]) <= 60) bad = true;
}
if (bad) res.push_back(transactions[i]);
}
return res;
}JavaScript
var invalidTransactions = function(transactions) {
var p = [];
for (var k = 0; k < transactions.length; k++) {
var f = transactions[k].split(",");
p.push({ name: f[0], time: parseInt(f[1], 10), amount: parseInt(f[2], 10), city: f[3] });
}
var res = [];
for (var i = 0; i < p.length; i++) {
var bad = p[i].amount > 1000;
for (var j = 0; j < p.length && !bad; j++) {
if (p[j].name === p[i].name && p[j].city !== p[i].city && Math.abs(p[j].time - p[i].time) <= 60) bad = true;
}
if (bad) res.push(transactions[i]);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.