<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>

vector<string> splitString(const string& str, char delimiter) {
    vector<string> tokens;
    stringstream ss(str);
    string token;

    while (getline(ss, token, delimiter)) {
        tokens.push_back(token);
    }

    return tokens;
}

template <class T> class ValueCounts {
    unordered_map<T, size_t> d_counts;

public:
    void add(const T& value) { d_counts[value] += 1; }
    bool remove(const T& value) {
        auto it = d_counts.find(value);
        if (it == d_counts.end()) {
            return false;
        }
        it->second -= 1;
        if (it->second == 0) {
            d_counts.erase(it);
        }
        return true;
    }
    void clear() noexcept { d_counts.clear(); }
    size_t size() const noexcept { return d_counts.size(); }
};

class Solution {
public:
    vector<string> invalidTransactions(vector<string>& transactions) {
        struct Transaction {
            string name;
            int16_t timestamp;
            uint16_t value;
            string city;
            size_t idx;
        };
        vector<Transaction> ts;
        for (auto i = 0u; i < transactions.size(); ++i) {
            auto parts = splitString(transactions[i], ',');
            ts.push_back(Transaction{
                .name = parts[0],
                .timestamp = static_cast<int16_t>(stoi(parts[1])),
                .value = static_cast<uint16_t>(stoul(parts[2])),
                .city = parts[3],
                .idx = i,
            });
        }

        unordered_set<size_t> invalid_ids;
        auto mark_invalid = [&ts, &invalid_ids](auto&& valid_time_diff) mutable {
            ValueCounts<string> cities;
            for (int i = 0, k = 0; i < ts.size(); ++i) {
                if (i > 0 && ts[i].name != ts[i - 1].name) {
                    cities.clear();
                    k = i;
                }
                while (k < i && !valid_time_diff(ts[i].timestamp, ts[k].timestamp)) {
                    cities.remove(ts[k].city);
                    k += 1;
                }
                cities.add(ts[i].city);
                if (ts[i].value > 1000 || cities.size() > 1) {
                    invalid_ids.insert(ts[i].idx);
                }
            }
        };

        // Sort by name and timestamp.
        ranges::sort(ts, {}, [](const auto& t) {
            return pair{t.name, t.timestamp};
        });
        mark_invalid([](int16_t current, int16_t prev) {
            return current - prev <= 60;
        });
        // Run in reverse order too.
        ranges::reverse(ts);
        mark_invalid([](int16_t current, int16_t prev) {
            return prev - current <= 60;
        });

        std::vector<string> invalid;
        invalid.reserve(invalid_ids.size());
        for (auto idx : invalid_ids) {
            invalid.push_back(move(transactions[idx]));
        }
        return invalid;
    }
};

22900