1169.Invalid Transactions

Link: 1169. Invalid Transactions - Medium

Question

Restate the problem

Given a list of transaction, where each transaction is in the formatname, time, amount, city
Invalid transition:

1. The amount > 1000 or
2. There exists another transaction with the same name, <= 60 minutes, in a different city.
   Return: list of invalid transaction

Q: Can there be multiple transactions with exactly the same values, and should they be treated as separate transactions?

Method

Approach - hashmap

Use a hash map to group transactions by name

• Find invalid amount, iterate through all transitions once. If amount > 1000, mark transition as invalid
• Find invalid time and city conflict.
  • Sort transition by time
  • compare transitions pairwise. If two transitions are within 60 minutes and they occurred in different cities
  • Mark both transitions as invalid
• Return all transitions whose indices are marked invalid

Complexity

• Time Complexity: O($n^2$)
  • sort: O($klogk$), under the same name, transition number
• Space Complexity: O(n)

Edge Case

• Empty input list

Code

class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]:
        n = len(transactions)
        invalid = [False] * n
        dic = defaultdict(list)
        for idx, tran in enumerate(transactions):
            name, time, amount, loc = tran.split(',')
            if int(amount) > 1000:
                invalid[idx] = True
            dic[name].append((int(time), int(amount), loc, idx))
 
        for name in dic:
            dic[name].sort(key = lambda x: x[0])
 
            m = len(dic[name])
 
            for i in range(m):
                rec_time, rec_amount, rec_loc, rec_idx = dic[name][i]
                for j in range(i + 1, m):
                    cur_time, cur_amount, cur_loc, cur_idx = dic[name][j]
                    
                    if cur_time - rec_time > 60: # add early break
                        break
                    if rec_loc != cur_loc and (cur_time - rec_time) <= 60:
                        invalid[rec_idx] = True
                        invalid[cur_idx] = True
        
        return [tran for idx, tran in enumerate(transactions) if invalid[idx]]

---

History

Jan-18-2026 Peeked, Mistake: didn’t compare each transaction