Alert Using Same Key-Card Three or More Times in a One Hour Period
Alert Using Same Key-Card Three or More Times in a One Hour Period is a medium arrays & hashing problem solved with the sliding window · fixed pattern.
The best approach, optimal (sort per person + window of three), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (count the hour after every swipe) up.
Problem
An office logs every key-card swipe. keyName[i] is the person who swiped and keyTime[i] is the moment of the swipe in 24-hour "HH:MM" format. All swipes happened on the same day.
The security system raises an alert for a person who used their card three or more times within any one-hour period. A period counts as one hour when the last swipe is at most 60 minutes after the first one (for example "10:00", "10:30" and "11:00" trigger an alert, but "22:51", "23:20" and "23:52" do not).
Return the names of all alerted people, each listed once, sorted in alphabetical order.
Examples
Example 1
- Input
keyName = ["maya", "maya", "maya", "omar", "omar"], keyTime = ["09:15", "09:50", "10:15", "11:00", "11:20"]- Output
["maya"]- Why
- Maya swiped at 09:15, 09:50 and 10:15, all inside one 60-minute window. Omar swiped only twice.
Example 2
- Input
keyName = ["lee", "lee", "lee", "lee"], keyTime = ["08:00", "08:40", "09:01", "09:30"]- Output
["lee"]- Why
- 08:00 to 09:01 spans 61 minutes, but 08:40, 09:01 and 09:30 fit within 50 minutes.
Example 3
- Input
keyName = ["zed", "amy", "zed", "zed", "amy"], keyTime = ["23:00", "01:00", "00:30", "12:00", "01:10"]- Output
[]- Why
- Times do not wrap around midnight, so 23:00 and 00:30 are far apart; nobody has three swipes in one hour.
Constraints
1 <= keyName.length == keyTime.length <= 10^51 <= keyName[i].length <= 10andkeyName[i]contains only lowercase letters.keyTime[i]has the form"HH:MM"with00 <= HH <= 23and00 <= MM <= 59.- Each pair
[keyName[i], keyTime[i]]is unique. - All times are within the same single day.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (count the hour after every swipe) | O(n² + N log N) | O(n) |
| Optimal (sort per person + window of three) | O(n log n) | O(n) |
1Brute force (count the hour after every swipe)
O(n² + N log N)A person with k swipes costs k² comparisons, which is n² in the worst case; sorting the N alerted names adds N log N.O(n)The map stores every swipe once.Group the times by name. For each swipe of a person, count how many of that person's swipes fall in the 60 minutes starting at it, by scanning all of their swipes. If any count reaches three, the person is alerted.
- Map each name to a list of times in minutes.
- For each name and each of its times
t, count the timesuwitht <= u <= t + 60. - If any count is at least 3, add the name to the answer.
- Sort the answer alphabetically.
class Solution {
public List<String> alertNames(String[] keyName, String[] keyTime) {
Map<String, List<Integer>> byName = new HashMap<>();
for (int i = 0; i < keyName.length; i++) {
String t = keyTime[i];
int mins = Integer.parseInt(t.substring(0, 2)) * 60 + Integer.parseInt(t.substring(3));
byName.computeIfAbsent(keyName[i], k -> new ArrayList<>()).add(mins);
}
List<String> ans = new ArrayList<>();
for (Map.Entry<String, List<Integer>> e : byName.entrySet()) {
List<Integer> times = e.getValue();
boolean alert = false;
for (int t : times) {
int cnt = 0;
for (int u : times) {
if (u >= t && u <= t + 60) cnt++;
}
if (cnt >= 3) {
alert = true;
break;
}
}
if (alert) ans.add(e.getKey());
}
Collections.sort(ans);
return ans;
}
}class Solution:
def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
by_name = {}
for name, t in zip(keyName, keyTime):
mins = int(t[:2]) * 60 + int(t[3:])
by_name.setdefault(name, []).append(mins)
ans = []
for name, times in by_name.items():
alert = False
for t in times:
cnt = 0
for u in times:
if t <= u <= t + 60:
cnt += 1
if cnt >= 3:
alert = True
break
if alert:
ans.append(name)
ans.sort()
return ansclass Solution {
public:
vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
unordered_map<string, vector<int>> byName;
for (size_t i = 0; i < keyName.size(); i++) {
const string& t = keyTime[i];
int mins = stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3));
byName[keyName[i]].push_back(mins);
}
vector<string> ans;
for (auto& [name, times] : byName) {
bool alert = false;
for (int t : times) {
int cnt = 0;
for (int u : times) {
if (u >= t && u <= t + 60) cnt++;
}
if (cnt >= 3) {
alert = true;
break;
}
}
if (alert) ans.push_back(name);
}
sort(ans.begin(), ans.end());
return ans;
}
};function alertNames(keyName, keyTime) {
const byName = new Map();
for (let i = 0; i < keyName.length; i++) {
const t = keyTime[i];
const mins = parseInt(t.slice(0, 2), 10) * 60 + parseInt(t.slice(3), 10);
if (!byName.has(keyName[i])) byName.set(keyName[i], []);
byName.get(keyName[i]).push(mins);
}
const ans = [];
for (const [name, times] of byName) {
let alert = false;
for (const t of times) {
let cnt = 0;
for (const u of times) {
if (u >= t && u <= t + 60) cnt++;
}
if (cnt >= 3) {
alert = true;
break;
}
}
if (alert) ans.push(name);
}
ans.sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
return ans;
}2Optimal (sort per person + window of three)
O(n log n)Sorting all per-person lists costs O(n log n) in total, and the window check is linear.O(n)The map stores every swipe once.Sort each person's swipe times. If any three swipes fit in one hour, the tightest three are consecutive in sorted order, so it is enough to slide a window of size three and test times[i + 2] - times[i] <= 60.
- Map each name to its list of times in minutes.
- Sort each list; for
ifrom 0 tosize - 3, iftimes[i + 2] - times[i] <= 60, mark the name and stop. - Sort the marked names alphabetically and return them.
class Solution {
public List<String> alertNames(String[] keyName, String[] keyTime) {
Map<String, List<Integer>> byName = new HashMap<>();
for (int i = 0; i < keyName.length; i++) {
String t = keyTime[i];
int mins = (t.charAt(0) - '0') * 600 + (t.charAt(1) - '0') * 60
+ (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
byName.computeIfAbsent(keyName[i], k -> new ArrayList<>()).add(mins);
}
List<String> ans = new ArrayList<>();
for (Map.Entry<String, List<Integer>> e : byName.entrySet()) {
List<Integer> times = e.getValue();
Collections.sort(times);
for (int i = 0; i + 2 < times.size(); i++) {
if (times.get(i + 2) - times.get(i) <= 60) {
ans.add(e.getKey());
break;
}
}
}
Collections.sort(ans);
return ans;
}
}class Solution:
def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
by_name = {}
for name, t in zip(keyName, keyTime):
mins = int(t[:2]) * 60 + int(t[3:])
by_name.setdefault(name, []).append(mins)
ans = []
for name, times in by_name.items():
times.sort()
for i in range(len(times) - 2):
if times[i + 2] - times[i] <= 60:
ans.append(name)
break
ans.sort()
return ansclass Solution {
public:
vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
unordered_map<string, vector<int>> byName;
for (size_t i = 0; i < keyName.size(); i++) {
const string& t = keyTime[i];
int mins = (t[0] - '0') * 600 + (t[1] - '0') * 60 + (t[3] - '0') * 10 + (t[4] - '0');
byName[keyName[i]].push_back(mins);
}
vector<string> ans;
for (auto& [name, times] : byName) {
sort(times.begin(), times.end());
for (size_t i = 0; i + 2 < times.size(); i++) {
if (times[i + 2] - times[i] <= 60) {
ans.push_back(name);
break;
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
};function alertNames(keyName, keyTime) {
const byName = new Map();
for (let i = 0; i < keyName.length; i++) {
const t = keyTime[i];
const mins = parseInt(t.slice(0, 2), 10) * 60 + parseInt(t.slice(3), 10);
if (!byName.has(keyName[i])) byName.set(keyName[i], []);
byName.get(keyName[i]).push(mins);
}
const ans = [];
for (const [name, times] of byName) {
times.sort((a, b) => a - b);
for (let i = 0; i + 2 < times.length; i++) {
if (times[i + 2] - times[i] <= 60) {
ans.push(name);
break;
}
}
}
ans.sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
return ans;
}Edge cases to test
- Three swipes exactly 60 minutes apart end to end (for example 10:00, 10:30, 11:00): they count, the window is inclusive
- A gap of 61 minutes between the first and third swipe: no alert for that triple
- The input is not sorted by time, or the swipes of one person are interleaved with others
- Times near midnight such as 23:50 and 00:10 are about 23 hours apart, not 20 minutes
- The answer must be sorted alphabetically and list each name once
Hints
Hint 1
Group the swipe times by name and convert "HH:MM" to minutes since midnight.
Hint 2
Once one person's times are sorted, three swipes within an hour exist exactly when some three consecutive times fit in 60 minutes.
Hint 3
Check times[i + 2] - times[i] <= 60 for every i. Collect the alerted names and sort them.
FAQ
What is the best time complexity for Alert Using Same Key-Card Three or More Times in a One Hour Period?
Optimal (sort per person + window of three) runs in O(n log n) time and O(n) extra space. Sorting all per-person lists costs O(n log n) in total, and the window check is linear.
Which pattern does Alert Using Same Key-Card Three or More Times in a One Hour Period use?
It is a arrays & hashing problem that uses the sliding window · fixed pattern. Other problems with the same pattern: Maximum Average Subarray I, K Radius Subarray Averages, Maximum Number of Vowels in a Substring of Given Length.
Is there a brute force solution for Alert Using Same Key-Card Three or More Times in a One Hour Period?
Yes. Brute force (count the hour after every swipe) takes O(n² + N log N) time and O(n) space. Group the times by name.
Which edge cases should I test for Alert Using Same Key-Card Three or More Times in a One Hour Period?
Three swipes exactly 60 minutes apart end to end (for example 10:00, 10:30, 11:00): they count, the window is inclusive; A gap of 61 minutes between the first and third swipe: no alert for that triple; The input is not sorted by time, or the swipes of one person are interleaved with others; Times near midnight such as 23:50 and 00:10 are about 23 hours apart, not 20 minutes; The answer must be sorted alphabetically and list each name once.