Invalid Transactions LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple BloombergViews 3525

Problem Statement

Invalid Transactions LeetCode Solution – 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.

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.


Bruteforce Approach:

The basic idea is to create a set to remove possible duplicates when looking at the two different ($1000 and within 60 minutes in a different city) invalid conditions. Then just brute force it by iteratively comparing every transaction with all the other transactions. This is extremely easy to do, but not optimal.

Optimized Approach:

  1. Create a transaction data structure so the attributes can easily be queried and stored in a transactions array
  2. Sort the transactions array-based on time
  3. Iterate through the transactions array and create a hash table/dictionary with name as the key, and an array of transaction indexes as the value.
  4. Iterate through the dictionary and loop through the name specific transaction indexes array.
    • Over 1000 dollars check: If the current transaction amount is greater than 1000, then add to the res and continue to the next transaction.
    • Within 60 minutes check: Use left, and right pointers to represent the possible neighbor transactions that are within the 60 minutes.
    • If the current transaction has any neighbors within the 60 minutes then check if the city is different. If so, add to the res and continue to the next transactions.

1 We need to sort the transactions by time, so a function convert string to a customized struct is required.
2 To reduce the effort of compare of transactions, we use unordered_map to classify them by name.
3 To generate the result easily, we add the input string and a bool flag to the struct, with other info in the transactions we get the 6-member struct design.
4 To reach better performance, we can do sort only for transactions from the same name.


C++ Code for Invalid Transaction

class Solution {
    struct CustomerDetail{
        string name;
        int time;
        int amount;
        string city;
    CustomerDetail prepareCustomerObject(string s){
        string t;
        istringstream f(s);
        CustomerDetail obj =  CustomerDetail();[0];
        return obj;
    vector<string> invalidTransactions(vector<string>& transactions) {
        vector<bool> invalid(transactions.size());
        vector<CustomerDetail> details;
        map<string/*name*/,vector<int>/*list of indexes*/> hashmap;
        int i=0;
        for(string s: transactions) {
            CustomerDetail obj = prepareCustomerObject(s);
            if(hashmap.find( != hashmap.end()) {
                vector<int> indexes = hashmap[];
                for(int ind: indexes) {
                    if(details[ind].city != && abs(obj.time-details[ind].time)<= 60) {
        vector<string> ans;
        return ans;

Java Code for Invalid Transaction

class Solution {
    public List<String> invalidTransactions(final String[] transactions) {
    final List<String> invalid = new ArrayList<>();
    final Map<String, List<Transaction>> map = new HashMap<>();

     * build a map with name as key and value as list of transactions for that name
    for (final String transaction : transactions) {
      final Transaction tran = new Transaction(transaction);

      if (map.containsKey( {
      } else {
        final List<Transaction> list = new ArrayList<>();
        map.put(, list);

    for (final String transaction : transactions) {
      final Transaction tran = new Transaction(transaction);

      if (!isValid(map.get(, tran)) {


    return invalid;

  public boolean isValid(final List<Transaction> transactions, final Transaction transaction) {

    /* if there is only one transaction and the amount is less than 1000 */
    if (transactions.size() <= 1 && transaction.amount < 1000)
      return true;

    /* check against all other transaction to check it this one is valid */
    for (final Transaction tran : transactions) {
      if (transaction.invalidTransaction(, tran.time)) {
        return false;
    return true;

  class Transaction {
    String name;
    int time;
    int amount;
    String city;

    Transaction(final String transaction) {
      final String[] t = transaction.split(","); = t[0];
      this.time = Integer.parseInt(t[1]);
      this.amount = Integer.parseInt(t[2]); = t[3];

     * the amount exceeds $1000, or;
     * if it occurs within (and including) 60 minutes of another transaction with
     * the same name in a different city. Each transaction string transactions[i]
     * consists of comma separated values representing the name, time (in minutes),
     * amount, and city of the transaction.
    public boolean invalidTransaction(final String city, final int time) {
      return invalidAmount() || differentCity(city, time);

    private boolean differentCity(final String city, final int time) {
      return ! && Math.abs(this.time - time) <= 60;

    private boolean invalidAmount() {
      return this.amount > 1000;

Python Code for Invalid Transaction

class Transaction:
    def __init__(self, name, time, amount, city): = name
        self.time = int(time)
        self.amount = int(amount) = city

from collections import defaultdict
class Solution:
    def invalidTransactions(self, transactions):
        transactions = [Transaction(*transaction.split(',')) for transaction in transactions]
        transactions.sort(key=lambda t: t.time) # O(nlogn) time

        trans_indexes = defaultdict(list)
        for i, t in enumerate(transactions): # O(n) time

        res = []
        for name, indexes in trans_indexes.items(): # O(n) time
            left = right = 0
            for i, t_index in enumerate(indexes):
                t = transactions[t_index]
                if (t.amount > 1000):
                    res.append("{},{},{},{}".format(, t.time, t.amount,
                while left <= len(indexes)-2 and transactions[indexes[left]].time < t.time - 60: # O(60) time
                    left += 1
                while right <= len(indexes)-2 and transactions[indexes[right+1]].time <= t.time + 60: # O(60) time
                    right += 1
                for i in range(left,right+1): # O(120) time
                    if transactions[indexes[i]].city !=
                        res.append("{},{},{},{}".format(, t.time, t.amount,

        return res

Complexity Analysis for Invalid Transactions LeetCode Solution

Time Complexity


Space Complexity

O(1) as we are not using any extra space.


Translate »