Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1604.html
1604. Alert Using Same Key-Card Three or More Times in a One Hour Period (Medium)
Leetcode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker's name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.
You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person's name and the time when their key-card was used in a single day.
Access times are given in the 24-hour time format "HH:MM", such as "23:51" and "09:49".
Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.
Notice that "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.
Example 1:
Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").
Example 2:
Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").
Example 3:
Input: keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"] Output: []
Example 4:
Input: keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"] Output: ["clare","leslie"]
Constraints:
1 <= keyName.length, keyTime.length <= 105keyName.length == keyTime.lengthkeyTimeare in the format "HH:MM".[keyName[i], keyTime[i]]is unique.1 <= keyName[i].length <= 10keyName[i] contains only lowercase English letters.
Related Topics:
String, Ordered Map
Solution 1. Hash Map
Use unordered_map<string, vector<int>> to group the times by name.
For the times of each person, sort the times. If there is any times[i] - times[i - 2] <= 60, then the person should get alerted.
// OJ: https://leetcode.com/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
unordered_map<string, vector<int>> m;
for (int i = 0; i < keyName.size(); ++i) {
auto &key = keyName[i], &time = keyTime[i];
int t = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));
m[key].push_back(t);
}
vector<string> ans;
for (auto &[key, times] : m) {
sort(begin(times), end(times));
for (int i = 2; i < times.size(); ++i) {
if (times[i] - times[i - 2] > 60) continue;
ans.push_back(key);
break;
}
}
sort(begin(ans), end(ans));
return ans;
}
};
Java
-
class Solution { public List<String> alertNames(String[] keyName, String[] keyTime) { Map<String, List<String>> map = new HashMap<String, List<String>>(); int length = keyName.length; for (int i = 0; i < length; i++) { String name = keyName[i]; String time = keyTime[i]; List<String> list = map.getOrDefault(name, new ArrayList<String>()); list.add(time); map.put(name, list); } List<String> alertList = new ArrayList<String>(); Set<String> keySet = map.keySet(); for (String name : keySet) { List<String> list = map.get(name); Collections.sort(list); int size = list.size(); for (int i = 2; i < size; i++) { String time1 = list.get(i - 2), time2 = list.get(i); int hour1 = Integer.parseInt(time1.substring(0, 2)), minute1 = Integer.parseInt(time1.substring(3)); int hour2 = Integer.parseInt(time2.substring(0, 2)), minute2 = Integer.parseInt(time2.substring(3)); int difference = (hour2 * 60 + minute2) - (hour1 * 60 + minute1); if (difference <= 60) { alertList.add(name); break; } } } Collections.sort(alertList); return alertList; } } -
// OJ: https://leetcode.com/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period/ // Time: O(NlogN) // Space: O(N) class Solution { public: vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) { unordered_map<string, vector<int>> m; for (int i = 0; i < keyName.size(); ++i) { auto &key = keyName[i], &time = keyTime[i]; int t = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3)); m[key].push_back(t); } vector<string> ans; for (auto &[key, times] : m) { sort(begin(times), end(times)); for (int i = 2; i < times.size(); ++i) { if (times[i] - times[i - 2] > 60) continue; ans.push_back(key); break; } } sort(begin(ans), end(ans)); return ans; } }; -
class Solution: def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]: d = defaultdict(list) for name, t in zip(keyName, keyTime): t = int(t[:2]) * 60 + int(t[3:]) d[name].append(t) ans = [] for name, ts in d.items(): if (n := len(ts)) > 2: ts.sort() for i in range(n - 2): if ts[i + 2] - ts[i] <= 60: ans.append(name) break ans.sort() return ans ############ # 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period # https://leetcode.com/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period/ class Solution: def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]: def convertTime(time): return int("".join(time.split(":"))) dic = {} for name,time in zip(keyName,keyTime): time = convertTime(time) if name not in dic: dic[name] = [time] else: dic[name].append(time) res = [] for name in dic: timeList = sorted(dic[name]) tmp = [] c = 0 for time in timeList: while tmp and time - tmp[0] > 100: tmp.pop(0) if c > 0: c -= 1 c += 1 tmp.append(time) if c >= 3: res.append(name) break return sorted(res)