Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1169.html

1169. Invalid Transactions (Medium)

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.

Each transaction string transactions[i] consists of comma separated values representing the name, time (in minutes), amount, and city of the transaction.

Given a list of transactions, return a list of transactions that are possibly invalid.  You may return the answer in any order.

 

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

 

Constraints:

  • transactions.length <= 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.

Related Topics:
Array, String

Solution 1. Brute force

// OJ: https://leetcode.com/problems/invalid-transactions/
// Time: O(N^2)
// Space: O(N)
struct Transaction {
    string name;
    int time;
    int amount;
    string city;
    Transaction(string t) {
        istringstream ss(t);
        getline(ss, name, ',');
        string token;
        getline(ss, token, ',');
        time = stoi(token);
        getline(ss, token, ',');
        amount = stoi(token);
        ss >> city;
    }
};
class Solution {
public:
    vector<string> invalidTransactions(vector<string>& A) {
        vector<Transaction> B;
        unordered_set<int> invalid;
        for (int i = 0; i < A.size(); ++i) {
            auto t = Transaction(A[i]);
            if (t.amount > 1000) invalid.insert(i);
            B.push_back(t);
        }
        for (int i = 0; i < A.size(); ++i) {
            for (int j = i + 1; j < A.size(); ++j) {
                if (B[i].name == B[j].name && abs(B[i].time - B[j].time) <= 60 && B[i].city != B[j].city) {
                    invalid.insert(i);
                    invalid.insert(j);
                }
            }
        }
        vector<string> ans;
        for (int i : invalid) ans.push_back(A[i]);
        return ans;
    }
};

Solution 1. Sliding Window

// OJ: https://leetcode.com/problems/invalid-transactions/
// Time: O(NlogN)
// Space: O(N)
struct Transaction {
    string name;
    int time;
    int amount;
    string city;
    Transaction(string t) {
        istringstream ss(t);
        getline(ss, name, ',');
        string token;
        getline(ss, token, ',');
        time = stoi(token);
        getline(ss, token, ',');
        amount = stoi(token);
        ss >> city;
    }
};
class Solution {
public:
    vector<string> invalidTransactions(vector<string>& A) {
        unordered_map<string, vector<int>> m;
        vector<Transaction> B;
        unordered_set<int> invalid;
        for (int i = 0; i < A.size(); ++i) {
            auto t = Transaction(A[i]);
            if (t.amount > 1000) invalid.insert(i);
            m[t.name].push_back(i);
            B.push_back(t);
        }
        for (auto &[p, ids] : m) {
            sort(begin(ids), end(ids), [&](int a, int b) { return B[a].time < B[b].time; });
            int i = 0, j = 0, k = 0, N = ids.size();
            unordered_map<string, int> cities;
            while (j < N) {
                while (B[ids[j]].time - B[ids[i]].time > 60) {
                    auto &c = B[ids[i++]];
                    if (--cities[c.city] == 0) cities.erase(c.city);
                }
                if (B[ids[j]].time - B[ids[i]].time <= 60) {
                    auto &c = B[ids[j++]];
                    cities[c.city]++;
                    if (cities.size() > 1) {
                        for (k = max(k, i); k < j; ++k) invalid.insert(ids[k]);
                    }
                }
            }
        }
        vector<string> ans;
        for (int i : invalid) ans.push_back(A[i]);
        return ans;
    }
};
  • class Solution {
        public List<String> invalidTransactions(String[] transactions) {
            int length = transactions.length;
            Transaction[] transactionsArray = new Transaction[length];
            for (int i = 0; i < length; i++) {
                String transactionStr = transactions[i];
                String[] array = transactionStr.split(",");
                String name = array[0];
                int time = Integer.parseInt(array[1]);
                int amount = Integer.parseInt(array[2]);
                String city = array[3];
                Transaction curTransaction = new Transaction(name, time, amount, city);
                transactionsArray[i] = curTransaction;
            }
            Arrays.sort(transactionsArray);
            Set<String> invalidSet = new HashSet<String>();
            Transaction transaction0 = transactionsArray[0];
            if (transaction0.amount > 1000)
                invalidSet.add(transaction0.toString());
            int prevIndex = 0;
            for (int i = 1; i < length; i++) {
                Transaction curTransaction = transactionsArray[i];
                if (curTransaction.amount > 1000)
                    invalidSet.add(curTransaction.toString());
                while (!transactionsArray[prevIndex].name.equals(curTransaction.name) || curTransaction.time - transactionsArray[prevIndex].time > 60)
                    prevIndex++;
                boolean flag = false;
                for (int j = prevIndex; j < i; j++) {
                    Transaction prevTransaction = transactionsArray[j];
                    if (curTransaction.name.equals(prevTransaction.name) && curTransaction.time - prevTransaction.time <= 60 && !curTransaction.city.equals(prevTransaction.city)) {
                        invalidSet.add(prevTransaction.toString());
                        flag = true;
                    }
                }
                if (flag)
                    invalidSet.add(curTransaction.toString());
            }
            List<String> invalidTransactionsList = new ArrayList<String>(invalidSet);
            return invalidTransactionsList;
        }
    }
    
    class Transaction implements Comparable<Transaction> {
        String name;
        int time;
        int amount;
        String city;
    
        public Transaction(String name, int time, int amount, String city) {
            this.name = name;
            this.time = time;
            this.amount = amount;
            this.city = city;
        }
    
        public int compareTo(Transaction transaction2) {
            if (!this.name.equals(transaction2.name))
                return this.name.compareTo(transaction2.name);
            else if (this.time != transaction2.time)
                return this.time - transaction2.time;
            else if (!this.city.equals(transaction2.city))
                return this.city.compareTo(transaction2.city);
            else
                return this.amount - transaction2.amount;
        }
    
        public String toString() {
            return name + "," + time + "," + amount + "," + city;
        }
    }
    
    ############
    
    class Solution {
        public List<String> invalidTransactions(String[] transactions) {
            Map<String, List<Item>> d = new HashMap<>();
            Set<Integer> idx = new HashSet<>();
            for (int i = 0; i < transactions.length; ++i) {
                var e = transactions[i].split(",");
                String name = e[0];
                int time = Integer.parseInt(e[1]);
                int amount = Integer.parseInt(e[2]);
                String city = e[3];
                d.computeIfAbsent(name, k -> new ArrayList<>()).add(new Item(time, city, i));
                if (amount > 1000) {
                    idx.add(i);
                }
                for (Item item : d.get(name)) {
                    if (!city.equals(item.city) && Math.abs(time - item.t) <= 60) {
                        idx.add(i);
                        idx.add(item.i);
                    }
                }
            }
            List<String> ans = new ArrayList<>();
            for (int i : idx) {
                ans.add(transactions[i]);
            }
            return ans;
        }
    }
    
    class Item {
        int t;
        String city;
        int i;
    
        Item(int t, String city, int i) {
            this.t = t;
            this.city = city;
            this.i = i;
        }
    }
    
  • // OJ: https://leetcode.com/problems/invalid-transactions/
    // Time: O(N^2)
    // Space: O(N)
    struct Transaction {
        string name;
        int time;
        int amount;
        string city;
        Transaction(string t) {
            istringstream ss(t);
            getline(ss, name, ',');
            string token;
            getline(ss, token, ',');
            time = stoi(token);
            getline(ss, token, ',');
            amount = stoi(token);
            ss >> city;
        }
    };
    class Solution {
    public:
        vector<string> invalidTransactions(vector<string>& A) {
            vector<Transaction> B;
            unordered_set<int> invalid;
            for (int i = 0; i < A.size(); ++i) {
                auto t = Transaction(A[i]);
                if (t.amount > 1000) invalid.insert(i);
                B.push_back(t);
            }
            for (int i = 0; i < A.size(); ++i) {
                for (int j = i + 1; j < A.size(); ++j) {
                    if (B[i].name == B[j].name && abs(B[i].time - B[j].time) <= 60 && B[i].city != B[j].city) {
                        invalid.insert(i);
                        invalid.insert(j);
                    }
                }
            }
            vector<string> ans;
            for (int i : invalid) ans.push_back(A[i]);
            return ans;
        }
    };
    
  • class Solution:
        def invalidTransactions(self, transactions: List[str]) -> List[str]:
            d = defaultdict(list)
            idx = set()
            for i, x in enumerate(transactions):
                name, time, amount, city = x.split(",")
                time, amount = int(time), int(amount)
                d[name].append((time, city, i))
                if amount > 1000:
                    idx.add(i)
                for t, c, j in d[name]:
                    if c != city and abs(time - t) <= 60:
                        idx.add(i)
                        idx.add(j)
            return [transactions[i] for i in idx]
    
    ############
    
    # 1169. Invalid Transactions
    # https://leetcode.com/problems/invalid-transactions/
    
    class Solution:
        def invalidTransactions(self, transactions: List[str]) -> List[str]:
            ans = []
            length = len(transactions)
            if not length: return ans
            name,time,money,city = [],[],[],[]
            add = [1] * length
            
            for trans in transactions:
                tran = trans.split(',')
                name.append(tran[0])
                time.append(int(tran[1]))
                money.append(int(tran[2]))
                city.append(tran[3])
                
            for i in range(length):
                if money[i] > 1000:
                    add[i] = False
                for j in range(i+1,length):
                    if name[i] == name[j] and abs(time[i]-time[j])<= 60 and city[i]!=city[j]:
                        add[i] = False
                        add[j] = False
                        
            for ind,val in enumerate(add):
                if not val:
                    ans.append(transactions[ind])
                    
            return ans
    
    
  • func invalidTransactions(transactions []string) (ans []string) {
    	d := map[string][]tuple{}
    	idx := map[int]bool{}
    	for i, x := range transactions {
    		e := strings.Split(x, ",")
    		name := e[0]
    		time, _ := strconv.Atoi(e[1])
    		amount, _ := strconv.Atoi(e[2])
    		city := e[3]
    		d[name] = append(d[name], tuple{time, city, i})
    		if amount > 1000 {
    			idx[i] = true
    		}
    		for _, item := range d[name] {
    			if city != item.city && abs(time-item.t) <= 60 {
    				idx[i], idx[item.i] = true, true
    			}
    		}
    	}
    	for i := range idx {
    		ans = append(ans, transactions[i])
    	}
    	return
    }
    
    func abs(x int) int {
    	if x < 0 {
    		return -x
    	}
    	return x
    }
    
    type tuple struct {
    	t    int
    	city string
    	i    int
    }
    

All Problems

All Solutions