LeetCode 1169 - Invalid Transactions
The problem asks us to identify transactions that are potentially invalid based on two rules. First, any transaction with an amount greater than $1000 is invalid.
Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Sorting
Solution
Problem Understanding
The problem asks us to identify transactions that are potentially invalid based on two rules. First, any transaction with an amount greater than $1000 is invalid. Second, any transaction is invalid if there exists another transaction with the same name that occurs within 60 minutes but in a different city.
The input is a list of strings, each representing a transaction in the format "name,time,amount,city". The time is in minutes, amount is an integer value, and city is a lowercase string. The output is a list of all transactions from the input that satisfy either of the invalidity conditions. The order of the output does not matter.
Constraints tell us that there are at most 1000 transactions, each transaction string is well-formed, names and cities are lowercase and of length 1 to 10, and times and amounts are within reasonable bounds. Because the input size is small, a quadratic-time solution is feasible, but we should aim for something more structured.
Important edge cases include transactions with the same name and city, transactions that occur exactly 60 minutes apart, transactions right at the $1000 threshold, and multiple transactions from the same person in different cities.
Approaches
A brute-force approach would be to check each transaction against all others. For each transaction, we would parse its components, then iterate through all other transactions to check for the same name and a time difference of at most 60 minutes in a different city. This approach works and correctly identifies invalid transactions, but it has a time complexity of $O(n^2)$, which may be slow if the input size approaches the upper bound.
A more optimal approach leverages grouping transactions by name. By doing this, we only need to compare transactions with the same name. Sorting each group by time allows us to efficiently check the 60-minute window condition without comparing every transaction against all others. Transactions exceeding $1000 can be marked as invalid immediately. This approach reduces unnecessary comparisons while maintaining correctness.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) | Compare each transaction against all others. Correct but slow. |
| Optimal | O(n log n) | O(n) | Group by name, sort each group by time, mark invalid transactions efficiently. |
Algorithm Walkthrough
- Parse all transactions into structured objects or tuples containing
name,time,amount,city, and the original string. This allows easy access to components for comparison. - Immediately mark any transaction with an amount greater than 1000 as invalid.
- Group transactions by name using a hash map or dictionary. This ensures we only compare transactions with the same name.
- For each group of transactions, sort them by time in ascending order. Sorting allows a linear sweep to check the 60-minute difference efficiently.
- For each transaction in the sorted group, check neighboring transactions within a 60-minute window. If any transaction occurs in a different city, mark both transactions as invalid.
- Collect all invalid transactions into a result list and return it.
Why it works: The algorithm guarantees that all transactions exceeding 1000 are marked, and the grouping by name ensures we only compare relevant transactions. Sorting ensures we efficiently find pairs within 60 minutes. This covers all possible invalid cases without redundant checks.
Python Solution
from typing import List
from collections import defaultdict
class Solution:
def invalidTransactions(self, transactions: List[str]) -> List[str]:
txn_data = []
invalid = set()
# Step 1: Parse transactions and mark by amount > 1000
for txn in transactions:
name, time, amount, city = txn.split(',')
time = int(time)
amount = int(amount)
txn_data.append((name, time, amount, city, txn))
if amount > 1000:
invalid.add(txn)
# Step 2: Group transactions by name
name_groups = defaultdict(list)
for txn in txn_data:
name_groups[txn[0]].append(txn)
# Step 3: Check 60-minute different city condition
for group in name_groups.values():
group.sort(key=lambda x: x[1]) # sort by time
n = len(group)
for i in range(n):
for j in range(i+1, n):
if group[j][1] - group[i][1] > 60:
break
if group[i][3] != group[j][3]:
invalid.add(group[i][4])
invalid.add(group[j][4])
return list(invalid)
The Python solution first parses each transaction and marks those exceeding $1000 as invalid. It then groups transactions by name, sorts each group by time, and checks only nearby transactions within 60 minutes for city differences, adding them to the invalid set as needed.
Go Solution
package main
import (
"strconv"
"strings"
)
func invalidTransactions(transactions []string) []string {
type txn struct {
name string
time int
amount int
city string
orig string
}
txnData := make([]txn, 0, len(transactions))
invalid := make(map[string]bool)
for _, t := range transactions {
parts := strings.Split(t, ",")
timeInt, _ := strconv.Atoi(parts[1])
amountInt, _ := strconv.Atoi(parts[2])
txnData = append(txnData, txn{parts[0], timeInt, amountInt, parts[3], t})
if amountInt > 1000 {
invalid[t] = true
}
}
nameGroups := make(map[string][]txn)
for _, t := range txnData {
nameGroups[t.name] = append(nameGroups[t.name], t)
}
for _, group := range nameGroups {
for i := 0; i < len(group); i++ {
for j := i + 1; j < len(group); j++ {
if group[j].time - group[i].time > 60 {
break
}
if group[i].city != group[j].city {
invalid[group[i].orig] = true
invalid[group[j].orig] = true
}
}
}
}
result := make([]string, 0, len(invalid))
for t := range invalid {
result = append(result, t)
}
return result
}
The Go solution mirrors the Python approach. It uses a struct to store transaction data, a map to mark invalid transactions, and nested loops within each name group to identify cross-city transactions within 60 minutes.
Worked Examples
Example 1: ["alice,20,800,mtv","alice,50,100,beijing"]
Parse: alice,20,800,mtv and alice,50,100,beijing. Neither exceeds $1000. Group by name gives one group. Sorted by time: 20, 50. Time difference 30 < 60, cities differ, so both are invalid. Output: ["alice,20,800,mtv","alice,50,100,beijing"].
Example 2: ["alice,20,800,mtv","alice,50,1200,mtv"]
alice,50,1200,mtv exceeds $1000. Group by name sorted by time: 20, 50. Cities same, so only the amount rule triggers. Output: ["alice,50,1200,mtv"].
Example 3: ["alice,20,800,mtv","bob,50,1200,mtv"]
Only Bob’s transaction exceeds $1000. Output: ["bob,50,1200,mtv"].
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Parsing is O(n), grouping O(n), sorting groups O(n log n), inner loop over 60-minute window is linear due to break |
| Space | O(n) | Store parsed transactions and invalid set |
The sorting dominates time complexity, while the space is linear due to storing parsed data and results.
Test Cases
# Basic examples
assert set(Solution().invalidTransactions(["alice,20,800,mtv","alice,50,100,beijing"])) == set(["alice,20,800,mtv","alice,50,100,beijing"])
assert Solution().invalidTransactions(["alice,20,800,mtv","alice,50,1200,mtv"]) == ["alice,50,1200,mtv"]
assert Solution().invalidTransactions(["alice,20,800,mtv","bob,50,1200,mtv"]) == ["bob,50,1200,mtv"]
# Edge case: same city, different times
assert Solution().invalidTransactions(["alice,20,800,mtv","alice,80,800,mtv"]) == []
# Edge case: exactly 60 minutes apart, different city
assert set(Solution().invalidTransactions(["alice,20,800,mtv","alice,80,800,beijing"])) == set(["alice,20,800,mtv","alice,80,800,beijing"])
# Edge case: multiple transactions same name and city
assert Solution().invalidTransactions(["alice,10,200,mtv","alice,20,300,mtv","alice,25,1500,mtv"]) ==