Formatted question description: https://leetcode.ca/all/1169.html

# 1169. Invalid Transactions (Medium)

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.

Each transaction string transactions[i] consists of comma separated values representing the name, time (in minutes), amount, and city of the transaction.

Given a list of transactions, 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 between 1 and 10.
• Each {time} consist of digits, and represent an integer between 0 and 1000.
• Each {amount} consist of digits, and represent an integer between 0 and 2000.

Related Topics:
Array, String

## Solution 1. Brute force

// OJ: https://leetcode.com/problems/invalid-transactions/

// Time: O(N^2)
// Space: O(N)
struct Transaction {
string name;
int time;
int amount;
string city;
Transaction(string t) {
istringstream ss(t);
getline(ss, name, ',');
string token;
getline(ss, token, ',');
time = stoi(token);
getline(ss, token, ',');
amount = stoi(token);
ss >> city;
}
};
class Solution {
public:
vector<string> invalidTransactions(vector<string>& A) {
vector<Transaction> B;
unordered_set<int> invalid;
for (int i = 0; i < A.size(); ++i) {
auto t = Transaction(A[i]);
if (t.amount > 1000) invalid.insert(i);
B.push_back(t);
}
for (int i = 0; i < A.size(); ++i) {
for (int j = i + 1; j < A.size(); ++j) {
if (B[i].name == B[j].name && abs(B[i].time - B[j].time) <= 60 && B[i].city != B[j].city) {
invalid.insert(i);
invalid.insert(j);
}
}
}
vector<string> ans;
for (int i : invalid) ans.push_back(A[i]);
return ans;
}
};


## Solution 1. Sliding Window

// OJ: https://leetcode.com/problems/invalid-transactions/

// Time: O(NlogN)
// Space: O(N)
struct Transaction {
string name;
int time;
int amount;
string city;
Transaction(string t) {
istringstream ss(t);
getline(ss, name, ',');
string token;
getline(ss, token, ',');
time = stoi(token);
getline(ss, token, ',');
amount = stoi(token);
ss >> city;
}
};
class Solution {
public:
vector<string> invalidTransactions(vector<string>& A) {
unordered_map<string, vector<int>> m;
vector<Transaction> B;
unordered_set<int> invalid;
for (int i = 0; i < A.size(); ++i) {
auto t = Transaction(A[i]);
if (t.amount > 1000) invalid.insert(i);
m[t.name].push_back(i);
B.push_back(t);
}
for (auto &[p, ids] : m) {
sort(begin(ids), end(ids), [&](int a, int b) { return B[a].time < B[b].time; });
int i = 0, j = 0, k = 0, N = ids.size();
unordered_map<string, int> cities;
while (j < N) {
while (B[ids[j]].time - B[ids[i]].time > 60) {
auto &c = B[ids[i++]];
if (--cities[c.city] == 0) cities.erase(c.city);
}
if (B[ids[j]].time - B[ids[i]].time <= 60) {
auto &c = B[ids[j++]];
cities[c.city]++;
if (cities.size() > 1) {
for (k = max(k, i); k < j; ++k) invalid.insert(ids[k]);
}
}
}
}
vector<string> ans;
for (int i : invalid) ans.push_back(A[i]);
return ans;
}
};


Java

class Solution {
public List<String> invalidTransactions(String[] transactions) {
int length = transactions.length;
Transaction[] transactionsArray = new Transaction[length];
for (int i = 0; i < length; i++) {
String transactionStr = transactions[i];
String[] array = transactionStr.split(",");
String name = array;
int time = Integer.parseInt(array);
int amount = Integer.parseInt(array);
String city = array;
Transaction curTransaction = new Transaction(name, time, amount, city);
transactionsArray[i] = curTransaction;
}
Arrays.sort(transactionsArray);
Set<String> invalidSet = new HashSet<String>();
Transaction transaction0 = transactionsArray;
if (transaction0.amount > 1000)
int prevIndex = 0;
for (int i = 1; i < length; i++) {
Transaction curTransaction = transactionsArray[i];
if (curTransaction.amount > 1000)
while (!transactionsArray[prevIndex].name.equals(curTransaction.name) || curTransaction.time - transactionsArray[prevIndex].time > 60)
prevIndex++;
boolean flag = false;
for (int j = prevIndex; j < i; j++) {
Transaction prevTransaction = transactionsArray[j];
if (curTransaction.name.equals(prevTransaction.name) && curTransaction.time - prevTransaction.time <= 60 && !curTransaction.city.equals(prevTransaction.city)) {
flag = true;
}
}
if (flag)
}
List<String> invalidTransactionsList = new ArrayList<String>(invalidSet);
return invalidTransactionsList;
}
}

class Transaction implements Comparable<Transaction> {
String name;
int time;
int amount;
String city;

public Transaction(String name, int time, int amount, String city) {
this.name = name;
this.time = time;
this.amount = amount;
this.city = city;
}

public int compareTo(Transaction transaction2) {
if (!this.name.equals(transaction2.name))
return this.name.compareTo(transaction2.name);
else if (this.time != transaction2.time)
return this.time - transaction2.time;
else if (!this.city.equals(transaction2.city))
return this.city.compareTo(transaction2.city);
else
return this.amount - transaction2.amount;
}

public String toString() {
return name + "," + time + "," + amount + "," + city;
}
}