| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
Medium |
1658 |
Weekly Contest 151 Q1 |
|
A transaction is possibly invalid if:
- the amount exceeds
$1000, or; - if it occurs within (and including)
60minutes 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.
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.
We traverse the transaction list. For each transaction, if the amount is greater than 1000, or if the transaction has the same name but different cities and the time interval does not exceed 60 minutes, then add it to the answer.
Specifically, we use a hash table d to record each transaction, where the key is the transaction name, and the value is a list. Each element in the list is a tuple (time, city, index), indicating that a transaction with the number index was conducted in the city city at the moment time. At the same time, we use a hash table idx to record the transaction number in the answer.
We traverse the transaction list. For each transaction, we first add it to the hash table d, and then judge whether its amount is greater than 1000. If so, add its number to the answer. Then we traverse the transactions in the hash table d. If the transaction names are the same but the cities are different and the time interval does not exceed 60 minutes, add its number to the answer.
Finally, we traverse the transaction numbers in the answer and add the corresponding transactions to the answer.
The time complexity is
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]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;
}
}class Solution {
public:
vector<string> invalidTransactions(vector<string>& transactions) {
unordered_map<string, vector<tuple<int, string, int>>> d;
unordered_set<int> idx;
for (int i = 0; i < transactions.size(); ++i) {
vector<string> e = split(transactions[i], ',');
string name = e[0];
int time = stoi(e[1]);
int amount = stoi(e[2]);
string city = e[3];
d[name].push_back({time, city, i});
if (amount > 1000) {
idx.insert(i);
}
for (auto& [t, c, j] : d[name]) {
if (c != city && abs(time - t) <= 60) {
idx.insert(i);
idx.insert(j);
}
}
}
vector<string> ans;
for (int i : idx) {
ans.emplace_back(transactions[i]);
}
return ans;
}
vector<string> split(string& s, char delim) {
stringstream ss(s);
string item;
vector<string> res;
while (getline(ss, item, delim)) {
res.emplace_back(item);
}
return res;
}
};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
}