#1169

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Invalid Transactions

Detect invalid transactions by scanning arrays and cross-checking with hash tables for time, amount, and city conflicts efficiently.

array hash table string sorting

Problem Statement

You are given an array of strings transactions where each string represents a transaction in the format "name,time,amount,city". A transaction is considered possibly invalid if the amount exceeds 1000 or if there is another transaction with the same name that occurs within 60 minutes in a different city.

Return an array of all possibly invalid transactions. Each transaction in the output should exactly match the input string, and the order of results does not matter.

Examples

Example 1

Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]

Output: ["alice,20,800,mtv","alice,50,100,beijing"]

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 details omitted.

Example 3

Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]

Output: ["bob,50,1200,mtv"]

Example details omitted.

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 between 1 and 10.
Each {time} consist of digits, and represent an integer between 0 and 1000.
Each {amount} consist of digits, and represent an integer between 0 and 2000.

Solution Approach

Split and Parse Transactions

Convert each transaction string into a structured object with fields for name, time, amount, and city. This allows direct access for comparisons and prepares data for hash lookup and array scanning patterns.

Use Hash Table for Name-based Lookup

Maintain a hash table mapping each name to a list of previous transactions. For each new transaction, scan the hash table to detect time conflicts in different cities and simultaneously check the amount condition. This efficiently captures the core invalid transaction patterns.

Iterate and Collect Results

Traverse the entire transactions array and apply the validation rules. Append any transaction exceeding 1000 or conflicting in time and city to the result list. This ensures completeness without missing any cross-city conflicts within 60 minutes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) in the worst case due to pairwise comparisons per name, but splitting and hash lookups reduce overhead. Space complexity is O(n) for storing transactions per name in hash tables.

What Interviewers Usually Probe

Checks if you can efficiently scan arrays while tracking past transactions with hash maps.
Wants you to correctly handle both amount threshold and cross-city time conflicts simultaneously.
May probe about optimizing nested loops or reducing redundant comparisons per user.

Common Pitfalls or Variants

Common pitfalls

Forgetting to compare transactions only with the same name, causing false positives.
Ignoring the 60-minute window or miscalculating the difference between transaction times.
Failing to preserve the original transaction string in the output while returning results.

Follow-up variants

Identify invalid transactions with a dynamic threshold instead of fixed 1000 amount.
Handle transactions across multiple cities with variable time windows.
Return transactions grouped by user instead of a flat list for further processing.

FAQ

What defines an invalid transaction in this problem?

A transaction is invalid if the amount exceeds 1000 or if another transaction with the same name occurs within 60 minutes in a different city.

How does the array scanning plus hash lookup pattern apply here?

Each transaction is scanned and compared against prior transactions stored in a hash table keyed by name, enabling quick detection of cross-city and time conflicts.

Can the output order differ from input?

Yes, the problem allows returning invalid transactions in any order as long as the strings match the original input.

What is the expected complexity?

Time complexity is worst-case O(n^2) per name due to pairwise checks, and space complexity is O(n) for storing transactions in hash tables.

How should ties within the 60-minute window be handled?

All transactions within 60 minutes across different cities for the same name should be marked invalid regardless of which appears first.

terminal

Solution

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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]

Continue Practicing

#1170 compare strings by frequency of the smallest character #1202 smallest string with swaps #1048 longest string chain