Question

1169. Invalid Transactions

中文文档

Description

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.

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

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.

Solutions

Solution 1: Hash Table + Simulation

We traverse the transaction list. For each transaction, if the amount is greater than 1000, or if the transaction has the same name but different cities and the time interval does not exceed 60 minutes, then add it to the answer.

Specifically, we use a hash table d to record each transaction, where the key is the transaction name, and the value is a list. Each element in the list is a tuple (time, city, index), indicating that a transaction with the number index was conducted in the city city at the moment time. At the same time, we use a hash table idx to record the transaction number in the answer.

We traverse the transaction list. For each transaction, we first add it to the hash table d, and then judge whether its amount is greater than 1000. If so, add its number to the answer. Then we traverse the transactions in the hash table d. If the transaction names are the same but the cities are different and the time interval does not exceed 60 minutes, add its number to the answer.

Finally, we traverse the transaction numbers in the answer and add the corresponding transactions to the answer.

The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Here, $n$ is the length of the transaction list.

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]

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

class Solution {
public:
  vector<string> invalidTransactions(vector<string>& transactions) {
    unordered_map<string, vector<tuple<int, string, int>>> d;
    unordered_set<int> idx;
    for (int i = 0; i < transactions.size(); ++i) {
      vector<string> e = split(transactions[i], ',');
      string name = e[0];
      int time = stoi(e[1]);
      int amount = stoi(e[2]);
      string city = e[3];
      d[name].push_back({time, city, i});
      if (amount > 1000) {
        idx.insert(i);
      }
      for (auto& [t, c, j] : d[name]) {
        if (c != city && abs(time - t) <= 60) {
          idx.insert(i);
          idx.insert(j);
        }
      }
    }
    vector<string> ans;
    for (int i : idx) {
      ans.emplace_back(transactions[i]);
    }
    return ans;
  }

  vector<string> split(string& s, char delim) {
    stringstream ss(s);
    string item;
    vector<string> res;
    while (getline(ss, item, delim)) {
      res.emplace_back(item);
    }
    return res;
  }
};

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
}