Leetcode 1169. Invalid Transactions
Asked at:
Bloomberg
DESCRIPTION
Given a list of transactions (each with name, time, amount, city), identify invalid transactions based on two rules: (1) any transaction with amount > 1000 is invalid, or (2) a transaction is invalid if another transaction with the same name occurs in a different city within 60 minutes (before or after). Return all invalid transaction strings. For example, if Alice,20,800,NYC and Alice,50,500,LA exist, both are invalid due to the time-window conflict across cities.
Input:
transactions = ["alice,20,800,mtv", "alice,50,100,beijing"]
Output:
["alice,20,800,mtv", "alice,50,100,beijing"]
Explanation: Both transactions occur within 60 minutes (time difference = 30) with the same name but different cities, so both are invalid.
Constraints:
- Each transaction string format: name,time,amount,city
- 1 <= transactions.length <= 1000
- 0 <= time <= 1000 (minutes)
- 0 <= amount <= 2000
- City and name are lowercase strings
Understanding the Problem
The core challenge is detecting conflicts within a 60-minute window for transactions sharing the same name but different cities. A naive O(n²) pairwise comparison works but can be optimized. First, parse each transaction string into structured data. Then group transactions by name to avoid comparing unrelated entries. Within each group, sort by time and check adjacent transactions (or use a sliding window) to detect city mismatches within 60 minutes. Finally, collect all invalid transaction strings (including those with amount > 1000).
Building Intuition
A naive approach checks every transaction pair (O(n²)), which works but is inefficient for large inputs. A better approach groups transactions by name first (using a hash map), then sorts each group by time. Within sorted groups, only transactions within a 60-minute sliding window need comparison—if any pair has different cities, both are invalid. For example, if Alice has transactions at times [10, 50, 120], only 10 and 50 need comparison (difference = 40 < 60), while 120 is outside the window.
This pattern applies to fraud detection systems where suspicious activity is flagged based on temporal and spatial anomalies (e.g., credit card used in two distant locations within minutes). Efficiently grouping and sorting by time windows is crucial for real-time monitoring at scale. The technique generalizes to any event correlation problem with time-based constraints.
Common Pitfalls
Implementation
Transaction Parsing and Data Structure
Parse each transaction string into a structured format (e.g., a class or dictionary with name, time, amount, city fields). Store the original string alongside parsed data to return invalid entries in their original format. For example, "alice,20,800,mtv" becomes {name: 'alice', time: 20, amount: 800, city: 'mtv', original: 'alice,20,800,mtv'}. This separation of concerns makes subsequent logic cleaner and avoids repeated string splitting.
class Transaction:def __init__(self, transaction_str):parts = transaction_str.split(',')self.name = parts[0]self.time = int(parts[1])self.amount = int(parts[2])self.city = parts[3]self.original = transaction_strdef parse_transactions(transactions):return [Transaction(t) for t in transactions]
Grouping and Sorting by Name
Use a hash map to group parsed transactions by name (e.g., {"alice": [tx1, tx2], "bob": [tx3]}). Within each group, sort transactions by time to enable efficient window-based comparisons. For example, if Alice has transactions at times [50, 10, 120], sorting yields [10, 50, 120], allowing linear scans to detect conflicts. This reduces comparisons from O(n²) globally to O(k²) per name group (where k is typically small).
def group_and_sort_transactions(transactions):from collections import defaultdictgrouped = defaultdict(list)for tx in transactions:grouped[tx.name].append(tx)for name in grouped:grouped[name].sort(key=lambda t: t.time)return grouped
Conflict Detection with Time Windows
For each name group, iterate through sorted transactions and compare each transaction with subsequent ones while the time difference ≤ 60. If two transactions have different cities within this window, mark both as invalid (store their indices or original strings in a set). Also check if amount > 1000 for each transaction independently. For example, transactions at times [10, 50, 120] only require comparing (10, 50) and (50, 120), skipping (10, 120) since the difference exceeds 60.
def detect_conflicts(grouped_transactions):invalid = set()for name, txs in grouped_transactions.items():for i in range(len(txs)):if txs[i].amount > 1000:invalid.add(txs[i].original)j = i + 1while j < len(txs) and txs[j].time - txs[i].time <= 60:if txs[i].city != txs[j].city:invalid.add(txs[i].original)invalid.add(txs[j].original)j += 1return list(invalid)
Complete Integration
Combine the parsing (Section 1), grouping/sorting (Section 2), and conflict detection (Section 3) into a single function. Parse all transactions, group by name, sort each group, detect conflicts and amount violations, then return the original strings of all invalid transactions. Use a Set to avoid duplicate entries if a transaction is flagged multiple times. For example, the main function orchestrates: parse → group → sort → detect → collect results.
def invalidTransactions(transactions):parsed = parse_transactions(transactions)grouped = group_and_sort_transactions(parsed)invalid = detect_conflicts(grouped)return invalid
What We've Learned
- Pattern: Group-by-key + sort-by-time enables efficient sliding window conflict detection in O(n log n) time.
- Use Case: Fraud detection, event correlation, and anomaly detection in time-series data with spatial constraints.
- Optimization: Sorting within groups (not globally) reduces comparisons when most transactions belong to different names.
- Edge Case: A transaction can be invalid for multiple reasons (amount + conflict)—use a set to deduplicate results.
Problems to Practice
easy
This problem involves checking for overlapping time intervals, which is directly related to the Invalid Transactions problem where you need to detect transactions within a 60-minute time window. Both require sorting by time and checking for conflicts between intervals.
medium
Similar to Invalid Transactions, this problem requires grouping and processing time-based data to detect overlaps. The pattern of sorting by time and checking adjacent/overlapping intervals is the same core technique needed for detecting transactions within 60 minutes.
medium
While this uses sliding window, it shares the pattern of tracking elements within a constrained range (time window vs character window) using a hashmap to group and check for duplicates/conflicts, similar to grouping transactions by name and checking within time windows.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late February, 2026
Bloomberg
Senior
1st question in 2 part phone screen
Mid December, 2025
Bloomberg
Senior
Mid February, 2025
Bloomberg
Junior
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.