1169. Invalid Transactions - Solution & Explanation

The problem

A transaction is possibly invalid if:

the amount exceeds $1000, or;
if it occurs within (and including) 60 minutes of another transaction with the same name in a different city.

You are given an array of strings transaction where transactions[i] consists of comma-separated values representing the name, time (in minutes), amount, and city of the transaction.

Return a list of transactions that are possibly invalid. You may return the answer in any order.

Example 1:

Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output: ["alice,20,800,mtv","alice,50,100,beijing"]
Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.

Example 2:

Input: transactions = ["alice,20,800,mtv","alice,50,1200,mtv"]
Output: ["alice,50,1200,mtv"]

Example 3:

Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]
Output: ["bob,50,1200,mtv"]

Constraints:

transactions.length <= 1000
Each transactions[i] takes the form "{name},{time},{amount},{city}"
Each {name} and {city} consist of lowercase English letters, and have lengths between 1 and 10.
Each {time} consist of digits, and represent an integer between 0 and 1000.
Each {amount} consist of digits, and represent an integer between 0 and 2000.

Approach overview

Problem Overview: Each transaction is a string formatted as name,time,amount,city. A transaction becomes invalid if the amount exceeds 1000, or if another transaction with the same name occurs within 60 minutes in a different city. You must return all transactions that violate these rules.

Approach 1: Brute Force Comparison (O(n²) time, O(n) space)

Parse every transaction into structured fields: name, time, amount, and city. First mark transactions invalid if amount > 1000. Then compare every pair of transactions using two nested loops. If two entries share the same name, their time difference is ≤ 60, and their cities differ, mark both as invalid. This approach directly implements the rule definition and requires only basic iteration over an array. The downside is the O(n²) pairwise comparison, which becomes slow when the number of transactions grows.

Approach 2: Map-Based Grouping with Sorting (O(n log n) time, O(n) space)

Group transactions by name using a hash table. For each name, sort that user's transactions by time using a sorting step. After sorting, iterate through the list and check nearby transactions whose time difference is within 60 minutes. Because the list is ordered, you only compare forward while the time window is valid, avoiding unnecessary checks. Transactions with amount > 1000 are immediately flagged, while city conflicts are detected during the local window scan. Sorting reduces the number of comparisons dramatically and keeps the logic organized by user.

This map-based approach scales much better because transactions from different users never interact. Each group is processed independently, and sorting allows efficient time-window checks instead of scanning the entire dataset repeatedly.

Recommended for interviews: The brute force approach demonstrates that you understand the rule constraints and how to translate them into comparisons. Interviewers usually expect the hash map grouping solution because it reduces unnecessary comparisons and structures the problem cleanly around user-based transaction histories. Showing the optimized map + sorting approach signals strong understanding of data organization and practical performance improvements.

Approach 1: Brute Force Approach

This initial approach involves checking each transaction to determine if it fails either of the given conditions. We'll iterate through the list multiple times to compare transactions that share the same name.

This is not the most optimal solution but it helps to ensure correctness before moving on to more optimized algorithms.

Python

def invalidTransactions(transactions):
    def isInvalid(tr1, tr2):
        return (
            tr1['name'] == tr2['name'] and
            abs(tr1['time'] - tr2['time']) <= 60 and
            tr1['city'] != tr2['city']
        )

    parsed_transactions = []
    for trans in transactions:
        name, time, amount, city = trans.split(",")
        parsed_transactions.append({
            'name': name,
            'time': int(time),
            'amount': int(amount),
            'city': city,
            'original': trans
        })

    invalid = []
    for i, tr1 in enumerate(parsed_transactions):
        if tr1['amount'] > 1000:
            invalid.append(tr1['original'])
            continue
        for j, tr2 in enumerate(parsed_transactions):
            if i != j and isInvalid(tr1, tr2):
                invalid.append(tr1['original'])
                break

    return invalid

C++

#include <vector>
#include <string>
#include <sstream>
#include <unordered_set>
using namespace std;

vector<string> invalidTransactions(vector<string>& transactions) {
    struct Transaction {
        string name;
        int time;
        int amount;
        string city;
        string original;
    };

    auto parseTransaction = [](const string& transaction_str) -> Transaction {
        stringstream ss(transaction_str);
        string name, time, amount, city;
        getline(ss, name, ',');
        getline(ss, time, ',');
        getline(ss, amount, ',');
        getline(ss, city, ',');
        return {name, stoi(time), stoi(amount), city, transaction_str};
    };

    vector<Transaction> transactions_parsed;
    for (const string& trans : transactions) {
        transactions_parsed.push_back(parseTransaction(trans));
    }

    unordered_set<string> invalid_set;
    for (size_t i = 0; i < transactions_parsed.size(); ++i) {
        const auto& t1 = transactions_parsed[i];
        if (t1.amount > 1000) {
            invalid_set.insert(t1.original);
            continue;
        }
        for (size_t j = 0; j < transactions_parsed.size(); ++j) {
            if (i != j) {
                const auto& t2 = transactions_parsed[j];
                if (t1.name == t2.name && ABS(t1.time - t2.time) <= 60 && t1.city != t2.city) {
                    invalid_set.insert(t1.original);
                    break;
                }
            }
        }
    }

    return vector<string>(invalid_set.begin(), invalid_set.end());
}

The function invalidTransactions begins by defining a helper function isInvalid to compare if two transactions are invalid due to name and city within 60 minutes. Transactions are then parsed into a dictionary for ease of comparison. Each transaction is checked if the amount exceeds 1000 or if conditions defined in isInvalid are met.

Complexity

Time Complexity: O(n^2) where n is the number of transactions. We have a nested loop comparing each transaction with every other transaction.
Space Complexity: O(n), since we store each parsed transaction in a list.

Try this approach in the editor

Approach 2: Optimized Map-based Approach

This approach optimizes the brute-force solution by using maps to store transactions group by their names, which reduces unnecessary comparisons, thus improving efficiency. This greatly reduces comparisons when there are many transactions with different names.

Java

import java.util.*;

public class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        Map<String, List<String[]>> transactionMap = new HashMap<>();
        List<String> result = new ArrayList<>();

        for (String t : transactions) {
            String[] details = t.split(",");
            transactionMap.computeIfAbsent(details[0], k -> new ArrayList<>()).add(details);
        }

        for (List<String[]> records : transactionMap.values()) {
            Collections.sort(records, Comparator.comparingInt(r -> Integer.parseInt(r[1])));
            for (int i = 0; i < records.size(); i++) {
                String[] t1 = records.get(i);
                if (Integer.parseInt(t1[2]) > 1000) {
                    result.add(String.join(",", t1));
                }
                for (int j = i + 1; j < records.size(); j++) {
                    String[] t2 = records.get(j);
                    int timeGap = Integer.parseInt(t2[1]) - Integer.parseInt(t1[1]);
                    if (timeGap > 60) break;
                    if (!t1[3].equals(t2[3])) {
                        result.add(String.join(",", t1));
                        result.add(String.join(",", t2));
                    }
                }
            }
        }
        return new ArrayList<>(new HashSet<>(result));
    }
}

JavaScript

function invalidTransactions(transactions) {
    const map = new Map();
    const result = new Set();

    transactions.forEach(t => {
        const [name, time, amount, city] = t.split(",");
        if (!map.has(name)) {
            map.set(name, []);
        }
        map.get(name).push({ time: parseInt(time), amount: parseInt(amount), city, original: t });
    });

    map.forEach(records => {
        records.sort((a, b) => a.time - b.time);
        for (let i = 0; i < records.length; i++) {
            if (records[i].amount > 1000) result.add(records[i].original);
            for (let j = i + 1; j < records.length; j++) {
                if (records[j].time - records[i].time > 60) break;
                if (records[i].city !== records[j].city) {
                    result.add(records[i].original);
                    result.add(records[j].original);
                }
            }
        }
    });

    return Array.from(result);
}

The Java solution employs a map to efficiently group transactions by name, reducing the scope of city and time comparison to only transactions that share a name. Each group is sorted by time to minimize comparison overhead. Uniqueness in the result is ensured by converting it to a set before returning.

Complexity

Time Complexity: O(n log n) due to sorting each group of transactions by time. Each time comparison within groups is constrained to those with smaller time differences.
Space Complexity: O(n) for storing parsed transactions.

Try this approach in the editor

Approach 3: Hash Table + Simulation

We traverse the transaction list. For each transaction, if the amount is greater than 1000, or if the transaction has the same name but different cities and the time interval does not exceed 60 minutes, then add it to the answer.

Specifically, we use a hash table d to record each transaction, where the key is the transaction name, and the value is a list. Each element in the list is a tuple (time, city, index), indicating that a transaction with the number index was conducted in the city city at the moment time. At the same time, we use a hash table idx to record the transaction number in the answer.

We traverse the transaction list. For each transaction, we first add it to the hash table d, and then judge whether its amount is greater than 1000. If so, add its number to the answer. Then we traverse the transactions in the hash table d. If the transaction names are the same but the cities are different and the time interval does not exceed 60 minutes, add its number to the answer.

Finally, we traverse the transaction numbers in the answer and add the corresponding transactions to the answer.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the transaction list.

func invalidTransactions(transactions []string) (ans []string) {
	d := map[string][]tuple{}
	idx := map[int]bool{}
	for i, x := range transactions {
		e := strings.Split(x, ",")
		name := e[0]
		time, _ := strconv.Atoi(e[1])
		amount, _ := strconv.Atoi(e[2])
		city := e[3]
		d[name] = append(d[name], tuple{time, city, i})
		if amount > 1000 {
			idx[i] = true
		}
		for _, item := range d[name] {
			if city != item.city && abs(time-item.t) <= 60 {
				idx[i], idx[item.i] = true, true
			}
		}
	}
	for i := range idx {
		ans = append(ans, transactions[i])
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

type tuple struct {
	t    int
	city string
	i    int
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n^2) where n is the number of transactions. We have a nested loop comparing each transaction with every other transaction. Space Complexity: O(n), since we store each parsed transaction in a list.
Optimized Map-based Approach	Time Complexity: O(n log n) due to sorting each group of transactions by time. Each time comparison within groups is constrained to those with smaller time differences. Space Complexity: O(n) for storing parsed transactions.
Hash Table + Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Pairwise Check	O(n²)	O(n)	Good for understanding the rule logic or when input size is small
Hash Map Grouping + Sorting	O(n log n)	O(n)	Best general solution; scales well by grouping transactions per user

Frequently asked questions

Is Invalid Transactions easy or hard?

Invalid Transactions is rated Medium difficulty because it combines multiple concepts: string parsing, hash map grouping, sorting, and conditional comparisons. The challenge lies in organizing the data correctly and efficiently checking the 60-minute rule without excessive comparisons.

How to solve Invalid Transactions in O(n)?

A strict O(n) solution is difficult because checking the 60‑minute window usually benefits from sorting by time. The typical optimized solution achieves O(n log n) by sorting transactions per user and scanning only nearby entries. Hash map grouping ensures transactions from different users are processed independently.

What is the best approach for Invalid Transactions?

The most efficient approach groups transactions by name using a hash map and then sorts each user's transactions by time. After sorting, you only compare transactions within a 60‑minute window to detect city conflicts. This reduces unnecessary comparisons and runs in O(n log n) time with O(n) space.

What data structure is used in Invalid Transactions?

The key data structure is a hash map that groups transactions by user name. Arrays or lists store each user's transactions, and sorting helps efficiently detect conflicts within a 60-minute window. String parsing is also required to extract fields from each transaction record.

What is the time complexity of Invalid Transactions?

The brute force solution checks every pair of transactions, resulting in O(n^2) time complexity. The optimized solution groups by name and sorts transactions by time, giving an overall complexity of O(n log n). Space complexity for both approaches is O(n) due to storing parsed transaction data.

Invalid Transactions Python or Java solution approach

In Python or Java, first split each transaction string into fields, then store them in a map keyed by name. Sort each user's transactions by time and scan nearby entries to detect city conflicts within 60 minutes. Also flag any transaction where the amount exceeds 1000.

Is Invalid Transactions asked at Google, Amazon, or Meta?

This problem represents a common interview pattern involving hash maps, string parsing, and time-window comparisons. Variants of transaction validation and log analysis appear in interviews at companies like Amazon, Google, and Meta where candidates must efficiently process event records.

Invalid Transactions solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Map-based Approach

Approach 3: Hash Table + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Invalid Transactions solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Map-based Approach

Approach 3: Hash Table + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems