1169. Invalid Transactions
Problem Description
The problem requires us to identify invalid financial transactions based on certain criteria. A transaction is considered to be possibly invalid if it meets at least one of the following conditions:
- The transaction amount exceeds $1000.
- There is another transaction with the same name and within 60 minutes of the current transaction, but in a different city.
We are provided with a list of transaction records. Each record is a string containing comma-separated values that represent the name of the client, the time of the transaction (in minutes), the amount of the transaction, and the city where the transaction took place.
Intuition
To find invalid transactions, we need to process each transaction and check it against the two criteria for invalidity.
- We check whether the transaction exceeds $1000. This is straightforward and can be done for each transaction individually.
- Checking if there is a similar transaction (same name) in a different city within a 60-minute window is more complex because it involves comparing each transaction with other transactions.
To keep track of transactions and make comparisons efficient, we use a data structure (in Python, a defaultdict
of lists) to map each unique name to a list of transactions associated with that name. This allows us to effectively group transactions by names and only compare transactions within each group.
The algorithm runs as follows:
- Iterate through all transactions. For each transaction:
- Split the data into the respective fields (name, time, amount, city).
- Check if the amount > $1000; if so, mark this transaction as invalid.
- Group this transaction with other transactions of the same name.
After grouping transactions, iterate over each group associated with a name and:
- Compare each transaction with the others in the group.
- If any two transactions have different cities and times within 60 minutes of each other, both are marked as invalid.
We use a set to keep track of indices of invalid transactions because sets avoid duplication and provide O(1) lookup. Finally, return the list of transactions at those indices marked as invalid.
Learn more about Sorting patterns.
Solution Approach
The algorithm to find invalid transactions from the problem uses a combination of data processing and efficient data structures to compare and filter the necessary information.
First, let's understand the key components:
-
The
defaultdict
from Python'scollections
module is used to map each person's name to a list. This list will store tuples containing the time of the transaction, the city where it occurred, and the index in the original transactions list. This data structure is particularly useful here because it allows automatic creation of a new list for each new key. -
A set
idx
is used to store the indices of transactions deemed invalid according to the problem criteria. The set is chosen for this purpose because the problem does not require us to maintain the order of invalid transactions, and sets prevent duplicates efficiently.
Here's a step-by-step breakdown of the implementation:
- We create a loop to iterate through the given transactions.
- For each transaction, we split it into its four components (name, time, amount, and city).
- We convert the
time
andamount
to integers to make numerical comparisons. - We append the transaction information as a tuple to the
defaultdict
list corresponding to thename
. - We immediately check if the transaction amount is greater than $1000. If so, we add the index of this transaction to the
idx
set since the transaction is invalid. - After that, we loop through the transactions stored in the list for this name. For each transaction pair, if they occurred in different cities, and their times are within 60 minutes of each other, both are marked invalid by adding their respective indices to the
idx
set. - The final step is to construct and return a list of invalid transactions using a list comprehension. We only include those transactions whose indices are stored in the
idx
set.
1class Solution:
2 def invalidTransactions(self, transactions: List[str]) -> List[str]:
3 d = defaultdict(list) # Mapping of names to their transaction details.
4 idx = set() # Set of indices of possibly invalid transactions.
5
6 for i, x in enumerate(transactions):
7 name, time, amount, city = x.split(",")
8 time, amount = int(time), int(amount)
9 d[name].append((time, city, i))
10
11 # Check if the transaction amount exceeds $1000.
12 if amount > 1000:
13 idx.add(i)
14
15 # Check for transactions with the same name in different cities within 60 minutes.
16 for t, c, j in d[name]:
17 if c != city and abs(time - t) <= 60:
18 idx.add(i)
19 idx.add(j)
20
21 # Generate a list of transactions that are possibly invalid.
22 return [transactions[i] for i in idx]
This solution takes advantage of Python's data structures to create a clear and efficient process that identifies invalid transactions as described.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider a sample list of transactions to illustrate the solution approach:
1transactions = ["Alice,20,800,NewYork", "Alice,25,1200,NewYork", "Alice,50,100,Philadelphia", "Bob,30,1300,NewYork", "Bob,40,700,NewYork", "Charlie,60,1500,NewYork"]
Here are the steps that the algorithm would follow to find invalid transactions from this list:
-
Initialize
d
asdefaultdict(list)
andidx
as an empty setset()
. -
The algorithm iterates through
transactions
. Let's observe the iteration:-
First transaction: "Alice,20,800,NewYork"
- Split into ("Alice", "20", "800", "NewYork") and convert "20" and "800" to integers.
- Append to
d["Alice"]
as (20, "NewYork", 0). - Since the amount is less than $1000, do nothing further.
-
Second transaction: "Alice,25,1200,NewYork"
- Split into ("Alice", "25", "1200", "NewYork"), convert to integers and append to
d["Alice"]
. - The amount exceeds $1000, so add index
1
toidx
. - Additionally, compare with Alice's previous transaction:
- Found "NewYork" equals "NewYork" and time is within 60 minutes, so no other action is needed.
- Split into ("Alice", "25", "1200", "NewYork"), convert to integers and append to
-
Third transaction: "Alice,50,100,Philadelphia"
- Split and convert to integers, append (50, "Philadelphia", 2) to
d["Alice"]
. - The amount is not over $1000, do nothing for the amount condition.
- Compare with Alice's transactions:
- Found that "Philadelphia" doesn't equal "NewYork", but time is within 60 minutes of "Alice,20,800,NewYork", so
idx
now includes index0
and2
.
- Found that "Philadelphia" doesn't equal "NewYork", but time is within 60 minutes of "Alice,20,800,NewYork", so
- Split and convert to integers, append (50, "Philadelphia", 2) to
-
Fourth transaction: "Bob,30,1300,NewYork"
- Split, convert, append, and since the amount is over $1000, add index
3
toidx
. - No previous transactions for Bob, so no further checks.
- Split, convert, append, and since the amount is over $1000, add index
-
Fifth transaction: "Bob,40,700,NewYork"
- Split, convert, append.
- The amount is not over $1000, do nothing for the amount condition.
- Time is within 60 minutes of Bob's transaction in "NewYork", but city is the same, so no action.
-
Final transaction: "Charlie,60,1500,NewYork"
- Split, convert, append, amount over $1000 so add index
5
toidx
. - No other transactions for Charlie, so no further checks.
- Split, convert, append, amount over $1000 so add index
-
-
After all iterations,
idx
contains indices 1, 0, 2, 3, and 5. These correspond to the invalid transactions. -
Construct the return list
[transactions[i] for i in idx]
. This results in list of invalid transactions:
1["Alice,20,800,NewYork", "Alice,25,1200,NewYork", "Alice,50,100,Philadelphia", "Bob,30,1300,NewYork", "Charlie,60,1500,NewYork"]
This example illustrates the application of the algorithm on a small set of data, exemplifying how the problem criteria are used to filter for possibly invalid transactions.
Solution Implementation
1from collections import defaultdict
2
3class Solution:
4 def invalidTransactions(self, transactions: List[str]) -> List[str]:
5 # Create a dictionary where each key is a person's name and each value
6 # is a list of tuples containing transaction time, city, and index in the original list.
7 transactions_dict = defaultdict(list)
8
9 # Set to store indices of invalid transactions.
10 invalid_indices = set()
11
12 # Iterate over the transactions to populate the dictionary.
13 for index, transaction in enumerate(transactions):
14 # Split the transaction data into its components.
15 name, time_str, amount_str, city = transaction.split(",")
16 # Convert time and amount to integers for comparison.
17 time, amount = int(time_str), int(amount_str)
18
19 # Append the tuple containing time, city, and index to the dictionary.
20 transactions_dict[name].append((time, city, index))
21
22 # Any transaction over $1000 is invalid.
23 if amount > 1000:
24 invalid_indices.add(index)
25
26 # Check for transactions within 60 minutes and different cities.
27 for other_time, other_city, other_index in transactions_dict[name]:
28 # If transaction occurred in a different city within 60 min, mark both as invalid.
29 if other_city != city and abs(time - other_time) <= 60:
30 invalid_indices.add(index)
31 invalid_indices.add(other_index)
32
33 # Construct the list of invalid transactions using the indices.
34 return [transactions[i] for i in invalid_indices]
35
1import java.util.*;
2
3class Solution {
4 public List<String> invalidTransactions(String[] transactions) {
5 // A map to maintain transaction items per user
6 Map<String, List<TransactionItem>> transactionMap = new HashMap<>();
7 // A set to keep track of invalid transaction indices
8 Set<Integer> invalidIndices = new HashSet<>();
9
10 // Iterate through all transactions
11 for (int i = 0; i < transactions.length; ++i) {
12 // Split the transaction string into individual pieces of data
13 String[] transactionDetails = transactions[i].split(",");
14 String name = transactionDetails[0];
15 int time = Integer.parseInt(transactionDetails[1]);
16 int amount = Integer.parseInt(transactionDetails[2]);
17 String city = transactionDetails[3];
18
19 // Add the transaction item under the user's name in the map
20 transactionMap.computeIfAbsent(name, k -> new ArrayList<>())
21 .add(new TransactionItem(time, city, i));
22
23 // If the amount exceeds $1000, mark as invalid
24 if (amount > 1000) {
25 invalidIndices.add(i);
26 }
27
28 // Check the transaction against other transaction items of the same user
29 for (TransactionItem item : transactionMap.get(name)) {
30 // If a transaction item with a different city within 60 minutes is found, mark as invalid
31 if (!city.equals(item.city) && Math.abs(time - item.time) <= 60) {
32 invalidIndices.add(i);
33 invalidIndices.add(item.index);
34 }
35 }
36 }
37
38 // Prepare the list of invalid transaction strings to return
39 List<String> answer = new ArrayList<>();
40 for (int index : invalidIndices) {
41 answer.add(transactions[index]);
42 }
43 return answer;
44 }
45}
46
47// A helper class to represent transaction items
48class TransactionItem {
49 int time;
50 String city;
51 int index;
52
53 TransactionItem(int time, String city, int index) {
54 this.time = time;
55 this.city = city;
56 this.index = index;
57 }
58}
59
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5#include <sstream>
6#include <tuple>
7
8using namespace std;
9
10class Solution {
11public:
12 vector<string> invalidTransactions(vector<string>& transactions) {
13 // Dictionary to hold information of transactions by user name.
14 unordered_map<string, vector<tuple<int, string, int>>> transactionsData;
15 // Set to hold indexes of invalid transactions.
16 unordered_set<int> invalidIndexes;
17
18 // Loop through each transaction to parse and process it.
19 for (int i = 0; i < transactions.size(); ++i) {
20 // Split the transaction into components.
21 vector<string> elements = split(transactions[i], ',');
22 // Extract the transaction components.
23 string name = elements[0];
24 int time = stoi(elements[1]);
25 int amount = stoi(elements[2]);
26 string city = elements[3];
27 // Store transaction data for future reference.
28 transactionsData[name].emplace_back(time, city, i);
29 // If the amount is over 1000, it's an invalid transaction.
30 if (amount > 1000) {
31 invalidIndexes.insert(i);
32 }
33 // Check other transactions for the same user for validity.
34 for (auto& [recordedTime, recordedCity, transactionIndex] : transactionsData[name]) {
35 // If the city is different and time within 60 minutes, mark as invalid.
36 if (recordedCity != city && abs(time - recordedTime) <= 60) {
37 invalidIndexes.insert(i);
38 invalidIndexes.insert(transactionIndex);
39 }
40 }
41 }
42
43 // Prepare the result vector with invalid transactions.
44 vector<string> result;
45 for (int index : invalidIndexes) {
46 result.push_back(transactions[index]);
47 }
48 return result;
49 }
50
51 // Helper function to split a string by delimiter.
52 vector<string> split(string& str, char delimiter) {
53 stringstream stream(str);
54 string item;
55 vector<string> tokens;
56 while (getline(stream, item, delimiter)) {
57 tokens.push_back(item);
58 }
59 return tokens;
60 }
61};
62
1type TransactionData = {
2 time: number;
3 city: string;
4 index: number;
5};
6
7// Function to find invalid transactions in the given set.
8function invalidTransactions(transactions: string[]): string[] {
9 // Map to hold information of transactions by user name.
10 const transactionsMap: Record<string, TransactionData[]> = {};
11 // Set to hold indexes of invalid transactions.
12 const invalidIndexes = new Set<number>();
13
14 // Loop through each transaction to parse and process it.
15 transactions.forEach((transaction, index) => {
16 // Split the transaction into components [name, time, amount, city].
17 const elements = split(transaction, ',');
18 // Extract and parse transaction components.
19 const name = elements[0];
20 const time = parseInt(elements[1], 10);
21 const amount = parseInt(elements[2], 10);
22 const city = elements[3];
23
24 // Initialize transactions for the user if not present.
25 if (!transactionsMap[name]) {
26 transactionsMap[name] = [];
27 }
28
29 // Store transaction data for future reference.
30 transactionsMap[name].push({ time: time, city: city, index: index });
31
32 // If the transaction amount is over 1000, it's invalid.
33 if (amount > 1000) {
34 invalidIndexes.add(index);
35 }
36
37 // Check other transactions for the same user for validity.
38 transactionsMap[name].forEach(({ time: recordedTime, city: recordedCity, index: transactionIndex }) => {
39 // If cities are different and times are within 60 minutes, mark as invalid.
40 if (recordedCity !== city && Math.abs(time - recordedTime) <= 60) {
41 invalidIndexes.add(index);
42 invalidIndexes.add(transactionIndex);
43 }
44 });
45 });
46
47 // Prepare the result array with invalid transactions using the invalidated indexes.
48 const result = Array.from(invalidIndexes).map(index => transactions[index]);
49
50 return result;
51}
52
53// Helper function to split a string by the given delimiter and return an array of substrings.
54function split(str: string, delimiter: string): string[] {
55 return str.split(delimiter);
56}
57
58// Example usage:
59const transactions = ["alice,20,800,mtv","alice,50,1200,mtv"];
60const result = invalidTransactions(transactions);
61console.log(result);
62
Time and Space Complexity
Time Complexity
The time complexity of the code can be analyzed as follows:
- The loop to iterate over all the transactions takes
O(n)
time, wheren
is the number of transactions. - Inside this loop, splitting each transaction into name, time, amount, and city takes
O(m)
time, wherem
is the average length of a transaction string. - Appending a tuple
(time, city, i)
to the list in the dictionary for the respective name is anO(1)
operation as appending to a list in Python has an amortized constant time complexity. However, since we do this for each transaction, it contributes toO(n)
over the entire loop. - The nested loop iterating through each entry in
d[name]
has a variable runtime that depends on the number of transactions associated with that name. If we assume that each person has at mostk
transactions, this nested loop will takeO(k)
time per transaction in the worst case, leading to an overall time complexity ofO(nk)
for the nested loops across all transactions. - The
if
condition checking for different cities and the time difference <= 60 isO(1)
.
So, the overall time complexity is O(n * (m + k))
.
Space Complexity
The space complexity of the code is given by:
- The dictionary
d
, which stores a list of tuples for each uniquename
. In the worst case, it has an entry for each transaction if all names are unique, which contributesO(n)
space complexity. - The set
idx
storing indices of invalid transactions, which in the worst case could include all transactions if they are all invalid, also contributesO(n)
space complexity.
Overall, the space complexity is O(n)
, taking into account the space required for the input and auxiliary data structures.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.