Alert Using Same Key-Card Three or More Times in a One Hour Period - Video Solutions
LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period
Alert Using Same Key-Card Three or More Times in a One Hour Period - Video Solution
Watch 9 video solutions for Alert Using Same Key-Card Three or More Times in a One Hour Period, a medium level problem involving Array, Hash Table, String. This walkthrough by Happy Coding has 1,513 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
Approach Overview
Problem Overview: Given employee names and key-card usage times, detect employees who used their card three or more times within any one-hour window. Return the employee names that trigger the alert, sorted lexicographically.
Approach 1: Sliding Window with Minute Conversion (O(n log n) time, O(n) space)
Group all access times by employee using a hash table. Convert each HH:MM timestamp into total minutes (hour * 60 + minute) so time comparisons become simple integer differences. For every employee, sort their access times using sorting. Then scan the sorted list with a small sliding window: if times[i] - times[i-2] <= 60, three accesses occurred within one hour and the employee triggers an alert. This works because the sorted order ensures the smallest possible window for any three consecutive entries. The approach is efficient and easy to reason about during interviews.
Approach 2: Heap-Based Tracking (O(n log n) time, O(n) space)
Maintain a min-heap of timestamps per employee. As each access event is processed, convert the time to minutes and push it into that employee's heap. Continuously remove entries older than 60 minutes compared with the current time. If the heap size reaches three, the employee has used their card three times within the one-hour window and should be flagged. The heap structure keeps timestamps ordered automatically while discarding outdated entries efficiently. This approach is useful in streaming scenarios where events arrive chronologically rather than being processed in batches.
Recommended for interviews: The sliding window with minute conversion is the expected solution. It demonstrates good use of grouping, sorting, and window scanning. A brute-force comparison of every triplet would be inefficient, but the sorted sliding window reduces the check to constant work per element. Interviewers usually look for the insight that only three consecutive timestamps need to be compared after sorting.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Minute Conversion | O(n log n) | O(n) | Best general solution. Group times by employee, sort, and check 3-entry windows. |
| Heap-Based Approach | O(n log n) | O(n) | Useful when processing access events as a stream and maintaining a rolling 1-hour window. |