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 "22:51" - "23:52" 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").
Constraints:
1 <= keyName.length, keyTime.length <= 105keyName.length == keyTime.lengthkeyTime[i] is in the format "HH:MM".[keyName[i], keyTime[i]] is unique.1 <= keyName[i].length <= 10keyName[i] contains only lowercase English letters.In #1604 Alert Using Same Key-Card Three or More Times in a One Hour Period, the goal is to identify employees who use their key-card at least three times within any one-hour window. A practical approach is to group all access times by employee using a hash table where the key is the employee name and the value is a list of times.
Convert each time from HH:MM format into total minutes for easier comparison. For each employee, sort the list of access times and scan it using a small sliding window. If the difference between the first and third time in a consecutive group is less than or equal to 60 minutes, that employee should be flagged.
Finally, collect all flagged employee names and return them in lexicographically sorted order. The main cost comes from sorting the time lists, giving a time complexity of O(n log n), while the grouping structure requires O(n) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Sorting + Sliding Window | O(n log n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Group the times by the name of the card user, then sort each group
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Converting time from HH:MM format to total minutes simplifies comparisons between timestamps. It allows quick arithmetic checks to determine whether three accesses occur within a 60-minute period.
Problems like this are common in technical interviews because they test hashing, sorting, and sliding window techniques. While the exact question may vary, similar patterns frequently appear in FAANG-style coding interviews.
A hash table (or dictionary) is the best structure to group key-card usage times by employee name. Combined with arrays or lists to store times and sorting for ordering, it enables efficient detection of one-hour activity windows.
The optimal approach groups key-card usage by employee using a hash map, converts times to minutes, and sorts each employee's access times. By scanning with a sliding window of three consecutive times, you can quickly detect if they fall within a 60-minute window.