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 <= 105
  • keyName.length == keyTime.length
  • keyTime are in the format "HH:MM".
  • [keyName[i], keyTime[i]] is unique.
  • 1 <= keyName[i].length <= 10
  • keyName[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;
        }
    };
    
  • # 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)
                        
                
    

All Problems

All Solutions