<p>A transaction is possibly invalid if:</p>

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

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

<p>Return a list of <code>transactions</code> that are possibly invalid. You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> transactions = [&quot;alice,20,800,mtv&quot;,&quot;alice,50,100,beijing&quot;]
<strong>Output:</strong> [&quot;alice,20,800,mtv&quot;,&quot;alice,50,100,beijing&quot;]
<strong>Explanation:</strong> 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.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> transactions = [&quot;alice,20,800,mtv&quot;,&quot;alice,50,1200,mtv&quot;]
<strong>Output:</strong> [&quot;alice,50,1200,mtv&quot;]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> transactions = [&quot;alice,20,800,mtv&quot;,&quot;bob,50,1200,mtv&quot;]
<strong>Output:</strong> [&quot;bob,50,1200,mtv&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>transactions.length &lt;= 1000</code></li>
	<li>Each <code>transactions[i]</code> takes the form <code>&quot;{name},{time},{amount},{city}&quot;</code></li>
	<li>Each <code>{name}</code> and <code>{city}</code> consist of lowercase English letters, and have lengths between <code>1</code> and <code>10</code>.</li>
	<li>Each <code>{time}</code> consist of digits, and represent an integer between <code>0</code> and <code>1000</code>.</li>
	<li>Each <code>{amount}</code> consist of digits, and represent an integer between <code>0</code> and <code>2000</code>.</li>
</ul>

/*
   a lousy problem, it's a real case but user name is quite annoying
   also, the string seperation and toInt is annoying too
   just want to focus the interesting way that how to check the invalid transaction
   for a people
   
   
   method:
     use hash table to seperate people. method below focuss on how to record if invalid
     transation
     
     1. brute force: O(n^2)
        sort all transaction by time
        for each transaction
           if amount > 1000, put into res
           else
               check other transactions in -60 <= time <= 60
               if 2 different cities found, put into res
        
     2. hash table + sliding window: O(nlogn)
        use a hash table to record if a transaction is put into res
        this is specific for amount > 1000 to avoid from reinserted
*/
class Solution {
    struct Data {
        string name;
        int time;
        int amount;
        string city;
    };
    
    Data getToken(string &s) {
        Data curr;
        string str;
        for (int i = 0, j = 0; i < s.length(); ++i) {
            if (s[i] == ',') {
                if (j == 0)
                    curr.name = str;
                else if (j == 1)
                    curr.time = getNum(str);
                else
                    curr.amount = getNum(str);
                ++j;
                str = "";
            } else
                str += s[i];
        }
        
        curr.city = str;
        return curr;
    }
    
    int getNum(string &s) {
        int res = 0;
        
        for (auto c: s)
            res = res*10 + c - '0';
        
        return res;
    }
    
public:
    vector<string> invalidTransactions(vector<string>& transactions) {
        vector<string> res;
        unordered_map<string, vector<int>> lut;
        unordered_map<int, Data> lut2;
        
        vector<int> visited(transactions.size(), 0);
        for (int i = 0; i < transactions.size(); ++i) {
            Data curr = getToken(transactions[i]);
            
            if (curr.amount > 1000) {
                res.push_back(transactions[i]);
                visited[i] = 1;
            }
            
            lut[curr.name].push_back(i);
            lut2[i] = curr;
        }
        
        for (auto &[name, v]: lut) {
            sort(v.begin(), v.end(),
                 [&](int i, int j) {
                     return lut2[i].time < lut2[j].time;
                });
            
            int l = 0, k = 0; // l is the leftmost index in 60 mins
                              // k is the leftmost index in 60 mins and still valid
                              //   transaction (i.e. a res candidate but not yet)
                                 
            unordered_map<string, int> w_cities;
            for (int r = 0; r < v.size(); ++r) {
                int curr = v[r];
                ++w_cities[lut2[curr].city];
                while (l < r) {
                    if (lut2[v[l]].time + 60 < lut2[curr].time) {
                        if (--w_cities[lut2[v[l]].city] == 0)
                            w_cities.erase(lut2[v[l]].city);
                        if (k < ++l)
                            ++k;
                    } else {
                        if (w_cities.size() >= 2) {
                            while (k <= r) {
                                if (visited[v[k]] == 0) {
                                    // visited[v[k]] = 1; // no need to record this
                                                          // since k will skip it
                                    res.push_back(transactions[v[k]]);
                                }
                                ++k;
                            }
                        }
                        break;
                    }
                }
            }
        }
        
        return res;
    }
};
16900