Leetcode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period

Problem Explanation

The problem is asking to find out the distinct names of the workers who used their key-cards three or more times within a one-hour period.

To solve the problem, we need to maintain a list of all access times for each worker. Then we need to check if there are any three access times within an one-hour period for each worker. If so, then we add the worker's name to the returned list. In the end, we need to sort the returned list in lexicographical order.

One important detail to keep in mind is that, as the problem stated, the time frame "10:00" - "11:00" is considered to be within a one-hour period, while "23:51" - "00:10" is not considered to be within a one-hour period.

Let's walk through the problem using the first example: Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]

We first group all access times for each worker: {"daniel":["10:00","10:40","11:00"], "luis":["09:00","11:00","13:00","15:00"]}

Then we sort the access times for "daniel": ["10:00","10:40","11:00"] Checking if there are any three access times within one hour, we can see that "10:00", "10:40" and "11:00" are within one hour. Therefore, "daniel" used his key-card three or more times within an one-hour period.

For "luis", we first sort his access times: ["09:00","11:00","13:00","15:00"] Checking if there are any three access times within one hour, we can see that there are no such times, since the intervals between all adjacent times are more than one hour.

Therefore, we return ["daniel"] as the result.

Solution Walkthrough

The solution uses a hashmap to store all access times for each worker. Then it checks if there are any three access times within a one-hour period for each worker. If so, it adds the worker's name to the returned list. Afterwards, it sorts the returned list in lexicographical order.

Here is a Python solution for the problem:

1
2python
3class Solution:
4  def transform(self, time: str) -> int:
5    h, m = map(int, time.split(':'))
6    return h * 60 + m
7
8  def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
9    records = collections.defaultdict(list)
10    for name, time in zip(keyName, keyTime):
11      records[name].append(self.transform(time))
12    res = []
13    for name, times in records.items():
14      times.sort()
15      for i in range(len(times) - 2):
16        if times[i + 2] - times[i] <= 60:
17          res.append(name)
18          break
19    return sorted(res)

The transform function is used to convert a time string to minutes. The alertNames function first groups all access times for each worker using a hashmap, then it sorts the access times and checks if there are any three access times within a one-hour period. If so, it adds the worker's name to the res list. Finally, it sorts the res list and returns it.Let's also see how you can implement this solution in JavaScript:

1
2javascript
3var alertNames = function(keyName, keyTime) {
4    const map = new Map();
5    for (let i = 0; i < keyName.length; i++) {
6        const time = convertToMin(keyTime[i]);
7        if (map.has(keyName[i])) {
8            map.get(keyName[i]).push(time);
9        } else {
10            map.set(keyName[i], [time]);
11        }
12    }
13    const res = [];
14    map.forEach((value, key)=> {
15        value.sort((a, b) => a - b);
16        for (let i = 0; i < value.length - 2; i++) {
17            if (value[i + 2] - value[i] <= 60) {
18                res.push(key);
19                break;
20            }
21        }
22    });
23    return res.sort();
24    
25    function convertToMin(timeStr) {
26        const [hr, min] = timeStr.split(':').map(Number);
27        return hr * 60 + min;
28    }
29};

This JavaScript solution is similar to the Python solution described above, but it's using JavaScript's built-in functions like Map(), forEach(), and sort().

And here's how you could solve the problem in Java:

1
2java
3class Solution {
4    public List<String> alertNames(String[] keyName, String[] keyTime) {
5        Map<String, List<Integer>> map = new HashMap<>();
6        for (int i = 0; i < keyName.length; i++) {
7            map.putIfAbsent(keyName[i], new ArrayList<>());
8            map.get(keyName[i]).add(convertToMinutes(keyTime[i]));
9        }
10        List<String> res = new ArrayList<>();
11        for (String name : map.keySet()) {
12            List<Integer> times = map.get(name);
13            Collections.sort(times);
14            for (int i = 0; i < times.size()-2; i++) {
15                if (times.get(i+2) - times.get(i) <= 60) {
16                    res.add(name);
17                    break;
18                }
19            }
20        }
21        Collections.sort(res);
22        return res;
23    }
24    
25    private int convertToMinutes(String timeStr) {
26        String[] time = timeStr.split(":");
27        return Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
28    }
29}

This Java solution follows the same logic as the one in Python. It uses the classes HashMap and ArrayList to store and sort the times for each worker. The method convertToMinutes is helping to convert the string time to minutes.

All of these solutions have a time complexity of O(NlogN) due to the sorting, where N is the number of keyTime entries, and a space complexity of O(N), where N is also the number of keyTime entries.