# Invalid Transactions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/invalid-transactions)
Canonical: https://scaleengineer.com/dsa/problems/invalid-transactions
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal), [Wix](https://scaleengineer.com/companies/wix)
---
## 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`.

# Approaches
## Brute Force Comparison
This approach directly translates the problem statement into code by iterating through every possible pair of transactions to check for the invalid conditions. It is the most straightforward but least efficient method, serving as a baseline.
**Time:** O(N^2), where N is the number of transactions. The nested loops that compare every pair of transactions dominate the runtime. · **Space:** O(N), where N is the number of transactions. This space is used to store the parsed transaction data and the `isInvalid` boolean array.
**Pros:** Simple to understand and implement.; Requires minimal complex data structures.
**Cons:** Inefficient for large inputs due to the O(N^2) time complexity.; Performs many redundant comparisons, especially for transactions with unique names.
### Explanation
In this method, we first parse all transaction strings into a more accessible format, such as parallel arrays or a list of custom objects, to easily retrieve the name, time, amount, and city for each transaction. We then use a boolean array, `isInvalid`, to keep track of the validity status of each transaction, initialized to `false`.

The core of the algorithm is a nested loop. The outer loop selects a transaction `i`, and the inner loop compares it against every other transaction `j`. For each transaction `i`, we first check if its amount exceeds $1000. If it does, we immediately mark it as invalid. Then, in the inner loop, we check for the second invalidity condition: a transaction `j` with the same name, a different city, and a time within 60 minutes. If such a transaction `j` is found, we mark transaction `i` as invalid and can break out of the inner loop since its status is confirmed.

After checking all transactions, we iterate through the `isInvalid` array and collect all the original transaction strings that were marked as invalid into a final list to be returned.

```java
class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        int n = transactions.length;
        if (n == 0) {
            return new ArrayList<>();
        }

        String[] names = new String[n];
        int[] times = new int[n];
        int[] amounts = new int[n];
        String[] cities = new String[n];

        for (int i = 0; i < n; i++) {
            String[] parts = transactions[i].split(",");
            names[i] = parts[0];
            times[i] = Integer.parseInt(parts[1]);
            amounts[i] = Integer.parseInt(parts[2]);
            cities[i] = parts[3];
        }

        boolean[] isInvalid = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (amounts[i] > 1000) {
                isInvalid[i] = true;
            }
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (names[i].equals(names[j]) && 
                    !cities[i].equals(cities[j]) && 
                    Math.abs(times[i] - times[j]) <= 60) {
                    isInvalid[i] = true;
                    break; 
                }
            }
        }

        List<String> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (isInvalid[i]) {
                result.add(transactions[i]);
            }
        }
        return result;
    }
}
```
### Algorithm
- Create a `Transaction` class or use parallel arrays to store the parsed details of each transaction: `name`, `time`, `amount`, and `city`.
- Initialize a boolean array, `isInvalid`, of size `n` (number of transactions) to all `false`.
- Iterate through each transaction `i` from `0` to `n-1`:
  - Check the amount condition: If `transactions[i].amount > 1000`, set `isInvalid[i] = true`.
  - Start a nested loop for each transaction `j` from `0` to `n-1`:
    - If `i` and `j` are the same, skip.
    - Check the conflict condition: If `transactions[i].name` equals `transactions[j].name`, `transactions[i].city` is different from `transactions[j].city`, and the absolute difference in their times is less than or equal to 60, then transaction `i` is invalid.
    - If the condition is met, set `isInvalid[i] = true` and `break` the inner loop, as we've confirmed `i` is invalid.
- After the loops, create a result list.
- Iterate from `i = 0` to `n-1`. If `isInvalid[i]` is `true`, add the original transaction string `transactions[i]` to the result list.
- Return the result list.

## Grouping by Name with Sorting
This optimized approach improves upon the brute-force method by reducing unnecessary comparisons. It works by first grouping all transactions by name using a `HashMap`. Then, for each name, it sorts the corresponding transactions by time. This sorting allows for a much more efficient search for time-based conflicts, as we only need to check a small window of transactions around the current one.
**Time:** O(N log K + M), where N is the total number of transactions, K is the maximum number of transactions for a single name, and M is the number of pairwise comparisons. The dominant factor is often sorting, leading to an average complexity close to O(N log K). The worst-case is O(N^2) if all transactions share the same name. · **Space:** O(N), where N is the number of transactions. Space is required for the `HashMap`, the `Transaction` objects it contains, and the result `Set`.
**Pros:** Significantly faster than brute force on average, especially when names are diverse.; Sorting by time allows for early termination of the inner loop, optimizing the search for conflicts.
**Cons:** More complex to implement due to the use of a HashMap, sorting, and a custom class.; The worst-case time complexity is still O(N^2), which occurs if all transactions have the same name.
### Explanation
The key insight for this optimization is that we only need to compare transactions that share the same name. We can achieve this efficiently by using a `HashMap` where keys are names and values are lists of transactions for that name.

First, we parse each transaction string into a custom `Transaction` object and populate the `HashMap`. After grouping, we process each group (each list of transactions in the map) independently. To efficiently check the time condition (`|time1 - time2| <= 60`), we sort each list of transactions by time. 

With a sorted list, for any given transaction `t1`, we only need to look at the transactions `t2` that immediately follow it. We can iterate forward from `t1` and check for conflicts. As soon as we find a `t2` where `t2.time - t1.time > 60`, we can stop searching for that `t1` because all subsequent transactions will also be outside the 60-minute window. If a conflicting transaction is found (same name, different city, time difference <= 60), both transactions involved are marked as invalid. We use a `Set` to store the results to automatically handle duplicates. Finally, we convert the set to a list.

```java
class Solution {
    class Transaction {
        String name;
        int time;
        int amount;
        String city;
        String original;

        public Transaction(String transactionString) {
            String[] parts = transactionString.split(",");
            this.name = parts[0];
            this.time = Integer.parseInt(parts[1]);
            this.amount = Integer.parseInt(parts[2]);
            this.city = parts[3];
            this.original = transactionString;
        }
    }

    public List<String> invalidTransactions(String[] transactions) {
        Map<String, List<Transaction>> nameToTransactionsMap = new HashMap<>();
        for (String t : transactions) {
            Transaction transaction = new Transaction(t);
            nameToTransactionsMap.computeIfAbsent(transaction.name, k -> new ArrayList<>()).add(transaction);
        }

        Set<String> invalidSet = new HashSet<>();
        for (List<Transaction> transactionList : nameToTransactionsMap.values()) {
            Collections.sort(transactionList, (a, b) -> a.time - b.time);

            for (int i = 0; i < transactionList.size(); i++) {
                Transaction t1 = transactionList.get(i);
                
                if (t1.amount > 1000) {
                    invalidSet.add(t1.original);
                }

                for (int j = i + 1; j < transactionList.size(); j++) {
                    Transaction t2 = transactionList.get(j);
                    
                    if (t2.time - t1.time > 60) {
                        break;
                    }

                    if (!t1.city.equals(t2.city)) {
                        invalidSet.add(t1.original);
                        invalidSet.add(t2.original);
                    }
                }
            }
        }
        return new ArrayList<>(invalidSet);
    }
}
```
### Algorithm
- Define a `Transaction` class to hold parsed data (`name`, `time`, `amount`, `city`) and the original transaction string.
- Create a `HashMap<String, List<Transaction>>` to group transactions by name.
- Iterate through the input array, parse each transaction string into a `Transaction` object, and add it to the corresponding list in the `HashMap`.
- Initialize a `HashSet<String>` to store the final list of invalid transactions, which helps avoid duplicates.
- Iterate through each list of transactions in the `HashMap`'s values:
  - Sort the list by transaction time.
  - Iterate through the sorted list with an index `i`. Let the current transaction be `t1`.
    - If `t1.amount > 1000`, add its original string to the result set.
    - Start a nested loop with index `j` from `i + 1` to check subsequent transactions (`t2`).
    - If `t2.time - t1.time > 60`, break the inner loop, as all further transactions will also be outside the time window.
    - If `t1` and `t2` have different cities, they are a conflicting pair. Add the original strings of both `t1` and `t2` to the result set.
- Convert the result set to a list and return it.

# Solutions
### Java

```java
class Solution {
public
  List<String> invalidTransactions(String[] transactions) {
    Map<String, List<Item>> d = new HashMap<>();
    Set<Integer> idx = new HashSet<>();
    for (int i = 0; i < transactions.length; ++i) {
      var e = transactions[i].split(",");
      String name = e[0];
      int time = Integer.parseInt(e[1]);
      int amount = Integer.parseInt(e[2]);
      String city = e[3];
      d.computeIfAbsent(name, k->new ArrayList<>())
          .add(new Item(time, city, i));
      if (amount > 1000) {
        idx.add(i);
      }
      for (Item item : d.get(name)) {
        if (!city.equals(item.city) && Math.abs(time - item.t) <= 60) {
          idx.add(i);
          idx.add(item.i);
        }
      }
    }
    List<String> ans = new ArrayList<>();
    for (int i : idx) {
      ans.add(transactions[i]);
    }
    return ans;
  }
} class Item {
  int t;
  String city;
  int i;
  Item(int t, String city, int i) {
    this.t = t;
    this.city = city;
    this.i = i;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> invalidTransactions(vector<string> &transactions) {
    unordered_map<string, vector<tuple<int, string, int>>> d;
    unordered_set<int> idx;
    for (int i = 0; i < transactions.size(); ++i) {
      vector<string> e = split(transactions[i], ',');
      string name = e[0];
      int time = stoi(e[1]);
      int amount = stoi(e[2]);
      string city = e[3];
      d[name].push_back({time, city, i});
      if (amount > 1000) {
        idx.insert(i);
      }
      for (auto &[t, c, j] : d[name]) {
        if (c != city && abs(time - t) <= 60) {
          idx.insert(i);
          idx.insert(j);
        }
      }
    }
    vector<string> ans;
    for (int i : idx) {
      ans.emplace_back(transactions[i]);
    }
    return ans;
  }
  vector<string> split(string &s, char delim) {
    stringstream ss(s);
    string item;
    vector<string> res;
    while (getline(ss, item, delim)) {
      res.emplace_back(item);
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def invalidTransactions(self, transactions: List[str]) -> List[str]: d = defaultdict(list) idx = set() for i, x in enumerate(transactions): name, time, amount, city = x . split(",") time, amount = int(time), int(amount) d[name]. append((time, city, i)) if amount > 1000: idx . add(i) for t, c, j in d[name]: if c != city and abs(time - t) <= 60: idx . add(i) idx . add(j) return [transactions[i] for i in idx]

```