{x}
blog image

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

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 <= 105
  • keyName.length == keyTime.length
  • keyTime[i] is in the format "HH:MM".
  • [keyName[i], keyTime[i]] is unique.
  • 1 <= keyName[i].length <= 10
  • keyName[i] contains only lowercase English letters.

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

This problem requires identifying employees who used their keycards three or more times within a one-hour period. The solution uses a hash table to efficiently store and process the data.

Approach:

  1. Data Storage: A hash table (dictionary in Python, HashMap in Java, unordered_map in C++, map in Go, etc.) is used to store employee names as keys and a list of their keycard access times as values. The times are converted from HH:MM format to total minutes from midnight for easier comparison.

  2. Iteration and Alert Condition Check: The code iterates through the hash table. For each employee:

    • It checks if the number of access times is greater than or equal to 3. If not, the employee is skipped.
    • If the number of access times is 3 or more, the access times are sorted in ascending order. This allows for efficient checking of consecutive times.
    • A nested loop checks if any three consecutive access times are within a 60-minute window (one hour). If such a window is found, the employee's name is added to the list of employees who triggered an alert.

  3. Result Handling: Finally, the list of alerted employees is sorted alphabetically and returned.

Time Complexity Analysis:

  • Hash Table Population: O(N), where N is the number of keycard entries, because inserting each key-value pair into the hash table takes constant time on average.
  • Iteration and Sorting: O(M log M) in the worst case, where M is the maximum number of keycard entries for a single employee. This is due to sorting the access times for each employee. The outer loop iterates through the employees, and the inner loop (checking for the 60-minute window) takes linear time in the worst case.
  • Overall: The dominant factor is the sorting step, leading to an overall time complexity of O(N log M), which is approximately O(N log N) in the worst-case scenario if the entries are relatively evenly distributed among employees. In practice, M is often much smaller than N.

Space Complexity Analysis:

  • The space complexity is dominated by the hash table, which stores the employee names and their access times. In the worst-case scenario, where each employee has many entries, the space complexity could approach O(N). However, in a more realistic scenario with a reasonable distribution of entries among employees, the space complexity is typically less than O(N).

Code Examples (Multiple Languages):

The code provided in the original response demonstrates the solution effectively in several programming languages. The core logic remains consistent across all examples. The differences primarily lie in syntax and specific data structure implementations. The comments within the code itself further clarify the steps involved.