Code Implementation

class Solution:
    def invalidTransactions(self, transactions):
        parsed = []
        for t in transactions:
            name, time, amount, city = t.split(",")
            parsed.append({
                'name': name,
                'time': int(time),
                'amount': int(amount),
                'city': city,
                'raw': t
            })
        n = len(parsed)
        invalid = set()
        for i in range(n):
            t1 = parsed[i]
            # Rule 1: amount > 1000
            if t1['amount'] > 1000:
                invalid.add(t1['raw'])
            # Rule 2: within 60 min, same name, different city
            for j in range(n):
                if i == j:
                    continue
                t2 = parsed[j]
                if t1['name'] == t2['name'] and t1['city'] != t2['city'] and abs(t1['time'] - t2['time']) <= 60:
                    invalid.add(t1['raw'])
        return list(invalid)
      

class Solution {
public:
    vector<string> invalidTransactions(vector<string>& transactions) {
        struct Tx {
            string name, city, raw;
            int time, amount;
        };
        vector<Tx> parsed;
        for (const string& s : transactions) {
            stringstream ss(s);
            string name, time, amount, city;
            getline(ss, name, ',');
            getline(ss, time, ',');
            getline(ss, amount, ',');
            getline(ss, city, ',');
            parsed.push_back({name, city, s, stoi(time), stoi(amount)});
        }
        int n = parsed.size();
        unordered_set<string> invalid;
        for (int i = 0; i < n; ++i) {
            // Rule 1
            if (parsed[i].amount > 1000)
                invalid.insert(parsed[i].raw);
            // Rule 2
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                if (parsed[i].name == parsed[j].name && parsed[i].city != parsed[j].city
                    && abs(parsed[i].time - parsed[j].time) <= 60)
                    invalid.insert(parsed[i].raw);
            }
        }
        return vector<string>(invalid.begin(), invalid.end());
    }
};
      

class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        class Tx {
            String name, city, raw;
            int time, amount;
            Tx(String n, int t, int a, String c, String r) {
                name = n; time = t; amount = a; city = c; raw = r;
            }
        }
        List<Tx> parsed = new ArrayList<>();
        for (String s : transactions) {
            String[] arr = s.split(",");
            parsed.add(new Tx(arr[0], Integer.parseInt(arr[1]), Integer.parseInt(arr[2]), arr[3], s));
        }
        int n = parsed.size();
        Set<String> invalid = new HashSet<>();
        for (int i = 0; i < n; ++i) {
            Tx t1 = parsed.get(i);
            if (t1.amount > 1000)
                invalid.add(t1.raw);
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                Tx t2 = parsed.get(j);
                if (t1.name.equals(t2.name) && !t1.city.equals(t2.city)
                    && Math.abs(t1.time - t2.time) <= 60)
                    invalid.add(t1.raw);
            }
        }
        return new ArrayList<>(invalid);
    }
}
      

var invalidTransactions = function(transactions) {
    let parsed = transactions.map(t => {
        let [name, time, amount, city] = t.split(',');
        return {
            name: name,
            time: parseInt(time),
            amount: parseInt(amount),
            city: city,
            raw: t
        }
    });
    let n = parsed.length;
    let invalid = new Set();
    for (let i = 0; i < n; ++i) {
        let t1 = parsed[i];
        if (t1.amount > 1000)
            invalid.add(t1.raw);
        for (let j = 0; j < n; ++j) {
            if (i === j) continue;
            let t2 = parsed[j];
            if (t1.name === t2.name && t1.city !== t2.city && Math.abs(t1.time - t2.time) <= 60)
                invalid.add(t1.raw);
        }
    }
    return Array.from(invalid);
};
      

Problem Description

You are given a list of transaction strings, where each transaction is formatted as "name,time,amount,city". Your task is to identify all invalid transactions and return them in any order.

A transaction is considered invalid if:

• The amount exceeds 1000.
• Or, there exists another transaction with the same name but in a different city that occurred within 60 minutes (inclusive) of this transaction.

Each transaction string is unique. You must not reuse or modify elements. The returned list can be in any order.

Thought Process

At first glance, the problem seems to require checking each transaction against all others for the same name and time window, as well as checking the amount. The naive approach is a brute-force comparison of every pair, but that can be inefficient for large lists.

To optimize, we can consider grouping transactions by name for faster lookup, and then, for each transaction, checking only the relevant others (same name, different city, within 60 minutes). However, since the list may be small (as per Leetcode constraints), a double loop is still acceptable for clarity.

The key is to ensure that:

• We parse transactions into structured data for easier handling.
• We check both rules for each transaction.
• We avoid duplicates in the result by using a set.

Solution Approach

Let's break down the solution into clear steps:

1. Parse Transactions:
   • Split each transaction string into name, time, amount, and city.
   • Store the parsed data in a list of objects or tuples for easy access.
2. Initialize a Set for Invalid Transactions:
   • Use a set to avoid duplicate entries in the output.
3. Check Each Transaction:
   • If amount > 1000, mark as invalid.
   • For each transaction, compare with all others:
     • If name matches, city is different, and abs(time1 - time2) <= 60, mark as invalid.
4. Return Results:
   • Convert the set of invalid transactions to a list and return.

We use a set for O(1) insertions and to ensure uniqueness. Parsing up-front avoids repeated string splits. The double loop is acceptable for the typical input size in this problem.

Example Walkthrough

Suppose the input is: ["alice,20,800,mtv","alice,50,100,beijing","alice,51,1200,mtv","bob,50,1200,mtv"]

• alice,20,800,mtv:
  • Amount < 1000, so not invalid by amount.
  • Compare to alice,50,100,beijing:
    • Same name, different city, |20-50|=30 ≤ 60. So, mark as invalid.
• alice,50,100,beijing:
  • Amount < 1000.
  • Compare to alice,20,800,mtv (already checked above), same as above, so mark as invalid.
• alice,51,1200,mtv:
  • Amount > 1000, so mark as invalid.
• bob,50,1200,mtv:
  • Amount > 1000, so mark as invalid.

The output will be all four transactions, as they all meet at least one invalid condition.

Time and Space Complexity

Brute-force Approach:

• Time: O(n²) — For each transaction, we may compare with every other transaction.
• Space: O(n) — For storing parsed transactions and the set of invalid transactions.

• Time: Still O(n²) in the worst case (if all names are the same), but can be better if names are unique.
• Space: O(n) for grouping and storage.

The solution is acceptable given the typical constraints of Leetcode problems.

Summary

The problem asks us to identify invalid transactions based on amount and suspicious timing/location patterns. By parsing each transaction, using a set for results, and comparing each transaction with all others, we can ensure correctness and clarity. While the approach is quadratic in time, it is straightforward and robust for the expected input size, making it an elegant solution for this scenario.