Invalid Transactions

Medium
1750.

Invalid Transactions

Invalid Transactions is a medium coding problem on arrays, strings and hash table, asked in Amazon and Bloomberg interviews.

Each entry of transactions is a string "name,time,amount,city": who paid, the minute it happened, the amount and the city.

A transaction is possibly invalid if either:

  • its amount is greater than 1000, or
  • it happens within (and including) 60 minutes of another transaction with the same name in a different city.

Return every possibly invalid transaction, in the order they appear in transactions. Identical strings at different positions are separate transactions and are reported separately.

Example 1

Input
transactions = ["kai,20,800,pune","kai,75,100,delhi","ravi,30,1500,pune"]
Output
["kai,20,800,pune","kai,75,100,delhi","ravi,30,1500,pune"]
Explanation
The two `kai` transactions are 55 minutes apart in different cities, so both are flagged; `ravi` spent more than 1000.

Example 2

Input
transactions = ["kai,20,800,pune","kai,81,100,delhi"]
Output
[]
Explanation
61 minutes apart is outside the window.

Example 3

Input
transactions = ["asha,10,1001,goa","asha,10,1000,goa"]
Output
["asha,10,1001,goa"]
Explanation
Same city, and 1000 itself is allowed.

Constraints

  • 1 <= transactions.length <= 1000
  • each transactions[i] has the form "{name},{time},{amount},{city}"
  • each {name} and {city} is 1 to 10 lowercase English letters
  • each {time} is an integer in [0, 1000]
  • each {amount} is an integer in [0, 2000]
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} transactions
 * @return {string[]}
 */
var invalidTransactions = function(transactions) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Invalid Transactions — Solution in Python, Java & C++

Invalid Transactions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Invalid Transactions is a medium coding problem on arrays, strings and hash table, asked in Amazon and Bloomberg interviews.

Problem statement

Each entry of transactions is a string "name,time,amount,city": who paid, the minute it happened, the amount and the city.

A transaction is possibly invalid if either:

  • its amount is greater than 1000, or
  • it happens within (and including) 60 minutes of another transaction with the same name in a different city.

Return every possibly invalid transaction, in the order they appear in transactions. Identical strings at different positions are separate transactions and are reported separately.

Example 1

Input: transactions = ["kai,20,800,pune","kai,75,100,delhi","ravi,30,1500,pune"]
Output: ["kai,20,800,pune","kai,75,100,delhi","ravi,30,1500,pune"]
Explanation: The two `kai` transactions are 55 minutes apart in different cities, so both are flagged; `ravi` spent more than 1000.

Example 2

Input: transactions = ["kai,20,800,pune","kai,81,100,delhi"]
Output: []
Explanation: 61 minutes apart is outside the window.

Example 3

Input: transactions = ["asha,10,1001,goa","asha,10,1000,goa"]
Output: ["asha,10,1001,goa"]
Explanation: Same city, and 1000 itself is allowed.

Constraints

  • 1 <= transactions.length <= 1000
  • each transactions[i] has the form "{name},{time},{amount},{city}"
  • each {name} and {city} is 1 to 10 lowercase English letters
  • each {time} is an integer in [0, 1000]
  • each {amount} is an integer in [0, 2000]

Hints for Invalid Transactions

  1. Hint 1

    Parse every string once into its four fields.

  2. Hint 2

    With at most 1000 transactions, comparing every pair is fast enough: 10^6 checks.

  3. Hint 3

    Transaction i is flagged if its amount exceeds 1000, or if some j has the same name, a different city and |time_i - time_j| <= 60. Keep the original strings so you can return them in input order.

How to solve Invalid Transactions

Both rules are local to a transaction and one other transaction, so parse once and test every pair — n <= 1000 makes the quadratic scan cheap and keeps the output in input order for free.

Approach

  1. Split each string on commas into name, time, amount, city (converting the numbers).
  2. For each i: mark it if amount > 1000; otherwise scan all j for the same name, a different city and |time_i - time_j| <= 60.
  3. Collect the original strings of the marked transactions, in index order.

Why it works

The two conditions are exactly the definition, and every transaction is checked against every other one, so nothing is missed. The j != i case is excluded automatically because a transaction never differs from itself in city.

Complexity

  • Time — O(n^2)
  • Space — O(n)

Pitfalls

  • Both transactions of a conflicting pair are invalid, not just the later one.
  • The window is inclusive: exactly 60 minutes apart still counts.
  • Do not de-duplicate — two identical strings are two transactions.
  • An amount of exactly 1000 is fine; only strictly greater is invalid.

Reference solution

Python

from typing import List

def invalidTransactions(transactions: List[str]) -> List[str]:
    parsed = []
    for t in transactions:
        name, time, amount, city = t.split(",")
        parsed.append((name, int(time), int(amount), city))
    res = []
    for i, (name, time, amount, city) in enumerate(parsed):
        bad = amount > 1000
        if not bad:
            for n2, t2, _, c2 in parsed:
                if n2 == name and c2 != city and abs(t2 - time) <= 60:
                    bad = True
                    break
        if bad:
            res.append(transactions[i])
    return res

Java

public static String[] invalidTransactions(String[] transactions) {
    int n = transactions.length;
    String[] names = new String[n], cities = new String[n];
    int[] times = new int[n], amounts = new int[n];
    for (int k = 0; k < n; k++) {
        String[] f = transactions[k].split(",");
        names[k] = f[0];
        times[k] = Integer.parseInt(f[1]);
        amounts[k] = Integer.parseInt(f[2]);
        cities[k] = f[3];
    }
    List<String> res = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        boolean bad = amounts[i] > 1000;
        for (int j = 0; j < n && !bad; j++) {
            if (names[j].equals(names[i]) && !cities[j].equals(cities[i]) && Math.abs(times[j] - times[i]) <= 60) bad = true;
        }
        if (bad) res.add(transactions[i]);
    }
    return res.toArray(new String[0]);
}

C++

vector<string> invalidTransactions(vector<string>& transactions) {
    int n = transactions.size();
    vector<string> names(n), cities(n);
    vector<int> times(n), amounts(n);
    for (int k = 0; k < n; k++) {
        stringstream ss(transactions[k]);
        string part;
        getline(ss, names[k], ',');
        getline(ss, part, ',');
        times[k] = stoi(part);
        getline(ss, part, ',');
        amounts[k] = stoi(part);
        getline(ss, cities[k], ',');
    }
    vector<string> res;
    for (int i = 0; i < n; i++) {
        bool bad = amounts[i] > 1000;
        for (int j = 0; j < n && !bad; j++) {
            if (names[j] == names[i] && cities[j] != cities[i] && abs(times[j] - times[i]) <= 60) bad = true;
        }
        if (bad) res.push_back(transactions[i]);
    }
    return res;
}

JavaScript

var invalidTransactions = function(transactions) {
    var p = [];
    for (var k = 0; k < transactions.length; k++) {
        var f = transactions[k].split(",");
        p.push({ name: f[0], time: parseInt(f[1], 10), amount: parseInt(f[2], 10), city: f[3] });
    }
    var res = [];
    for (var i = 0; i < p.length; i++) {
        var bad = p[i].amount > 1000;
        for (var j = 0; j < p.length && !bad; j++) {
            if (p[j].name === p[i].name && p[j].city !== p[i].city && Math.abs(p[j].time - p[i].time) <= 60) bad = true;
        }
        if (bad) res.push(transactions[i]);
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings