Problem Explanation

You are given a list of transaction details where each transaction is represented as a string with comma separated values indicating the name, time (in minutes), amount, and city of the transaction. Your task is to determine which transactions are possibly invalid based on the following criteria:

1. If the transaction amount exceeds $1000.

2. If a transaction occurs within (and including) 60 minutes of another transaction with the same name but in a different city.

The output should be a list of all "invalid" transactions. The order of the transactions in the returned list does not matter.

Example

Let's take an example to understand the problem. For transactions = ["alice,20,800,london", "alice,50,1000,paris", "bob,40,2000,berlin"],

Here, "alice,50,1000,paris" is invalid because it occurs within 60 minutes of another transaction with the same name but in a different city. "bob,40,2000,berlin" is invalid because its amount exceeds $1000. So, the result would be ["alice,50,1000,paris", "bob,40,2000,berlin"].

Approach

The solution uses a hashmap to store all the transactions based on the name of the transactor. Then we loop through the transactions. We add a transaction to our invalid list if it's amount is more than $1000 or if it occurs within 60 minutes of another transaction with the same name in a different city.

This can be done efficiently with the help of a data structure, unordered_map in C++ (equivalent to a dictionary in Python or a hashmap in Java), where the key is the name of the person and the value is a vector of the transaction structures. We also define a struct that represents the transaction details for ease of access.

Python Solution

1
2python
3from collections import defaultdict
4from typing import List
5
6class Transaction:
7    def __init__(self, name, time, amount, city):
8        self.name = name
9        self.time = time
10        self.amount = amount
11        self.city = city
12
13class Solution:
14    def invalidTransactions(self, transactions: List[str]) -> List[str]:
15        nameToTrans = defaultdict(list)
16        invalid = []
17
18        for trans in transactions:
19            name, time, amount, city = trans.split(',')
20            t = Transaction(name, int(time), int(amount), city)
21            nameToTrans[name].append(t)
22
23            if t.amount > 1000:
24                invalid.append(trans)
25
26        for trans in transactions:
27            name, time, amount, city = trans.split(',')
28            t = Transaction(name, int(time), int(amount), city)
29            
30            if any(abs(tt.time - t.time) <= 60 and tt.city != city for tt in nameToTrans[name]):
31                invalid.append(trans)
32
33        return list(set(invalid)) # remove duplicates and return

In the above Python solution, we utilize a dictionary (equivalent to unordered_map in C++) for efficient lookups. The time complexity of the solution is O(n^2). Here 'n' is the number of transactions and we iterate over each transaction twice to check for both conditions stated in the problem.

Java Solution

1
2java
3import java.util.*;
4
5class Transaction {
6    String name;
7    int time;
8    int amount;
9    String city;
10
11    Transaction(String name, int time, int amount, String city) {
12        this.name = name;
13        this.time = time;
14        this.amount = amount;
15        this.city = city;
16    }
17}
18
19class Solution {
20    public List<String> invalidTransactions(String[] transactions) {
21        Map<String, List<Transaction>> map = new HashMap<>();
22        List<String> invalidTransactions = new ArrayList<>();
23
24        for (String t : transactions) {
25            String[] s = t.split(",");
26            Transaction transaction = new Transaction(s[0], Integer.parseInt(s[1]), Integer.parseInt(s[2]), s[3]);
27            map.putIfAbsent(transaction.name, new ArrayList<>());
28            map.get(transaction.name).add(transaction);
29
30            if (transaction.amount > 1000)
31                invalidTransactions.add(t);
32        }
33
34        for (String t : transactions) {
35            String[] s = t.split(",");
36            Transaction transaction = new Transaction(s[0], Integer.parseInt(s[1]), Integer.parseInt(s[2]), s[3]);
37
38            if (map.get(transaction.name).stream().anyMatch(x -> Math.abs(x.time - transaction.time) <= 60 && !x.city.equals(transaction.city))) {
39                invalidTransactions.add(t);
40            }
41        }
42
43        return invalidTransactions;
44    }
45}

Similar to the Python solution, the Java solution also makes use of a hashmap for efficient lookups. The time complexity of the solution is the same, i.e., O(n^2).

Javascript Solution

Now let's solve this problem in JavaScript. The approach remains similar but the syntax varies as per the language.

1
2javascript
3class Transaction {
4    constructor(name, time, amount, city) {
5        this.name = name;
6        this.time = time;
7        this.amount = amount;
8        this.city = city;
9    }
10}
11
12var invalidTransactions = function(transactions) {
13    const nameToTrans = new Map();
14    const invalid = [];
15
16    transactions.forEach(trans => {
17        const [name, time, amount, city] = trans.split(',');
18        const t = new Transaction(name, parseInt(time), parseInt(amount), city);
19
20        if (!nameToTrans.has(name)) {
21            nameToTrans.set(name, []);
22        }
23        nameToTrans.get(name).push(t);
24
25        if (t.amount > 1000) {
26            invalid.push(trans);
27        }
28    });
29
30    transactions.forEach(trans => {
31        const [name, time, amount, city] = trans.split(',');
32        const t = new Transaction(name, parseInt(time), parseInt(amount), city);
33
34        if (nameToTrans.get(name).some(tt => Math.abs(tt.time - t.time) <= 60 && tt.city !== city)) {
35            invalid.push(trans);
36        }
37    });
38
39    return Array.from(new Set(invalid)); // remove duplicates and return
40};

As seen in the Python and Java solutions, the JavaScript solution also utilizes a Map for efficient lookups. However, unlike Python and Java, JavaScript does not have a predefined standard class with a 'stream' or 'any' method. Instead, we use 'some', a JavaScript array method that tests whether at least one element in the array passes the testing function.

The time complexity remains the same, O(n^2). Here 'n' is the number of transactions. We iterate over each transaction twice to verify for both conditions stated in the problem.

With these solutions in Python, Java, and JavaScript, we have now covered how to tackle this problem in some of the most commonly used programming languages. The provided solutions are efficient and should stand the test of most transaction lists. However, if the list of transactions is extremely large, a more efficient approach may be needed.