Invalid Transactions

Parse each string once into (name, time, amount, city). Then take every transaction and compare it against every other transaction with the same name: if the cities differ and the times are within 60 minutes, mark it invalid. The amount rule is evaluated independently. A pair only has to be detected once, because a conflicting transaction is marked when it is the outer loop’s turn just as it is when it is the inner loop’s turn.

class Solution:
    def invalidTransactions(self, transactions: list[str]) -> list[str]:
        parsed = []
        for x in transactions:
            name, time, amount, city = x.split(",")
            parsed.append((name, int(time), int(amount), city))

        invalid = set()
        n = len(transactions)
        for i in range(n):
            name_i, time_i, amount_i, city_i = parsed[i]
            if amount_i > 1000:
                invalid.add(i)
            for j in range(n):
                if i == j:
                    continue
                name_j, time_j, _, city_j = parsed[j]
                if name_i == name_j and city_i != city_j and abs(time_i - time_j) <= 60:
                    invalid.add(i)

        return [transactions[i] for i in invalid]

Why it is quadratic: the nested loops compare all n² ordered pairs even though the name is often different, and every comparison is constant work, so time is O(n²). The parsed copy and the result set hold at most n entries each, so space is O(n) (the output itself can be all n transactions).

Only transactions with the same name can invalidate each other, so build a hash map from name to the list of indices that carry it. Then scan the transactions left to right. For transaction i, first apply the local amount rule; then compare it with the earlier entries in its own bucket only, one at a time. A comparison is a conflict exactly when both conditions hold together — the cities differ and the time gap is at most 60 minutes. When they do, add i and the earlier partner j to the invalid set. Restricting the scan to j < i avoids checking each pair twice, while still marking both sides.

class Solution:
    def invalidTransactions(self, transactions: list[str]) -> list[str]:
        parsed = []
        for x in transactions:
            name, time, amount, city = x.split(",")
            parsed.append((name, int(time), int(amount), city))

        by_name = {}
        for i, (name, _, _, _) in enumerate(parsed):
            by_name.setdefault(name, []).append(i)

        invalid = set()
        for i, (name, time, amount, city) in enumerate(parsed):
            if amount > 1000:
                invalid.add(i)
            for j in by_name[name]:
                if j >= i:
                    continue
                other_time = parsed[j][1]
                other_city = parsed[j][3]
                if other_city != city and abs(time - other_time) <= 60:
                    invalid.add(i)
                    invalid.add(j)

        return [transactions[i] for i in invalid]

Watch how each new row only ever looks at the earlier rows of its own name bucket, and how a conflicting pair marks both indices:

Why it works: the name bucket contains every transaction that could possibly be a partner, and the j < i guard pairs each comparison exactly once while still marking both endpoints. The amount rule is checked without reference to any partner. Complexity: building the buckets is O(n), and the comparisons total sum of C(k, 2) over the name bucket sizes k, which is O(n²) in the worst case when every transaction shares one name and O(n) when all names are distinct. The buckets and parsed rows use O(n) space.