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

The problem gives us two parallel arrays, keyName and keyTime. Each index represents a single key-card usage event. For example: Together, they describe when a specific employee used their key-card during a single day.

leetcodemediumarrayhash-tablestringsorting

LeetCode Problem 1604

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Sorting

Solution

Problem Understanding

The problem gives us two parallel arrays, keyName and keyTime. Each index represents a single key-card usage event. For example:

keyName[i] = employee name
keyTime[i] = time of usage

Together, they describe when a specific employee used their key-card during a single day.

Our task is to identify every employee who used their key-card at least three times within any one-hour window. The result must contain unique employee names sorted alphabetically.

The important detail is how the one-hour rule is interpreted. If the difference between the earliest and latest access times in a group of three is less than or equal to 60 minutes, then that employee should trigger an alert.

For example:

10:00, 10:40, 11:00

This counts because the difference between 10:00 and 11:00 is exactly 60 minutes.

However:

22:51, 23:52

does not count because the difference is 61 minutes.

The constraints are large:

  • Up to 10^5 access records
  • Employee names can repeat many times
  • Times are given as strings in "HH:MM" format

These constraints immediately tell us that inefficient repeated scanning will likely be too slow. We need a solution close to O(n log n) or better.

Another important observation is that all access events happen within a single day. This means we never need to worry about crossing midnight. Converting times into minutes from midnight is therefore straightforward and safe.

Some important edge cases include:

  • An employee with exactly three accesses within 60 minutes
  • Multiple overlapping one-hour windows
  • Employees with many access records
  • Times that are not initially sorted
  • Employees with fewer than three accesses
  • Accesses exactly 60 minutes apart, which should count

The problem also guarantees that each [keyName[i], keyTime[i]] pair is unique, so we do not need to handle duplicate events.

Approaches

Brute Force Approach

A brute-force solution would group all access times by employee, then examine every possible combination of three accesses for each employee.

For each employee:

  1. Convert all times into minutes.
  2. Sort the times.
  3. Check every triple (i, j, k) where i < j < k.
  4. If times[k] - times[i] <= 60, trigger an alert.

This works because sorting ensures that the earliest and latest times in the triple determine whether all three accesses fit within one hour.

However, this approach is inefficient. If one employee has m access records, checking all triples requires O(m^3) time in the worst case. With up to 10^5 total records, this becomes infeasible.

Key Insight

After sorting an employee's access times, we do not need to check every triple.

If three accesses fit within one hour, then in sorted order they must appear consecutively somewhere in the list.

That means we only need to examine windows of size three:

times[i], times[i+1], times[i+2]

If:

times[i+2] - times[i] <= 60

then we found a valid alert condition.

This dramatically reduces the work. After sorting, we scan linearly through the times.

The optimization works because sorted order guarantees that any wider window would contain a consecutive triple if a valid triple exists.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) worst case O(n) Checks every possible triple of accesses
Optimal O(n log n) O(n) Sorts times and checks consecutive windows of size three

Algorithm Walkthrough

  1. Create a hash map where the key is an employee name and the value is a list of access times.

We use a hash map because it allows efficient grouping of records by employee name. 2. Convert each "HH:MM" string into total minutes from midnight.

For example:

"10:40" -> 640

This makes time comparison simple arithmetic instead of string manipulation. 3. Store each converted time in the corresponding employee's list. 4. For every employee:

  • Sort their list of access times in ascending order.
  • Iterate through the sorted list using a sliding window of size three.
  1. For each index i, check:
times[i + 2] - times[i] <= 60

If true, this employee triggered an alert. 6. Add the employee name to the answer list and stop checking further windows for that employee.

Once an employee qualifies, additional checks are unnecessary. 7. Sort the final answer list alphabetically. 8. Return the sorted result.

Why it works

Sorting the times ensures chronological order. Any valid one-hour interval containing at least three accesses must contain three consecutive accesses in the sorted list. Therefore, checking every consecutive group of three is sufficient to detect all alert conditions. If the earliest and latest times in such a group differ by at most 60 minutes, then all three accesses fall within the required interval.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        employee_times = defaultdict(list)

        for name, time_str in zip(keyName, keyTime):
            hours, minutes = map(int, time_str.split(":"))
            total_minutes = hours * 60 + minutes
            employee_times[name].append(total_minutes)

        alerted_employees = []

        for name, times in employee_times.items():
            times.sort()

            for i in range(len(times) - 2):
                if times[i + 2] - times[i] <= 60:
                    alerted_employees.append(name)
                    break

        alerted_employees.sort()
        return alerted_employees

The implementation starts by using a defaultdict(list) to group access times by employee name. This avoids manual existence checks before inserting values.

Each time string is converted into minutes from midnight. This transformation simplifies comparisons because integer subtraction directly gives the difference in minutes.

After grouping all records, the algorithm processes each employee independently. Their access times are sorted chronologically, allowing us to examine consecutive windows of size three.

The condition:

times[i + 2] - times[i] <= 60

checks whether three accesses occurred within one hour.

Once an employee satisfies the condition, their name is added to the result list and the loop stops early for efficiency.

Finally, the result is sorted alphabetically before returning.

Go Solution

package main

import (
	"sort"
	"strconv"
	"strings"
)

func alertNames(keyName []string, keyTime []string) []string {
	employeeTimes := make(map[string][]int)

	for i := 0; i < len(keyName); i++ {
		name := keyName[i]
		timeStr := keyTime[i]

		parts := strings.Split(timeStr, ":")
		hours, _ := strconv.Atoi(parts[0])
		minutes, _ := strconv.Atoi(parts[1])

		totalMinutes := hours*60 + minutes

		employeeTimes[name] = append(employeeTimes[name], totalMinutes)
	}

	var alertedEmployees []string

	for name, times := range employeeTimes {
		sort.Ints(times)

		for i := 0; i+2 < len(times); i++ {
			if times[i+2]-times[i] <= 60 {
				alertedEmployees = append(alertedEmployees, name)
				break
			}
		}
	}

	sort.Strings(alertedEmployees)

	return alertedEmployees
}

The Go implementation follows the same logic as the Python version. A map[string][]int stores access times for each employee.

Unlike Python's convenient split(":") and tuple unpacking, Go requires explicit parsing with strings.Split and strconv.Atoi.

Sorting is done using sort.Ints, and the final result is alphabetically ordered using sort.Strings.

Go slices automatically grow when using append, which makes them convenient for dynamically collecting access times.

Worked Examples

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"]

Step 1: Build the map

Employee Times
daniel [600, 640, 660]
luis [540, 660, 780, 900]

Step 2: Process daniel

Sorted times:

[600, 640, 660]

Check window:

Window Difference Alert?
600, 640, 660 660 - 600 = 60 Yes

daniel is added to the result.

Step 3: Process luis

Sorted times:

[540, 660, 780, 900]

Check windows:

Window Difference Alert?
540, 660, 780 780 - 540 = 240 No
660, 780, 900 900 - 660 = 240 No

No alert for luis.

Final result:

["daniel"]

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"]

Step 1: Build the map

Employee Times
alice [721, 720, 1080]
bob [1260, 1280, 1290, 1380]

Step 2: Process alice

Sorted times:

[720, 721, 1080]

Check window:

Window Difference Alert?
720, 721, 1080 1080 - 720 = 360 No

No alert.

Step 3: Process bob

Sorted times:

[1260, 1280, 1290, 1380]

Check first window:

Window Difference Alert?
1260, 1280, 1290 1290 - 1260 = 30 Yes

bob is added to the result.

Final result:

["bob"]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(n) Hash map stores all access times

The grouping step processes each record once, which costs O(n) time.

The expensive part is sorting. If an employee has m access records, sorting costs O(m log m). Across all employees, the total sorting complexity is bounded by O(n log n).

The sliding window scan after sorting is linear.

The space complexity is O(n) because all access times are stored in the hash map.

Test Cases

solution = Solution()

# Example 1
assert solution.alertNames(
    ["daniel","daniel","daniel","luis","luis","luis","luis"],
    ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
) == ["daniel"]  # exactly 60 minutes apart

# Example 2
assert solution.alertNames(
    ["alice","alice","alice","bob","bob","bob","bob"],
    ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
) == ["bob"]  # valid triple within 30 minutes

# Single employee with no alert
assert solution.alertNames(
    ["john","john","john"],
    ["10:00","11:01","12:00"]
) == []  # intervals exceed one hour

# Exactly three accesses within one hour
assert solution.alertNames(
    ["emma","emma","emma"],
    ["09:00","09:30","10:00"]
) == ["emma"]  # boundary condition

# More than three accesses with overlapping windows
assert solution.alertNames(
    ["sam","sam","sam","sam"],
    ["10:00","10:20","10:40","11:30"]
) == ["sam"]  # first three trigger alert

# Multiple employees triggering alerts
assert solution.alertNames(
    ["a","a","a","b","b","b"],
    ["01:00","01:20","01:40","02:00","02:30","02:50"]
) == ["a", "b"]  # multiple valid employees

# Unsorted input times
assert solution.alertNames(
    ["zoe","zoe","zoe"],
    ["11:00","10:00","10:30"]
) == ["zoe"]  # sorting required

# Employee with fewer than three accesses
assert solution.alertNames(
    ["max","max"],
    ["08:00","08:30"]
) == []  # insufficient accesses

# Accesses just outside one hour
assert solution.alertNames(
    ["leo","leo","leo"],
    ["10:00","10:30","11:01"]
) == []  # 61 minute gap

# Many accesses, later window triggers
assert solution.alertNames(
    ["kate","kate","kate","kate","kate"],
    ["08:00","09:30","10:00","10:20","10:40"]
) == ["kate"]  # later consecutive triple valid

Test Case Summary

Test Why
Example 1 Verifies exact 60-minute boundary
Example 2 Verifies normal alert detection
No alert case Ensures invalid intervals are rejected
Exactly three accesses Tests minimum qualifying count
Overlapping windows Ensures early valid window works
Multiple employees Verifies independent processing
Unsorted input Confirms sorting is necessary
Fewer than three accesses Tests minimum access requirement
61-minute gap Verifies strict boundary handling
Later valid window Ensures all windows are checked

Edge Cases

One important edge case is when the three accesses are exactly 60 minutes apart. For example:

10:00, 10:30, 11:00

A common mistake is using a strict inequality like < 60 instead of <= 60. The implementation correctly handles this by explicitly checking:

times[i + 2] - times[i] <= 60

Another important edge case is unsorted input. The records are not guaranteed to appear in chronological order. A naive implementation that checks adjacent records without sorting could miss valid alert windows. The solution avoids this problem by sorting each employee's access times before scanning.

Employees with fewer than three accesses are also important. Such employees can never trigger an alert, regardless of timing. The implementation naturally handles this because the loop:

for i in range(len(times) - 2):

does not execute when fewer than three access times exist.

A final subtle edge case involves overlapping windows. Consider:

10:00, 10:20, 10:40, 11:00

Several valid triples exist here. The algorithm correctly identifies the first valid window and immediately stops processing that employee, preventing duplicate entries in the result list.