1169. Invalid Transactions
Description
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.
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 between1
and10
. - Each
{time}
consist of digits, and represent an integer between0
and1000
. - Each
{amount}
consist of digits, and represent an integer between0
and2000
.
Solutions
Solution 1: Hash Table + Simulation
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 $O(n^2)$, and the space complexity is $O(n)$. Here, $n$ is the length of the transaction list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
|