Welcome to Subscribe On Youtube
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 between1and10. - Each
{time}consist of digits, and represent an integer between0and1000. - Each
{amount}consist of digits, and represent an integer between0and2000.
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;
}
};
-
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[0]; int time = Integer.parseInt(array[1]); int amount = Integer.parseInt(array[2]); String city = array[3]; Transaction curTransaction = new Transaction(name, time, amount, city); transactionsArray[i] = curTransaction; } Arrays.sort(transactionsArray); Set<String> invalidSet = new HashSet<String>(); Transaction transaction0 = transactionsArray[0]; if (transaction0.amount > 1000) invalidSet.add(transaction0.toString()); int prevIndex = 0; for (int i = 1; i < length; i++) { Transaction curTransaction = transactionsArray[i]; if (curTransaction.amount > 1000) invalidSet.add(curTransaction.toString()); 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)) { invalidSet.add(prevTransaction.toString()); flag = true; } } if (flag) invalidSet.add(curTransaction.toString()); } 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; } } ############ class Solution { public List<String> invalidTransactions(String[] transactions) { Map<String, List<Item>> d = new HashMap<>(); Set<Integer> idx = new HashSet<>(); for (int i = 0; i < transactions.length; ++i) { var e = transactions[i].split(","); String name = e[0]; int time = Integer.parseInt(e[1]); int amount = Integer.parseInt(e[2]); String city = e[3]; d.computeIfAbsent(name, k -> new ArrayList<>()).add(new Item(time, city, i)); if (amount > 1000) { idx.add(i); } for (Item item : d.get(name)) { if (!city.equals(item.city) && Math.abs(time - item.t) <= 60) { idx.add(i); idx.add(item.i); } } } List<String> ans = new ArrayList<>(); for (int i : idx) { ans.add(transactions[i]); } return ans; } } class Item { int t; String city; int i; Item(int t, String city, int i) { this.t = t; this.city = city; this.i = i; } } -
// 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; } }; -
class Solution: def invalidTransactions(self, transactions: List[str]) -> List[str]: d = defaultdict(list) idx = set() for i, x in enumerate(transactions): name, time, amount, city = x.split(",") time, amount = int(time), int(amount) d[name].append((time, city, i)) if amount > 1000: idx.add(i) for t, c, j in d[name]: if c != city and abs(time - t) <= 60: idx.add(i) idx.add(j) return [transactions[i] for i in idx] ############ # 1169. Invalid Transactions # https://leetcode.com/problems/invalid-transactions/ class Solution: def invalidTransactions(self, transactions: List[str]) -> List[str]: ans = [] length = len(transactions) if not length: return ans name,time,money,city = [],[],[],[] add = [1] * length for trans in transactions: tran = trans.split(',') name.append(tran[0]) time.append(int(tran[1])) money.append(int(tran[2])) city.append(tran[3]) for i in range(length): if money[i] > 1000: add[i] = False for j in range(i+1,length): if name[i] == name[j] and abs(time[i]-time[j])<= 60 and city[i]!=city[j]: add[i] = False add[j] = False for ind,val in enumerate(add): if not val: ans.append(transactions[ind]) return ans -
func invalidTransactions(transactions []string) (ans []string) { d := map[string][]tuple{} idx := map[int]bool{} for i, x := range transactions { e := strings.Split(x, ",") name := e[0] time, _ := strconv.Atoi(e[1]) amount, _ := strconv.Atoi(e[2]) city := e[3] d[name] = append(d[name], tuple{time, city, i}) if amount > 1000 { idx[i] = true } for _, item := range d[name] { if city != item.city && abs(time-item.t) <= 60 { idx[i], idx[item.i] = true, true } } } for i := range idx { ans = append(ans, transactions[i]) } return } func abs(x int) int { if x < 0 { return -x } return x } type tuple struct { t int city string i int }