Practice/Bloomberg/Leetcode 1169. Invalid Transactions

Leetcode 1169. Invalid Transactions

CodingMust

Problem

You work for a financial institution's fraud detection team. You need to identify potentially fraudulent transactions based on two criteria:

1. High Amount: Any transaction with an amount exceeding $1000 is considered suspicious
2. Impossible Travel: If the same person makes transactions in two different cities within 60 minutes (inclusive), both transactions are flagged as suspicious

Given an array of transaction records, return all transactions that meet at least one of these fraud criteria.

Each transaction is represented as a comma-separated string with the format: "name,time,amount,city" where:

• name is the person's name (string)
• time is the timestamp in minutes (integer)
• amount is the transaction amount in dollars (integer)
• city is the city where the transaction occurred (string)

Requirements

1. A transaction is invalid if its amount is strictly greater than 1000
2. A transaction is invalid if there exists another transaction with the same name that occurred in a different city within 60 minutes (the time difference is less than or equal to 60)
3. Return the invalid transactions in any order, formatted as they appeared in the input
4. If a transaction is flagged by either rule, it should appear in the result

Constraints

• 1 ≤ transactions.length ≤ 1000
• Each transaction string follows the format "name,time,amount,city"
• 0 ≤ time ≤ 10000
• 0 ≤ amount ≤ 10000
• Name and city consist of lowercase English letters
• If a transaction is invalid for multiple reasons, it should still only appear once in the output

Examples

Example 1:

Input: ["alice,20,800,mtv", "alice,50,100,beijing"] Output: ["alice,20,800,mtv", "alice,50,100,beijing"] Explanation: Both transactions are for alice, occur 30 minutes apart (20 and 50), and are in different cities (mtv vs beijing). This triggers the impossible travel rule.

Example 2:

Input: ["bob,1,1500,denver"] Output: ["bob,1,1500,denver"] Explanation: The amount 1500 exceeds the 1000 threshold.

Example 3:

Input: ["charlie,10,500,sf", "charlie,70,400,sf"] Output: [] Explanation: Both transactions are in the same city and amounts are under 1000. The 60-minute time difference only matters for different cities.

Example 4:

Input: ["alice,1,100,nyc", "bob,2,200,la", "alice,50,300,chicago"] Output: ["alice,1,100,nyc", "alice,50,300,chicago"] Explanation: Alice's two transactions are 49 minutes apart in different cities, making both invalid. Bob's transaction is unrelated and valid.