Alert Using Same Key-Card Three or More Times in a One Hour Period
MedPrompt
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 <= 105keyName.length == keyTime.lengthkeyTime[i]is in the format "HH:MM".[keyName[i], keyTime[i]]is unique.1 <= keyName[i].length <= 10keyName[i] contains only lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves grouping the key-card access times by worker and then, for each worker, checking every possible combination of three access times to see if they fall within a one-hour period. This is a straightforward but highly inefficient method.
Algorithm
-
- Create a
HashMap<String, List<Integer>>to store access times for each worker. Convert time strings to minutes from midnight.
- Create a
-
- Iterate through the input
keyNameandkeyTimearrays, populating the map.
- Iterate through the input
-
- Create a
HashSet<String>to store the names of workers who trigger an alert.
- Create a
-
- For each worker in the map:
- a. If they have fewer than 3 access times, continue to the next worker.
- b. Use three nested loops to select every combination of three access times.
- c. For each combination, find the minimum and maximum time.
- d. If
max_time - min_time <= 60, add the worker's name to theHashSetand break the loops for this worker.
-
- Convert the
HashSetto aList.
- Convert the
-
- Sort the list alphabetically and return it.
Walkthrough
First, we process the input arrays to group all access times for each worker. A HashMap is used, where keys are worker names and values are lists of their access times. To facilitate comparisons, time strings like "HH:MM" are converted into an integer representation, such as the total number of minutes from midnight.
After grouping, we iterate through each worker in the map. If a worker has fewer than three access records, they are skipped. Otherwise, we use three nested loops to iterate through all unique combinations of three access times from their list.
For each combination of three times, we calculate the difference between the maximum and minimum time in that triplet. If this difference is less than or equal to 60 minutes, it signifies that three uses occurred within a one-hour period. The worker's name is then added to a HashSet to ensure uniqueness and to mark them for an alert. We can then stop checking for this worker and move to the next.
Finally, the names from the HashSet are transferred to a list, which is sorted alphabetically before being returned.
import java.util.*; class Solution { public List<String> alertNames(String[] keyName, String[] keyTime) { Map<String, List<Integer>> map = new HashMap<>(); for (int i = 0; i < keyName.length; i++) { String name = keyName[i]; String timeStr = keyTime[i]; int time = Integer.parseInt(timeStr.substring(0, 2)) * 60 + Integer.parseInt(timeStr.substring(3, 5)); map.computeIfAbsent(name, k -> new ArrayList<>()).add(time); } Set<String> alertSet = new HashSet<>(); for (Map.Entry<String, List<Integer>> entry : map.entrySet()) { String name = entry.getKey(); List<Integer> times = entry.getValue(); if (times.size() < 3) { continue; } // This is the inefficient part for (int i = 0; i < times.size(); i++) { for (int j = i + 1; j < times.size(); j++) { for (int k = j + 1; k < times.size(); k++) { int t1 = times.get(i); int t2 = times.get(j); int t3 = times.get(k); int minTime = Math.min(t1, Math.min(t2, t3)); int maxTime = Math.max(t1, Math.max(t2, t3)); if (maxTime - minTime <= 60) { alertSet.add(name); // Break all loops for this user i = times.size(); j = times.size(); k = times.size(); } } } } } List<String> result = new ArrayList<>(alertSet); Collections.sort(result); return result; }}Complexity
Time
O(N^3) in the worst case, where N is the total number of key-card entries. If one worker has N entries, checking all triplets of times takes O(N^3) time. This will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
Space
O(N), where N is the total number of entries. This space is used to store the map of names to their access times.
Trade-offs
Pros
Conceptually simple and easy to understand.
Cons
Extremely inefficient due to the cubic time complexity, making it infeasible for large inputs.
Solutions
Solution
class Solution {public List<String> alertNames(String[] keyName, String[] keyTime) { Map<String, List<Integer>> d = new HashMap<>(); for (int i = 0; i < keyName.length; ++i) { String name = keyName[i]; String time = keyTime[i]; int t = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3)); d.computeIfAbsent(name, k->new ArrayList<>()).add(t); } List<String> ans = new ArrayList<>(); for (var e : d.entrySet()) { var ts = e.getValue(); int n = ts.size(); if (n > 2) { Collections.sort(ts); for (int i = 0; i < n - 2; ++i) { if (ts.get(i + 2) - ts.get(i) <= 60) { ans.add(e.getKey()); break; } } } } Collections.sort(ans); return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.