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.

&nbsp;
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"]


&nbsp;
Constraints:


	transactions.length &lt;= 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.


class Transaction:
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = 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
            trans_indexes[t.name].append(i)

        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.name, t.time, t.amount, t.city))
                    continue
                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 != t.city:
                        res.append("{},{},{},{}".format(t.name, t.time, t.amount, t.city))
                        break

        return res
class Solution {
  public List<String> invalidTransactions(String[] transactions) {
    Map<String, List<Transaction>> nameToTransaction = new HashMap<>();
    for (int i = 0; i < transactions.length; i++) {
      Transaction t = new Transaction(transactions[i], i);
      nameToTransaction.putIfAbsent(t.name, new ArrayList<>());
      nameToTransaction.get(t.name).add(t);
    }
    List<String> invalid = new ArrayList<>();
    for (List<Transaction> list : nameToTransaction.values()) {
      for (Transaction t : list) {
        if (t.isInvalidAmount()) invalid.add(transactions[t.id]);
        else {
          for (Transaction otherT : list) {
            if (t.isInvalidCity(otherT)) {
              invalid.add(transactions[t.id]);
              break;
            }
          }
        }
      }
    }
    return invalid;
  }
}

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

  Transaction(String s, int id) {
    this.id = id;
    String[] split = s.split(",");
    name = split[0];
    time = Integer.parseInt(split[1]);
    amount = Integer.parseInt(split[2]);
    city = split[3];
  }

  boolean isInvalidAmount() {
    return this.amount > 1000;
  }

  boolean isInvalidCity(Transaction t) {
    return !city.equals(t.city) && Math.abs(t.time - time) <= 60;
  }
}
class Solution {
public:
    /*
      this  question is absolutely frustrating 🙂
    */
    
    /*
        method to split string
    */
    vector<string> split(string s){
      string t="";
        vector<string> v;
        for(int i=0;i<s.length();i++){
            if(s[i]==','){
                v.push_back(t);
                t="";
            }else{
            t+=s[i];    
            }
            
        }
        v.emplace_back(t);
        return v;
    }
    
    /*
        this function checks the second condition.
    */
    bool check(string s,string time,string city,map<string,vector<string>>mp){
        for(auto x:mp[s]){
                     vector<string>out=split(x);
                     int val1=stoi(out[1]);
                     int val2=stoi(time);
                     if(out[3]!=city and abs(val2-val1)<=60){
                        return true;
                     }
                 }
        return false;
    }
    
    
    vector<string> invalidTransactions(vector<string>& transactions) {
        vector<string> res;/* stores the result */
      
        map<string,vector<string>>mp;/* to search for only that person*/
        
        int n=transactions.size();
        
        vector<vector<string>>v(n,vector<string>(4));/*ith v stores info about ith transaction*/
        int c=0;
        
        for(auto x:transactions){
            vector<string> out=split(x);
            v[c]=out;
            mp[out[0]].emplace_back(x);
            c+=1;
        }
        
        for(int i=0;i<n;i++){
            
             if(stoi(v[i][2])>1000){
                 /*
                    check for first condition
                 */
                 res.emplace_back(transactions[i]);
             }else{
                 /*
                    checks for second condition.
                 */
                 if(check(v[i][0],v[i][1],v[i][3],mp)){
                     res.emplace_back(transactions[i]);
                 }
             }
            
        }
     
        return res;
    }
};
var invalidTransactions = function(transactions) {
    const invalid = new Uint8Array(transactions.length).fill(false);

    for(let i = 0; i < transactions.length; i++){
        const [name, time, amount, city] = transactions[i].split(',');

        if(+amount > 1000) invalid[i] = true;

        for(let j = i + 1; j < transactions.length; j++){
            const [name1, time1, amount1, city1] = transactions[j].split(',');

            if(Math.abs(+time - +time1) <= 60 && name === name1 && city !== city1){
                invalid[i] = true;
                invalid[j] = true;
            }
        }
    }

    return invalid.reduce((acc, val, index) => {
        if(val) acc.push(transactions[index])
        return acc;
    }, [])
};
Invalid Transactions