Algorithm
Problem Name: 1169. Invalid Transactions
Problem Link: https://leetcode.com/problems/invalid-transactions/
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.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List invalidTransactions(String[] transactions) {
Set invalidTransactionSet = new HashSet<>();
Map> map = new HashMap<>();
Map transactionOccurenceCount = new HashMap<>();
for (String transactionString : transactions) {
transactionOccurenceCount.put(transactionString, transactionOccurenceCount.getOrDefault(transactionString, 0) + 1);
String[] transaction = transactionString.split(",");
String name = transaction[0];
int amount = Integer.parseInt(transaction[2]);
String city = transaction[3];
int time = Integer.parseInt(transaction[1]);
if (amount > 1000) {
invalidTransactionSet.add(transactionString);
}
map.computeIfAbsent(name, k -> new ArrayList<>());
List currentTransactions = map.get(name);
for (String currentTransaction : currentTransactions) {
String currentCity = currentTransaction.split(",")[3];
int currentTime = Integer.parseInt(currentTransaction.split(",")[1]);
if (!currentCity.equals(city) && Math.abs(time - currentTime) <= 60) {
invalidTransactionSet.add(currentTransaction);
invalidTransactionSet.add(transactionString);
}
}
currentTransactions.add(transactionString);
map.put(name, currentTransactions);
}
List result = new ArrayList<>();
for (String trs : invalidTransactionSet) {
int count = transactionOccurenceCount.get(trs);
while (count-- > 0) {
result.add(trs);
}
}
return result;
}
}
Input
transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output
["alice,20,800,mtv","alice,50,100,beijing"]
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def invalidTransactions(self, transactions: List[str]) -> List[str]:
last = collections.defaultdict(list)
ret = set()
for n, t, a, c in sorted([t.split(',') for t in transactions], key = lambda x: int(x[1])):
if int(a) > 1000:
ret.add(','.join([n, t, a, c]))
if n in last:
for tt, aa, cc in last[n][::-1]:
if int(t) - int(tt) > 60:
break
if cc != c:
ret.add(','.join([n, tt, aa, cc]))
ret.add(','.join([n, t, a, c]))
last[n].append([t, a, c])
return list(ret)
Input
transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output
["alice,20,800,mtv","alice,50,100,beijing"]