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

MediumArrayHash TableStringSorting
Leetcode Link

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:

  1. Parse each time entry in keyTime from "HH:MM" format to minutes only. This makes it easier to calculate the difference between times.
  2. 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.
  3. 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.
  4. 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.

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:

  1. The defaultdict from Python's collections 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.

  2. The solution iterates through the combined keyName and keyTime lists using zip, which allows us to process the corresponding elements of these two lists in pairs.

  3. 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 and t[3:] extracts the minutes component from the string, which are then converted to an integer total number of minutes.

  4. 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.

  5. 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.

  6. To check for a one-hour period alert, a window of three consecutive times ts[i], ts[i + 1], and ts[i + 2] is examined. If the difference between ts[i + 2] and ts[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.

  7. 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.

  8. 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.

💪
Level Up Your
Algo Skills

Example 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"]
  1. 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
  2. Group by worker names using defaultdict:

    1{"Alice": [600, 660, 720], "Bob": [620, 640]}
  3. 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.

  4. Sort the times for each worker. In this case, Alice's times are already in order.

  5. 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.

  6. 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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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:

  1. Zipping and transforming times: The zip(keyName, keyTime) operation goes through all the keys and times once, which is O(N) where N is the number of entries in the keyName and keyTime lists.

  2. 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).

  3. Sorting the times: The sort() operation on the list of times within the dictionary d can vary in its time complexity depending on the number of time stamps per name, which is less than or equal to N. In the worst case, if every name has N timestamps associated with it and we assume M to represent the number of unique names, then the sorting can take O(N log N). However, since every timestamp can only belong to one name, and assuming K average number of timestamps per name, sorting would be O(K log K) for each name and O(M * K log K) in total.

  4. Checking for 60-minute frames: The for loop runs a maximum of K - 2 times per name, which is O(K), regarding the inner operation as constant time. Multiplying by the number of unique names M, this gives us O(M * K) for all names.

  5. Sorting the answer: Finally, sorting the list of names ans, which has at most M elements, will take O(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:

  1. Storing timestamps: The dictionary d can have at most M unique names with N total timestamps, so in the worst case, space complexity for d is O(N).

  2. Answer List: The ans list will contain at most M elements (as it only stores names), so the space needed is O(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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫