1169. Invalid Transactions

MediumArrayHash TableStringSorting
Leetcode Link

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:

  1. The transaction amount exceeds $1000.
  2. 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.

  1. We check whether the transaction exceeds $1000. This is straightforward and can be done for each transaction individually.
  2. 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.

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's collections 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:

  1. We create a loop to iterate through the given transactions.
  2. For each transaction, we split it into its four components (name, time, amount, and city).
  3. We convert the time and amount to integers to make numerical comparisons.
  4. We append the transaction information as a tuple to the defaultdict list corresponding to the name.
  5. 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.
  6. 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.
  7. 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.

💪
Level Up Your
Algo Skills

Example 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:

  1. Initialize d as defaultdict(list) and idx as an empty set set().

  2. 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 to idx.
      • Additionally, compare with Alice's previous transaction:
        • Found "NewYork" equals "NewYork" and time is within 60 minutes, so no other action is needed.
    • 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 index 0 and 2.
    • Fourth transaction: "Bob,30,1300,NewYork"

      • Split, convert, append, and since the amount is over $1000, add index 3 to idx.
      • No previous transactions for Bob, so no further checks.
    • 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 to idx.
      • No other transactions for Charlie, so no further checks.
  3. After all iterations, idx contains indices 1, 0, 2, 3, and 5. These correspond to the invalid transactions.

  4. 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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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, where n is the number of transactions.
  • Inside this loop, splitting each transaction into name, time, amount, and city takes O(m) time, where m 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 an O(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 to O(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 most k transactions, this nested loop will take O(k) time per transaction in the worst case, leading to an overall time complexity of O(nk) for the nested loops across all transactions.
  • The if condition checking for different cities and the time difference <= 60 is O(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 unique name. In the worst case, it has an entry for each transaction if all names are unique, which contributes O(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 contributes O(n) space complexity.

Overall, the space complexity is O(n), taking into account the space required for the input and auxiliary data structures.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫