Problem Description

You're given information about employees using key-cards to access their office. Each key-card usage is recorded with the employee's name and the time they used it during a single day.

The security system needs to identify employees who use their key-card three or more times within any one-hour period and generate an alert for them.

Input:

• keyName: A list of strings representing employee names
• keyTime: A list of strings representing the times when key-cards were used in 24-hour format "HH:MM"
• keyName[i] and keyTime[i] together represent that employee keyName[i] used their key-card at time keyTime[i]

Output:

• Return a list of unique employee names who triggered the alert (used their key-card 3+ times within a one-hour period)
• The names should be sorted alphabetically in ascending order

Important Notes:

• A one-hour period means any 60-minute window. For example:
  • "10:00" to "11:00" is within a one-hour period (exactly 60 minutes)
  • "22:51" to "23:52" is NOT within a one-hour period (61 minutes)
• All times are from the same day
• An employee triggers an alert if ANY three of their key-card uses fall within a 60-minute window

Example scenario: If an employee uses their key-card at "09:00", "09:30", and "09:50", all three uses are within the one-hour window from "09:00" to "10:00", so this employee would trigger an alert.

Intuition

To find employees who used their key-card 3 or more times within a one-hour window, we need to examine all the times each employee used their card and check if any group of 3 uses falls within 60 minutes.

The key insight is that we need to group all key-card uses by employee name first, since we're looking for patterns in individual employees' usage. This naturally leads us to use a hash table where each employee's name maps to their list of access times.

Once we have all times for each employee, how do we efficiently check if any 3 uses are within a one-hour window? The crucial observation is that if we sort the times chronologically, then any 3 uses within a one-hour window must appear close together in the sorted list. Specifically, if three times are within a one-hour window, the earliest and latest of those three times must be at most 60 minutes apart.

This means we can use a sliding window approach: after sorting an employee's times, we can check consecutive groups of 3 times. For any position i in the sorted list, we just need to check if times[i+2] - times[i] <= 60. If this condition is true, then the three times at positions i, i+1, and i+2 are all within a one-hour window.

To make the time comparisons easier, we convert the time strings from "HH:MM" format to total minutes since midnight. For example, "09:30" becomes 9 * 60 + 30 = 570 minutes. This allows us to directly subtract times to find the difference in minutes.

The algorithm becomes straightforward:

1. Group all access times by employee name
2. For each employee with 3+ accesses, sort their times
3. Check if any window of 3 consecutive sorted times spans 60 minutes or less
4. Collect all employees who trigger the alert and sort their names alphabetically

Learn more about Sorting patterns.

Solution Approach

The solution uses a hash table combined with sorting to efficiently identify employees who trigger the alert.

Step 1: Group access times by employee

We create a hash table d using defaultdict(list) where each key is an employee name and the value is a list of their access times. As we iterate through the input arrays keyName and keyTime, we:

• Convert each time string to minutes since midnight: int(t[:2]) * 60 + int(t[3:])
  • t[:2] extracts the hour portion
  • t[3:] extracts the minute portion
  • For example, "09:30" becomes 9 * 60 + 30 = 570
• Append this converted time to the employee's list in the hash table

Step 2: Check each employee for alert conditions

We iterate through each employee in our hash table. For each employee:

• First check if they have at least 3 access times (len(ts) > 2). If not, skip them
• Sort their access times in ascending order using ts.sort()
• Use a sliding window to check consecutive groups of 3 times:

  for i in range(n - 2):
      if ts[i + 2] - ts[i] <= 60:

  • We iterate from index 0 to n-3 (where n is the total number of times)
  • At each position i, we check if the time at i+2 minus the time at i is within 60 minutes
  • If we find such a window, we add the employee's name to our answer list and break (since we only need to add each name once)

Step 3: Sort and return the result

After checking all employees, we sort the answer list alphabetically using ans.sort() and return it.

Time Complexity: O(n log n) where n is the total number of key-card uses, dominated by sorting operations Space Complexity: O(n) for storing the hash table and result list

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

• keyName = ["alice", "alice", "alice", "bob", "bob", "bob", "bob"]
• keyTime = ["12:01", "12:10", "12:55", "08:00", "08:50", "09:15", "09:45"]

Step 1: Group access times by employee

First, we convert each time to minutes and group by employee name:

• "alice" at "12:01" → 12 * 60 + 1 = 721 minutes
• "alice" at "12:10" → 12 * 60 + 10 = 730 minutes
• "alice" at "12:55" → 12 * 60 + 55 = 775 minutes
• "bob" at "08:00" → 8 * 60 + 0 = 480 minutes
• "bob" at "08:50" → 8 * 60 + 50 = 530 minutes
• "bob" at "09:15" → 9 * 60 + 15 = 555 minutes
• "bob" at "09:45" → 9 * 60 + 45 = 585 minutes

Our hash table d becomes:

{
  "alice": [721, 730, 775],
  "bob": [480, 530, 555, 585]
}

Step 2: Check each employee for alert conditions

For "alice":

• Has 3 access times, so we proceed
• Times are already sorted: [721, 730, 775]
• Check window starting at index 0: 775 - 721 = 54 minutes ≤ 60 ✓
• Alice triggers an alert! Add "alice" to answer list

For "bob":

• Has 4 access times, so we proceed
• Times are already sorted: [480, 530, 555, 585]
• Check window starting at index 0: 555 - 480 = 75 minutes > 60 ✗
• Check window starting at index 1: 585 - 530 = 55 minutes ≤ 60 ✓
• Bob triggers an alert! Add "bob" to answer list

Step 3: Sort and return the result

Answer list: ["alice", "bob"] After sorting alphabetically: ["alice", "bob"]

Output: ["alice", "bob"]

Both employees triggered the security alert because they each used their key-card 3 or more times within a 60-minute window.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm processes n key-card records through the following steps:

1. Initial iteration through all records to parse times and group by names: O(n)
2. For each unique person, their timestamps are sorted. In the worst case, one person has all n records, requiring O(n log n) time for sorting
3. After sorting, checking consecutive windows of 3 elements takes O(k) time per person, where k is the number of records for that person
4. Final sorting of alert names: O(m log m) where m is the number of unique names, and m ≤ n

The dominant operation is the sorting step, giving an overall time complexity of O(n × log n).

Space Complexity: O(n)

The space usage includes:

1. Dictionary d storing all timestamps grouped by names: O(n) space for storing n timestamp values
2. Result list ans storing names that trigger alerts: O(m) space where m is the number of unique names
3. The sorting operations use O(log k) auxiliary space for each person's timestamps

Since we store all n input records in the dictionary structure, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Time Window Interpretation

The Problem: A common mistake is misunderstanding what "within a one-hour period" means. Some developers might check if the difference between the first and last access is exactly 60 minutes, or they might use a strict less-than comparison (< 60) instead of less-than-or-equal (<= 60).

Incorrect Implementation:

# Wrong: Using strict less-than
if times[i + 2] - times[i] < 60:  # This misses exactly 60-minute windows
    alert_names.append(name)
    break

Why It's Wrong: The problem states that accesses at "10:00" to "11:00" should trigger an alert (exactly 60 minutes). Using < 60 would miss this case.

Correct Solution:

# Correct: Using less-than-or-equal
if times[i + 2] - times[i] <= 60:  # Includes exactly 60-minute windows
    alert_names.append(name)
    break

Pitfall 2: Forgetting to Sort Times Before Checking

The Problem: The access times in the input aren't guaranteed to be in chronological order for each employee. If you don't sort the times before checking for the one-hour window, you might miss valid alert conditions.

Incorrect Implementation:

# Wrong: Not sorting times before checking
for name, times in name_to_times.items():
    if len(times) > 2:
        # Directly checking without sorting
        for i in range(len(times) - 2):
            if times[i + 2] - times[i] <= 60:
                alert_names.append(name)
                break

Why It's Wrong: If an employee's times are ["09:50", "09:00", "09:30"], without sorting, you'd check if 09:30 - 09:50 <= 60, which gives a negative number and fails the check, missing the actual alert condition.

Correct Solution:

# Correct: Sort times before checking
times.sort()  # Essential step before checking windows
for i in range(len(times) - 2):
    if times[i + 2] - times[i] <= 60:
        alert_names.append(name)
        break

Pitfall 3: Checking Only Consecutive Pairs Instead of Windows of Three

The Problem: Some might mistakenly check if any two consecutive accesses are within 60 minutes, rather than checking if any three accesses fall within a 60-minute window.

Incorrect Implementation:

# Wrong: Checking pairs instead of windows of three
for i in range(len(times) - 1):
    if times[i + 1] - times[i] <= 60:  # This checks pairs, not groups of three
        alert_names.append(name)
        break

Why It's Wrong: The problem requires THREE or more uses within a one-hour period. Two uses within an hour don't trigger an alert.

Correct Solution:

# Correct: Check windows of three accesses
for i in range(len(times) - 2):  # Note: -2 to ensure we have three elements
    if times[i + 2] - times[i] <= 60:  # Check if all three fit in 60 minutes
        alert_names.append(name)
        break