Invalid Transactions

Medium

Asked by:

94 views

Topics:

ArraysStringsTwo Pointers

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of transactions and the length of each transaction string?
Are the time values always non-negative integers? What is the possible range for the time?
Can transaction amounts be non-integer values, and can they be negative? What is the expected behavior for zero-amount transactions?
If multiple transactions from the same name occur within 60 minutes of each other but in different cities, are *all* of them marked invalid, or only the ones within 60 minutes of another different-city transaction?
What should be the order of the invalid transactions in the returned list? Should they be sorted based on time or the order they appear in the input?

Brute Force Solution

Approach

The brute force method for finding invalid transactions involves checking every transaction against all other transactions to see if it is invalid. We'll compare each transaction against the others based on the rules for determining invalidity. Transactions are flagged as invalid if they violate these rules.

Here's how the algorithm would work step-by-step:

Take the first transaction from the list.
Compare this transaction to every other transaction in the list.
Check if any other transaction has the same name, but a different city, and occurs within a certain timeframe (e.g., one hour) of the first transaction.
If such a transaction exists, mark the first transaction as invalid.
Also check if the transaction amount exceeds a certain threshold. If it does, mark the transaction as invalid.
Repeat this process (comparing to all other transactions and the amount threshold) for every transaction in the original list.
After comparing each transaction to all others and the amount threshold, collect all transactions flagged as invalid.

Code Implementation

def find_invalid_transactions_brute_force(transactions):
    invalid_transactions = []
    number_of_transactions = len(transactions)

    for i in range(number_of_transactions):
        current_transaction = transactions[i].split(',')
        current_transaction_name = current_transaction[0]
        current_transaction_time = int(current_transaction[1])
        current_transaction_amount = int(current_transaction[2])
        current_transaction_city = current_transaction[3]

        is_valid = True

        # Check if the transaction amount exceeds the threshold.
        if current_transaction_amount > 1000:
            is_valid = False

        for j in range(number_of_transactions):
            if i == j:
                continue

            other_transaction = transactions[j].split(',')
            other_transaction_name = other_transaction[0]
            other_transaction_time = int(other_transaction[1])
            other_transaction_city = other_transaction[3]

            # Check for name collision in different cities within one hour.
            if (current_transaction_name == other_transaction_name and\
                    current_transaction_city != other_transaction_city and\
                    abs(current_transaction_time - other_transaction_time) <= 60):
                is_valid = False
                break

        if not is_valid:
            invalid_transactions.append(transactions[i])

    return invalid_transactions

Big(O) Analysis

Time Complexity

O(n²) – The provided approach iterates through each of the n transactions in the input list. For each transaction, it compares it against every other transaction in the list to check for invalidity based on name, city, and time. This nested iteration results in approximately n comparisons for each of the n transactions. Therefore, the total number of operations scales roughly as n * n, which simplifies to O(n²).

Space Complexity

O(N) – The described algorithm involves identifying and collecting invalid transactions. In the worst-case scenario, every transaction could be flagged as invalid, requiring us to store all N transactions in a list to hold the invalid ones. Therefore, the algorithm requires auxiliary space proportional to the number of transactions, N, to store the potentially invalid transactions. This results in O(N) space complexity.

Optimal Solution

Approach

The goal is to find transactions that are either too large in amount or happen too close in time or location to other transactions by the same person. We can do this efficiently by organizing the transactions and then checking for invalid ones.

Here's how the algorithm would work step-by-step:

First, group all the transactions by the person who made them. This way, we only compare transactions made by the same person.
For each person, sort their transactions by time. This makes it easy to check if transactions are close together in time.
Go through each person's sorted transactions one by one.
For each transaction, check if its amount is greater than a certain limit. If it is, mark it as invalid.
For each transaction, check if there are any other transactions by the same person within a certain time range (before and after).
If any transaction within that time range has a different location, mark both the current transaction and the other transaction as invalid.
After checking all transactions, return the list of transactions that were marked as invalid.

Code Implementation

def invalid_transactions(transactions):
    transactions_by_name = {}
    invalid_transactions_list = []

    for transaction in transactions:
        name, time, amount, city = transaction.split(',')
        time = int(time)
        amount = int(amount)

        if name not in transactions_by_name:
            transactions_by_name[name] = []
        transactions_by_name[name].append([time, amount, city, transaction])

    for name in transactions_by_name:
        transactions_by_name[name].sort()

        transaction_list = transactions_by_name[name]

        for i in range(len(transaction_list)):
            time, amount, city, transaction = transaction_list[i]

            # Flag transactions exceeding the amount limit as invalid.
            if amount > 1000:
                invalid_transactions_list.append(transaction)

            # Iterate through other transactions to check proximity
            for j in range(len(transaction_list)):
                if i == j:
                    continue

                other_time, other_amount, other_city, other_transaction = transaction_list[j]

                # Check if transactions are within the time limit and different cities.
                if abs(time - other_time) <= 60 and city != other_city:
                    if transaction not in invalid_transactions_list:
                        invalid_transactions_list.append(transaction)
                    if other_transaction not in invalid_transactions_list:
                        invalid_transactions_list.append(other_transaction)

    return invalid_transactions_list

Big(O) Analysis

Time Complexity

O(n log n) – Grouping transactions by person can be done in O(n) time using a hash map. Sorting each person's transactions by time takes O(k log k) where k is the number of transactions for that person. In the worst case, one person has all n transactions, resulting in O(n log n). Iterating through the sorted transactions for each person involves checking for amount limits (O(1)) and comparing locations within a time range. In the worst case, for each transaction, we might need to check all other transactions for the same person within the time range, taking O(n) in the worst case for a single person (although this check benefits from the time-sorted order, making it closer to constant on average). Since sorting dominates this cost, the overall time complexity is approximately O(n log n).

Space Complexity

O(N) – The primary space complexity comes from grouping transactions by person, potentially requiring a hash map or similar data structure to store each person and their associated transactions. In the worst-case scenario, each transaction could be from a different person. This grouping would then need to store all N transactions. Sorting each person's transactions uses in-place sorts, but the auxiliary space for the grouping dominates. The list of invalid transactions also contributes O(N) space in the worst case where all transactions are invalid. Therefore, the overall space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty transactions array	Return an empty list since there are no transactions to validate.
Transaction string is malformed (missing fields, incorrect format)	Handle parsing errors gracefully, possibly skipping the invalid transaction string and logging the error or returning an error result.
Time values are negative or extremely large	Validate the time value range and handle out-of-bounds values, likely skipping the transaction or adjusting the timestamp.
Amount is zero or negative	Consider amount <= 0 as valid or invalid based on problem requirements; if invalid, flag the transaction.
A very large number of transactions with the same name	Ensure the data structure used to store transactions for a given name doesn't cause a performance bottleneck (e.g., use a balanced tree or hash map for efficient lookups).
Two transactions by the same person, different cities, at the same exact time	This should be treated as invalid according to the problem statement.
Transactions are already sorted by time	The solution should still work correctly and efficiently, avoiding unnecessary sorting if it's not required by the chosen approach.
Integer overflow when calculating time differences	Use long data type for storing and calculating time differences to prevent overflow.

Null or empty transactions array

How to Handle:

Return an empty list since there are no transactions to validate.

Transaction string is malformed (missing fields, incorrect format)

How to Handle:

Handle parsing errors gracefully, possibly skipping the invalid transaction string and logging the error or returning an error result.

Time values are negative or extremely large

How to Handle:

Validate the time value range and handle out-of-bounds values, likely skipping the transaction or adjusting the timestamp.

Amount is zero or negative

How to Handle:

Consider amount <= 0 as valid or invalid based on problem requirements; if invalid, flag the transaction.

A very large number of transactions with the same name

How to Handle:

Ensure the data structure used to store transactions for a given name doesn't cause a performance bottleneck (e.g., use a balanced tree or hash map for efficient lookups).

Two transactions by the same person, different cities, at the same exact time

How to Handle:

This should be treated as invalid according to the problem statement.

Transactions are already sorted by time

How to Handle:

The solution should still work correctly and efficiently, avoiding unnecessary sorting if it's not required by the chosen approach.

Integer overflow when calculating time differences

How to Handle:

Use long data type for storing and calculating time differences to prevent overflow.