Invalid Transactions

Medium Arrays & Hashing Hashing Original on LeetCode

Reported atStripeBloomberg

Invalid Transactions is a medium arrays & hashing problem solved with the hashing pattern. The best approach, optimal (group by name + sliding time window), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from compare every pair up.

Problem

Each entry of transactions is a string "name,time,amount,city": who paid, at which minute, how much, and where.

A transaction is possibly invalid if its amount is greater than 1000, or if the same person made another transaction in a different city at most 60 minutes before or after it (the 60-minute boundary counts).

Return every possibly invalid transaction, as the original strings, in any order. If the same string appears several times and is invalid, include each copy.

Examples

Example 1

Input
transactions = ["ravi,100,300,pune", "ravi,140,250,goa", "mira,500,1200,goa"]
Output
["ravi,100,300,pune", "ravi,140,250,goa", "mira,500,1200,goa"]
Why
ravi's two transactions are 40 minutes apart in different cities, so both are flagged; mira's is over 1000.

Example 2

Input
transactions = ["lena,10,800,oslo", "lena,71,900,bergen", "lena,200,1001,oslo"]
Output
["lena,200,1001,oslo"]
Why
The first two are 61 minutes apart, which is outside the window; only the third exceeds 1000.

Example 3

Input
transactions = ["tom,30,20,rome", "ann,50,20,milan", "tom,90,40,rome"]
Output
[]
Why
tom stays in one city and the city change is by a different person, so nothing is invalid.

Constraints

  • 1 <= transactions.length <= 1000
  • Each transaction has the form "name,time,amount,city".
  • name and city are 1 to 10 lowercase English letters.
  • 0 <= time <= 1000 and 0 <= amount <= 2000, written as integers without leading zeros.
  • The answer may be returned in any order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Compare every pairO(n²)O(n)
Optimal (group by name + sliding time window)O(n log n)O(n)

1Compare every pair

TimeO(n²)All n(n - 1) / 2 pairs are compared, each in O(1) after parsing (names and cities are at most 10 characters).
SpaceO(n)The parsed fields and the marks.

Parse all transactions. Mark one invalid if its amount is over 1000, or if some other transaction has the same name, a different city and a time at most 60 minutes away.

  1. Split each string by commas into name, time, amount, city.
  2. For each pair (i, j): if the names match, the cities differ and |time_i - time_j| <= 60, mark both.
  3. Also mark every transaction with amount > 1000.
  4. Return the original strings of the marked transactions.
class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        int n = transactions.length;
        String[] name = new String[n], city = new String[n];
        int[] time = new int[n], amount = new int[n];
        for (int i = 0; i < n; i++) {
            String[] p = transactions[i].split(",");
            name[i] = p[0];
            time[i] = Integer.parseInt(p[1]);
            amount[i] = Integer.parseInt(p[2]);
            city[i] = p[3];
        }
        boolean[] bad = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (amount[i] > 1000) bad[i] = true;
            for (int j = i + 1; j < n; j++) {
                if (name[i].equals(name[j]) && !city[i].equals(city[j]) && Math.abs(time[i] - time[j]) <= 60) {
                    bad[i] = true;
                    bad[j] = true;
                }
            }
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (bad[i]) res.add(transactions[i]);
        }
        return res;
    }
}

2Optimal (group by name + sliding time window)

TimeO(n log n)Sorting the groups dominates; the window pointers make one forward pass per group.
SpaceO(n)Parsed fields, the groups and the window counter.

Only transactions of the same person can conflict, so group indices by name and sort each group by time. For the transaction at time t, the partners that matter are exactly those with time in [t - 60, t + 60]. Both ends of that window only move forward as t grows, so two pointers plus a city counter tell you in O(1) amortized whether the window holds more than one distinct city.

  1. Parse every transaction and group the indices by name.
  2. Sort each group by time. Keep pointers lo and hi and a map city -> count for the window.
  3. For each transaction k in the group at time t: advance hi while time[hi] <= t + 60, adding its city; advance lo while time[lo] < t - 60, removing its city.
  4. If the map has more than one city, mark k invalid.
  5. Also mark every amount > 1000, then return the marked original strings.
class Solution {
    public List<String> invalidTransactions(String[] transactions) {
        int n = transactions.length;
        String[] city = new String[n];
        int[] time = new int[n], amount = new int[n];
        Map<String, List<Integer>> byName = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String[] p = transactions[i].split(",");
            time[i] = Integer.parseInt(p[1]);
            amount[i] = Integer.parseInt(p[2]);
            city[i] = p[3];
            byName.computeIfAbsent(p[0], k -> new ArrayList<>()).add(i);
        }
        boolean[] bad = new boolean[n];
        for (List<Integer> group : byName.values()) {
            group.sort((a, b) -> Integer.compare(time[a], time[b]));
            Map<String, Integer> inWindow = new HashMap<>();
            int m = group.size(), lo = 0, hi = 0;
            for (int k = 0; k < m; k++) {
                int t = time[group.get(k)];
                while (hi < m && time[group.get(hi)] <= t + 60) {
                    inWindow.merge(city[group.get(hi)], 1, Integer::sum);
                    hi++;
                }
                while (time[group.get(lo)] < t - 60) {
                    String c = city[group.get(lo)];
                    if (inWindow.merge(c, -1, Integer::sum) == 0) inWindow.remove(c);
                    lo++;
                }
                if (inWindow.size() > 1) bad[group.get(k)] = true;
            }
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (bad[i] || amount[i] > 1000) res.add(transactions[i]);
        }
        return res;
    }
}

Edge cases to test

  • Exactly 60 minutes apart counts as within the window
  • Amount exactly 1000 is fine; 1001 is not
  • Identical duplicate transactions: each copy is reported separately if invalid
  • Same city at the same time is never a conflict
  • Different names in different cities never conflict

Hints

Hint 1

Parse each string into its four fields first.

Hint 2

Checking every pair of transactions is fast enough for 1000 entries, but think about how to do better.

Hint 3

Group by name and sort each group by time. For each transaction, the others within 60 minutes form a window that only slides forward; count cities inside it.

FAQ

What is the best time complexity for Invalid Transactions?

Optimal (group by name + sliding time window) runs in O(n log n) time and O(n) extra space. Sorting the groups dominates; the window pointers make one forward pass per group.

Which pattern does Invalid Transactions use?

It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.

Is there a brute force solution for Invalid Transactions?

Yes. Compare every pair takes O(n²) time and O(n) space. Parse all transactions.

Which edge cases should I test for Invalid Transactions?

Exactly 60 minutes apart counts as within the window; Amount exactly 1000 is fine; 1001 is not; Identical duplicate transactions: each copy is reported separately if invalid; Same city at the same time is never a conflict; Different names in different cities never conflict.