Invalid Transactions
MedPrompt
A transaction is possibly invalid if:
- the amount exceeds
$1000, or; - if it occurs within (and including)
60minutes 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.
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 between1and10. - Each
{time}consist of digits, and represent an integer between0and1000. - Each
{amount}consist of digits, and represent an integer between0and2000.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code by iterating through every possible pair of transactions to check for the invalid conditions. It is the most straightforward but least efficient method, serving as a baseline.
Algorithm
- Create a
Transactionclass or use parallel arrays to store the parsed details of each transaction:name,time,amount, andcity. - Initialize a boolean array,
isInvalid, of sizen(number of transactions) to allfalse. - Iterate through each transaction
ifrom0ton-1:- Check the amount condition: If
transactions[i].amount > 1000, setisInvalid[i] = true. - Start a nested loop for each transaction
jfrom0ton-1:- If
iandjare the same, skip. - Check the conflict condition: If
transactions[i].nameequalstransactions[j].name,transactions[i].cityis different fromtransactions[j].city, and the absolute difference in their times is less than or equal to 60, then transactioniis invalid. - If the condition is met, set
isInvalid[i] = trueandbreakthe inner loop, as we've confirmediis invalid.
- If
- Check the amount condition: If
- After the loops, create a result list.
- Iterate from
i = 0ton-1. IfisInvalid[i]istrue, add the original transaction stringtransactions[i]to the result list. - Return the result list.
Walkthrough
In this method, we first parse all transaction strings into a more accessible format, such as parallel arrays or a list of custom objects, to easily retrieve the name, time, amount, and city for each transaction. We then use a boolean array, isInvalid, to keep track of the validity status of each transaction, initialized to false.
The core of the algorithm is a nested loop. The outer loop selects a transaction i, and the inner loop compares it against every other transaction j. For each transaction i, we first check if its amount exceeds $1000. If it does, we immediately mark it as invalid. Then, in the inner loop, we check for the second invalidity condition: a transaction j with the same name, a different city, and a time within 60 minutes. If such a transaction j is found, we mark transaction i as invalid and can break out of the inner loop since its status is confirmed.
After checking all transactions, we iterate through the isInvalid array and collect all the original transaction strings that were marked as invalid into a final list to be returned.
class Solution { public List<String> invalidTransactions(String[] transactions) { int n = transactions.length; if (n == 0) { return new ArrayList<>(); } String[] names = new String[n]; int[] times = new int[n]; int[] amounts = new int[n]; String[] cities = new String[n]; for (int i = 0; i < n; i++) { String[] parts = transactions[i].split(","); names[i] = parts[0]; times[i] = Integer.parseInt(parts[1]); amounts[i] = Integer.parseInt(parts[2]); cities[i] = parts[3]; } boolean[] isInvalid = new boolean[n]; for (int i = 0; i < n; i++) { if (amounts[i] > 1000) { isInvalid[i] = true; } for (int j = 0; j < n; j++) { if (i == j) continue; if (names[i].equals(names[j]) && !cities[i].equals(cities[j]) && Math.abs(times[i] - times[j]) <= 60) { isInvalid[i] = true; break; } } } List<String> result = new ArrayList<>(); for (int i = 0; i < n; i++) { if (isInvalid[i]) { result.add(transactions[i]); } } return result; }}Complexity
Time
O(N^2), where N is the number of transactions. The nested loops that compare every pair of transactions dominate the runtime.
Space
O(N), where N is the number of transactions. This space is used to store the parsed transaction data and the `isInvalid` boolean array.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal complex data structures.
Cons
Inefficient for large inputs due to the O(N^2) time complexity.
Performs many redundant comparisons, especially for transactions with unique names.
This optimized approach improves upon the brute-force method by reducing unnecessary comparisons. It works by first grouping all transactions by name using a HashMap. Then, for each name, it sorts the corresponding transactions by time. This sorting allows for a much more efficient search for time-based conflicts, as we only need to check a small window of transactions around the current one.
Algorithm
- Define a
Transactionclass to hold parsed data (name,time,amount,city) and the original transaction string. - Create a
HashMap<String, List<Transaction>>to group transactions by name. - Iterate through the input array, parse each transaction string into a
Transactionobject, and add it to the corresponding list in theHashMap. - Initialize a
HashSet<String>to store the final list of invalid transactions, which helps avoid duplicates. - Iterate through each list of transactions in the
HashMap's values:- Sort the list by transaction time.
- Iterate through the sorted list with an index
i. Let the current transaction bet1.- If
t1.amount > 1000, add its original string to the result set. - Start a nested loop with index
jfromi + 1to check subsequent transactions (t2). - If
t2.time - t1.time > 60, break the inner loop, as all further transactions will also be outside the time window. - If
t1andt2have different cities, they are a conflicting pair. Add the original strings of botht1andt2to the result set.
- If
- Convert the result set to a list and return it.
Walkthrough
The key insight for this optimization is that we only need to compare transactions that share the same name. We can achieve this efficiently by using a HashMap where keys are names and values are lists of transactions for that name.
First, we parse each transaction string into a custom Transaction object and populate the HashMap. After grouping, we process each group (each list of transactions in the map) independently. To efficiently check the time condition (|time1 - time2| <= 60), we sort each list of transactions by time.
With a sorted list, for any given transaction t1, we only need to look at the transactions t2 that immediately follow it. We can iterate forward from t1 and check for conflicts. As soon as we find a t2 where t2.time - t1.time > 60, we can stop searching for that t1 because all subsequent transactions will also be outside the 60-minute window. If a conflicting transaction is found (same name, different city, time difference <= 60), both transactions involved are marked as invalid. We use a Set to store the results to automatically handle duplicates. Finally, we convert the set to a list.
class Solution { class Transaction { String name; int time; int amount; String city; String original; public Transaction(String transactionString) { String[] parts = transactionString.split(","); this.name = parts[0]; this.time = Integer.parseInt(parts[1]); this.amount = Integer.parseInt(parts[2]); this.city = parts[3]; this.original = transactionString; } } public List<String> invalidTransactions(String[] transactions) { Map<String, List<Transaction>> nameToTransactionsMap = new HashMap<>(); for (String t : transactions) { Transaction transaction = new Transaction(t); nameToTransactionsMap.computeIfAbsent(transaction.name, k -> new ArrayList<>()).add(transaction); } Set<String> invalidSet = new HashSet<>(); for (List<Transaction> transactionList : nameToTransactionsMap.values()) { Collections.sort(transactionList, (a, b) -> a.time - b.time); for (int i = 0; i < transactionList.size(); i++) { Transaction t1 = transactionList.get(i); if (t1.amount > 1000) { invalidSet.add(t1.original); } for (int j = i + 1; j < transactionList.size(); j++) { Transaction t2 = transactionList.get(j); if (t2.time - t1.time > 60) { break; } if (!t1.city.equals(t2.city)) { invalidSet.add(t1.original); invalidSet.add(t2.original); } } } } return new ArrayList<>(invalidSet); }}Complexity
Time
O(N log K + M), where N is the total number of transactions, K is the maximum number of transactions for a single name, and M is the number of pairwise comparisons. The dominant factor is often sorting, leading to an average complexity close to O(N log K). The worst-case is O(N^2) if all transactions share the same name.
Space
O(N), where N is the number of transactions. Space is required for the `HashMap`, the `Transaction` objects it contains, and the result `Set`.
Trade-offs
Pros
Significantly faster than brute force on average, especially when names are diverse.
Sorting by time allows for early termination of the inner loop, optimizing the search for conflicts.
Cons
More complex to implement due to the use of a HashMap, sorting, and a custom class.
The worst-case time complexity is still O(N^2), which occurs if all transactions have the same name.
Solutions
Solution
class Solution {public List<String> invalidTransactions(String[] transactions) { Map<String, List<Item>> d = new HashMap<>(); Set<Integer> idx = new HashSet<>(); for (int i = 0; i < transactions.length; ++i) { var e = transactions[i].split(","); String name = e[0]; int time = Integer.parseInt(e[1]); int amount = Integer.parseInt(e[2]); String city = e[3]; d.computeIfAbsent(name, k->new ArrayList<>()) .add(new Item(time, city, i)); if (amount > 1000) { idx.add(i); } for (Item item : d.get(name)) { if (!city.equals(item.city) && Math.abs(time - item.t) <= 60) { idx.add(i); idx.add(item.i); } } } List<String> ans = new ArrayList<>(); for (int i : idx) { ans.add(transactions[i]); } return ans; }} class Item { int t; String city; int i; Item(int t, String city, int i) { this.t = t; this.city = city; this.i = i; }}class Solution {public: vector<string> invalidTransactions(vector<string> &transactions) { unordered_map<string, vector<tuple<int, string, int>>> d; unordered_set<int> idx; for (int i = 0; i < transactions.size(); ++i) { vector<string> e = split(transactions[i], ','); string name = e[0]; int time = stoi(e[1]); int amount = stoi(e[2]); string city = e[3]; d[name].push_back({time, city, i}); if (amount > 1000) { idx.insert(i); } for (auto &[t, c, j] : d[name]) { if (c != city && abs(time - t) <= 60) { idx.insert(i); idx.insert(j); } } } vector<string> ans; for (int i : idx) { ans.emplace_back(transactions[i]); } return ans; } vector<string> split(string &s, char delim) { stringstream ss(s); string item; vector<string> res; while (getline(ss, item, delim)) { res.emplace_back(item); } return res; }};class Solution: def invalidTransactions(self, transactions: List[str]) -> List[str]: d = defaultdict(list) idx = set() for i, x in enumerate(transactions): name, time, amount, city = x . split(",") time, amount = int(time), int(amount) d[name]. append((time, city, i)) if amount > 1000: idx . add(i) for t, c, j in d[name]: if c != city and abs(time - t) <= 60: idx . add(i) idx . add(j) return [transactions[i] for i in idx]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.