1604. Alert Using Same Key-Card Three or More Times in a One Hour Period
Problem Description
The problem provides data on the use of key-cards by LeetCode company workers for unlocking office doors. The security system logs the name of the worker and the time when the key-card was used. An alert is triggered if any worker uses the key-card three or more times within any one-hour period during a single day.
The task is to write a program that analyzes this data. You're given two lists: keyName
, containing the names of the workers, and keyTime
, containing the corresponding times when their key-cards were used. The program must output a list of unique names of workers who triggered an alert due to frequent use of their key-card within any given one-hour period. This output list should be sorted in alphabetical order.
Access times in keyTime
are in a 24-hour format, denoted as "HH:MM". It is important to note that overlapping hours, such as from "10:00" to "11:00", are considered a one-hour period, but times from "22:51" to "23:52" are not since they span into a new one-hour period.
Intuition
To solve this problem, the primary goal is to track the usage frequency of key-cards by each worker within a one-hour period. Here, we can follow these steps as part of our intuition towards the solution:
- Parse each time entry in
keyTime
from "HH:MM" format to minutes only. This makes it easier to calculate the difference between times. - Group all the time entries by worker names using a dictionary where the key is the worker's name and the value is a list of their corresponding times in minutes.
- Iterate over each worker's list of time entries:
- If a worker's list contains less than three time entries, no alert would be triggered for this worker, so they can be skipped.
- Sort the list of times for each worker, because to find a period of one hour where the card was used at least three times, the times need to be in order.
- Look for any three consecutive time entries (after sorting) within a 60-minute window. If there are such entries, add the worker's name to the list of those who triggered an alert.
- Finally, sort the list of workers who triggered an alert in alphabetical order and return it.
This approach is efficient since it minimizes sorting to only the necessary times (those belonging to the same worker), instead of sorting all time entries globally. The lookup to check for the one-hour frequency is optimized by only comparing between three consecutive time entries due to the sorted nature of the lists.
Learn more about Sorting patterns.
Solution Approach
The implementation of the solution given applies several common programming patterns and data structures to efficiently address the problem. Let's break down how the provided Python solution accomplishes this task:
-
The
defaultdict
from Python'scollections
module is used to create a dictionary that will automatically generate a list for each new key. This data structure helps group all the key-card use times by worker name. -
The solution iterates through the combined
keyName
andkeyTime
lists usingzip
, which allows us to process the corresponding elements of these two lists in pairs. -
Each time in the
keyTime
list is converted from the "HH:MM" string format to a total number of minutes using integer arithmetic. This conversion allows for much simpler comparisons since we can now just subtract the times to get the difference in minutes:1t = int(t[:2]) * 60 + int(t[3:])
Here,
t[:2]
extracts the hours component andt[3:]
extracts the minutes component from the string, which are then converted to an integer total number of minutes. -
For each worker, we sort their list of time entries, necessary to find the sequence of three time entries within a one-hour window (60 minutes). The sorting assures us that no three consecutive time entries can be more than one hour apart if there is no such trio within the sorted list.
-
The algorithm then iterates over each sorted time list for the workers, only if there are at least three time entries (
n := len(ts)
). Python’s Walrus operator:=
is used for assignment and comparison in a single expression. -
To check for a one-hour period alert, a window of three consecutive times
ts[i]
,ts[i + 1]
, andts[i + 2]
is examined. If the difference betweents[i + 2]
andts[i]
is less than or equal to 60 minutes, we confirm that there were at least three uses within a one-hour period:1if ts[i + 2] - ts[i] <= 60:
If this condition is met, the worker’s name is added to the
ans
list, and the loop breaks since one alert is sufficient to flag the worker. -
After all the workers have been checked, the list of workers who triggered an alert (
ans
) is sorted alphabetically to meet the specified output requirement. -
The sorted list
ans
is returned, containing all the worker names that triggered an alert, sorted in ascending alphabetical order.
By using these steps, the algorithm is able to efficiently check each worker against the alert condition while maintaining the order of names as required for the output.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach.
Suppose keyName
and keyTime
are as follows:
1keyName = ["Alice", "Bob", "Alice", "Alice", "Bob"] 2keyTime = ["10:00", "10:20", "11:00", "12:00", "10:40"]
-
Convert
keyTime
entries to minutes:1["10:00", "10:20", "11:00", "12:00", "10:40"] 2becomes 3[600, 620, 660, 720, 640] # after conversion
-
Group by worker names using
defaultdict
:1{"Alice": [600, 660, 720], "Bob": [620, 640]}
-
The times associated with Alice are [600, 660, 720], and for Bob, they are [620, 640]. Alice's times contain more than two entries, but Bob's do not, so Bob can be skipped.
-
Sort the times for each worker. In this case, Alice's times are already in order.
-
For Alice, check three consecutive time entries:
1Between 600, 660 - Not within a one-hour window (difference is 60 minutes). 2Between 660, 720 - Not within a one-hour window (difference is 60 minutes).
Since there are no three consecutive entries within a 60-minute window for Alice, she does not trigger an alert.
-
No alerts are triggered for any worker, so the final step of sorting the
ans
list is trivial as it is empty.
Hence, the output would be an empty list []
, indicating that no worker triggered an alert in this example.
Solution Implementation
1from collections import defaultdict
2
3class Solution:
4 def alertNames(self, keyNames: List[str], keyTimes: List[str]) -> List[str]:
5 # Create a dictionary to store times associated with each name
6 name_times_dict = defaultdict(list)
7
8 # Convert time strings to minutes and store them in the dictionary
9 for name, time_str in zip(keyNames, keyTimes):
10 time_minutes = int(time_str[:2]) * 60 + int(time_str[3:])
11 name_times_dict[name].append(time_minutes)
12
13 # Initialize a list to hold the names of individuals who should be alerted
14 alert_names = []
15
16 # Iterate through the dictionary to check for each person
17 for name, times in name_times_dict.items():
18 times_count = len(times)
19 # Only proceed if there are more than two time points
20 if times_count > 2:
21 # Sort the times in ascending order
22 times.sort()
23 # Check for any three consecutive times within a 60 minutes window
24 for i in range(times_count - 2):
25 if times[i + 2] - times[i] <= 60:
26 # If the condition is met, add the person's name to the alert list
27 alert_names.append(name)
28 break # No need to check further for this person
29
30 # Sort the list of names alphabetically before returning
31 alert_names.sort()
32 return alert_names
33
1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4import java.util.Map;
5import java.util.HashMap;
6
7class Solution {
8 public List<String> alertNames(String[] keyNames, String[] keyTimes) {
9 // Map to track the time (converted to minutes) at which each keyName logs in
10 Map<String, List<Integer>> nameToTimesMap = new HashMap<>();
11
12 // Iterate over the input arrays to populate the nameToTimesMap
13 for (int i = 0; i < keyNames.length; ++i) {
14 String name = keyNames[i];
15 String time = keyTimes[i];
16 // Convert the time string to total minutes for easier comparison later
17 int totalMinutes
18 = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3));
19 // If the name is not in the map, put it with a new ArrayList; add the time otherwise
20 nameToTimesMap.computeIfAbsent(name, k -> new ArrayList<>()).add(totalMinutes);
21 }
22
23 // List to hold the names of individuals who should receive an alert
24 List<String> alerts = new ArrayList<>();
25
26 // Iterate through the map entries
27 for (Map.Entry<String, List<Integer>> entry : nameToTimesMap.entrySet()) {
28 List<Integer> times = entry.getValue();
29 int n = times.size();
30 // We only care about individuals with more than 2 time logs
31 if (n > 2) {
32 // Sort the times to check the sequence
33 Collections.sort(times);
34 // Go through the times to find a sequence of 3 within 60 minutes
35 for (int i = 0; i < n - 2; ++i) {
36 if (times.get(i + 2) - times.get(i) <= 60) {
37 // If such a sequence is found, add the name to the alerts list and break
38 alerts.add(entry.getKey());
39 break;
40 }
41 }
42 }
43 }
44
45 // Sort the names alphabetically before returning
46 Collections.sort(alerts);
47 return alerts;
48 }
49}
50
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5
6class Solution {
7public:
8 vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
9 // Map to store user names and their swipe times in minutes
10 unordered_map<string, vector<int>> nameTimeMap;
11
12 // Convert times into minutes and store them in the map
13 for (size_t i = 0; i < keyName.size(); ++i) {
14 string name = keyName[i];
15 string time = keyTime[i];
16 int hours, minutes;
17 // Parse the time string to extract hours and minutes
18 sscanf(time.c_str(), "%d:%d", &hours, &minutes);
19 // Calculate total time in minutes
20 int totalMinutes = hours * 60 + minutes;
21 // Add the total time to the corresponding name in the map
22 nameTimeMap[name].emplace_back(totalMinutes);
23 }
24
25 // List to hold the names of users who trigger the alert condition
26 vector<string> alertNamesList;
27
28 // Iterate over each entry in the name time map
29 for (auto& [name, timeStamps] : nameTimeMap) {
30 // Sort the timestamps for each user
31 sort(timeStamps.begin(), timeStamps.end());
32 // Check if the user has at least three timestamps
33 if (timeStamps.size() > 2) {
34 // Iterate through the timestamps
35 for (size_t i = 0; i < timeStamps.size() - 2; ++i) {
36 // Check if three consecutive swipes are within 60 minutes
37 if (timeStamps[i + 2] - timeStamps[i] <= 60) {
38 // Add the name to the alert list and break the loop
39 alertNamesList.emplace_back(name);
40 break;
41 }
42 }
43 }
44 }
45
46 // Sort the list of names that trigger the alert condition
47 sort(alertNamesList.begin(), alertNamesList.end());
48
49 // Return the final list of alert names
50 return alertNamesList;
51 }
52};
53
1// Represents a map from user names to an array of their swipe times in minutes
2const nameTimeMap: { [name: string]: number[] } = {};
3
4/**
5 * Converts a time string to minutes.
6 * @param time - A string representing the time in HH:MM format.
7 * @returns The number of minutes since midnight.
8 */
9function convertTimeToMinutes(time: string): number {
10 const [hours, minutes] = time.split(':').map(Number);
11 return hours * 60 + minutes;
12}
13
14/**
15 * Checks if the alert condition is met for a user.
16 * @param timeStamps - An array of swipe times in minutes for a user.
17 * @returns A boolean indicating if the alert condition is met.
18 */
19function checkAlertCondition(timeStamps: number[]): boolean {
20 for (let i = 0; i < timeStamps.length - 2; i++) {
21 if (timeStamps[i + 2] - timeStamps[i] <= 60) {
22 return true;
23 }
24 }
25 return false;
26}
27
28/**
29 * Adds swipe times to the name-time mapping.
30 * @param keyName - An array of key names.
31 * @param keyTime - An array of corresponding key times.
32 */
33function processSwipeTimes(keyName: string[], keyTime: string[]): void {
34 for (let i = 0; i < keyName.length; ++i) {
35 const name = keyName[i];
36 const time = keyTime[i];
37 const totalMinutes = convertTimeToMinutes(time);
38 if (!nameTimeMap[name]) {
39 nameTimeMap[name] = [];
40 }
41 nameTimeMap[name].push(totalMinutes);
42 }
43}
44
45/**
46 * Generates a list of names who triggered the alert condition.
47 * @param keyName - An array of key names.
48 * @param keyTime - An array of corresponding key times.
49 * @returns An array of names for those who have triggered the alert.
50 */
51function alertNames(keyName: string[], keyTime: string[]): string[] {
52 processSwipeTimes(keyName, keyTime);
53
54 const alertNamesList: string[] = [];
55
56 // Iterate over each entry in the name-time map
57 for (const name in nameTimeMap) {
58 // Sort the timestamps for each user
59 nameTimeMap[name].sort((a, b) => a - b);
60 // Check if the alert condition is met for the user
61 if (checkAlertCondition(nameTimeMap[name])) {
62 alertNamesList.push(name);
63 }
64 }
65
66 // Sort the list of names that triggered the alert condition
67 alertNamesList.sort();
68
69 return alertNamesList;
70}
71
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be analyzed in the following steps:
-
Zipping and transforming times: The
zip(keyName, keyTime)
operation goes through all the keys and times once, which isO(N)
whereN
is the number of entries in thekeyName
andkeyTime
lists. -
Time conversion: The conversion of times from strings to minutes is done for each element once and takes constant time, so for N elements, this is also
O(N)
. -
Sorting the times: The
sort()
operation on the list of times within the dictionaryd
can vary in its time complexity depending on the number of time stamps per name, which is less than or equal toN
. In the worst case, if every name hasN
timestamps associated with it and we assumeM
to represent the number of unique names, then the sorting can takeO(N log N)
. However, since every timestamp can only belong to one name, and assumingK
average number of timestamps per name, sorting would beO(K log K)
for each name andO(M * K log K)
in total. -
Checking for 60-minute frames: The for loop runs a maximum of
K - 2
times per name, which isO(K)
, regarding the inner operation as constant time. Multiplying by the number of unique namesM
, this gives usO(M * K)
for all names. -
Sorting the answer: Finally, sorting the list of names
ans
, which has at mostM
elements, will takeO(M log M)
.
Combining these steps, the dominating factor in time complexity is the sorting of timestamps, because K
could be much larger than log K
. Therefore, if every person has many timestamps, the time complexity approaches O(N log N)
. Otherwise, it is more appropriately represented as O(M * K log K + M log M)
.
Space Complexity
The space complexity can be analyzed as follows:
-
Storing timestamps: The dictionary
d
can have at mostM
unique names withN
total timestamps, so in the worst case, space complexity ford
isO(N)
. -
Answer List: The
ans
list will contain at mostM
elements (as it only stores names), so the space needed isO(M)
.
Hence, the total space complexity for the algorithm is O(N)
because the space needed for the dictionary will be larger than or equal to the space for the list with all unique names.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.