# Invalid Transactions LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple BloombergViews 24

## Problem Statement

Invalid Transactions LeetCode Solution – A transaction is possibly invalid if:

• the amount exceeds `\$1000`, or;
• if it occurs within (and including) `60` minutes 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.

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

## Explanation

### Bruteforce Approach:

The basic idea is to create a set to remove possible duplicates when looking at the two different (\$1000 and within 60 minutes in a different city) invalid conditions. Then just brute force it by iteratively comparing every transaction with all the other transactions. This is extremely easy to do, but not optimal.

### Optimized Approach:

1. Create a `transaction` data structure so the attributes can easily be queried and stored in a `transactions` array
2. Sort the `transactions` array-based on `time`
3. Iterate through the `transactions` array and create a hash table/dictionary with `name` as the key, and an array of `transaction indexes` as the value.
4. Iterate through the dictionary and loop through the `name` specific `transaction indexes` array.
• Over `1000` dollars check: If the current transaction `amount` is greater than `1000`, then add to the `res` and continue to the next transaction.
• Within `60` minutes check: Use left, and right pointers to represent the possible neighbor transactions that are within the `60` minutes.
• If the current transaction has any neighbors within the `60` minutes then check if the city is different. If so, add to the `res` and continue to the next transactions.

1 We need to sort the transactions by time, so a function convert string to a customized struct is required.
2 To reduce the effort of compare of transactions, we use unordered_map to classify them by name.
3 To generate the result easily, we add the input string and a bool flag to the struct, with other info in the transactions we get the 6-member struct design.
4 To reach better performance, we can do sort only for transactions from the same name.

## Code

### C++ Code for Invalid Transaction

```class Solution {
public:
struct CustomerDetail{
string name;
int time;
int amount;
string city;
};
CustomerDetail prepareCustomerObject(string s){
vector<string>temp;
string t;
istringstream f(s);
while(getline(f,t,',')){
temp.push_back(t);
}
CustomerDetail obj =  CustomerDetail();
obj.name=temp;
obj.time=stoi(temp);
obj.amount=stoi(temp);
obj.city=temp;
return obj;
}
vector<string> invalidTransactions(vector<string>& transactions) {
vector<bool> invalid(transactions.size());
vector<CustomerDetail> details;
map<string/*name*/,vector<int>/*list of indexes*/> hashmap;
int i=0;
for(string s: transactions) {
CustomerDetail obj = prepareCustomerObject(s);
invalid[i]=obj.amount>1000;

if(hashmap.find(obj.name) != hashmap.end()) {
vector<int> indexes = hashmap[obj.name];

for(int ind: indexes) {
if(details[ind].city != obj.city && abs(obj.time-details[ind].time)<= 60) {
invalid[ind]=true;
invalid[i]=true;
}
}
}
hashmap[obj.name].push_back(i);
details.push_back(obj);
i++;
}
vector<string> ans;
for(i=0;i<transactions.size();i++){
if(invalid[i])
ans.push_back(transactions[i]);
}
return ans;
}
};```

### Java Code for Invalid Transaction

```class Solution {
public List<String> invalidTransactions(final String[] transactions) {
final List<String> invalid = new ArrayList<>();
final Map<String, List<Transaction>> map = new HashMap<>();

/*
* build a map with name as key and value as list of transactions for that name
*/
for (final String transaction : transactions) {
final Transaction tran = new Transaction(transaction);

if (map.containsKey(tran.name)) {
} else {
final List<Transaction> list = new ArrayList<>();
map.put(tran.name, list);
}
}

for (final String transaction : transactions) {
final Transaction tran = new Transaction(transaction);

if (!isValid(map.get(tran.name), tran)) {
}

}

return invalid;
}

public boolean isValid(final List<Transaction> transactions, final Transaction transaction) {

/* if there is only one transaction and the amount is less than 1000 */
if (transactions.size() <= 1 && transaction.amount < 1000)
return true;

/* check against all other transaction to check it this one is valid */
for (final Transaction tran : transactions) {
if (transaction.invalidTransaction(tran.city, tran.time)) {
return false;
}
}
return true;
}

class Transaction {
String name;
int time;
int amount;
String city;

Transaction(final String transaction) {
final String[] t = transaction.split(",");
this.name = t;
this.time = Integer.parseInt(t);
this.amount = Integer.parseInt(t);
this.city = t;
}

/*
* the amount exceeds \$1000, or;
*
* if it occurs within (and including) 60 minutes of another transaction with
* the same name in a different city. Each transaction string transactions[i]
* consists of comma separated values representing the name, time (in minutes),
* amount, and city of the transaction.
*/
public boolean invalidTransaction(final String city, final int time) {
return invalidAmount() || differentCity(city, time);
}

private boolean differentCity(final String city, final int time) {
return !this.city.equals(city) && Math.abs(this.time - time) <= 60;
}

private boolean invalidAmount() {
return this.amount > 1000;
}
}
}```

### Python Code for Invalid Transaction

```class Transaction:
def __init__(self, name, time, amount, city):
self.name = name
self.time = int(time)
self.amount = int(amount)
self.city = city

from collections import defaultdict
class Solution:
def invalidTransactions(self, transactions):
transactions = [Transaction(*transaction.split(',')) for transaction in transactions]
transactions.sort(key=lambda t: t.time) # O(nlogn) time

trans_indexes = defaultdict(list)
for i, t in enumerate(transactions): # O(n) time
trans_indexes[t.name].append(i)

res = []
for name, indexes in trans_indexes.items(): # O(n) time
left = right = 0
for i, t_index in enumerate(indexes):
t = transactions[t_index]
if (t.amount > 1000):
res.append("{},{},{},{}".format(t.name, t.time, t.amount, t.city))
continue
while left <= len(indexes)-2 and transactions[indexes[left]].time < t.time - 60: # O(60) time
left += 1
while right <= len(indexes)-2 and transactions[indexes[right+1]].time <= t.time + 60: # O(60) time
right += 1
for i in range(left,right+1): # O(120) time
if transactions[indexes[i]].city != t.city:
res.append("{},{},{},{}".format(t.name, t.time, t.amount, t.city))
break

return res```

## Complexity Analysis for Invalid Transactions LeetCode Solution

O(NLogN)

### Space Complexity

O(1) as we are not using any extra space.

Reference: https://en.wikipedia.org/wiki/Hash_table

Translate »