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

Medium Arrays & Hashing Sliding Window · Fixed Original on LeetCode

Reported atStripe

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^5
  • 1 <= keyName[i].length <= 10 and keyName[i] contains only lowercase letters.
  • keyTime[i] has the form "HH:MM" with 00 <= HH <= 23 and 00 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(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.
SpaceO(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.

  1. Map each name to a list of times in minutes.
  2. For each name and each of its times t, count the times u with t <= u <= t + 60.
  3. If any count is at least 3, add the name to the answer.
  4. 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;
    }
}

2Optimal (sort per person + window of three)

TimeO(n log n)Sorting all per-person lists costs O(n log n) in total, and the window check is linear.
SpaceO(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.

  1. Map each name to its list of times in minutes.
  2. Sort each list; for i from 0 to size - 3, if times[i + 2] - times[i] <= 60, mark the name and stop.
  3. 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;
    }
}

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.