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

Problem

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.

Examples

Example 1:

1
2
3


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:

1
2
3


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 <= 105
keyName.length == keyTime.length
keyTime[i] is in the format " HH:MM".
[keyName[i], keyTime[i]] is unique.
1 <= keyName[i].length <= 10
keyName[i] contains only lowercase English letters.

Solution

Method 1 – Sorting and Sliding Window

Intuition

If we sort each person’s keycard usage times, we can efficiently check for any three usages within a one-hour window by sliding through their sorted times. If such a window exists, that person should be alerted.

Approach

Group by Name: Build a mapping from each name to a list of their keycard usage times.
Convert Times: Convert each time from “HH:MM” format to minutes since midnight for easy comparison.
Sort Times: For each person, sort their list of times.
Sliding Window: For each person, check every window of three consecutive times. If the difference between the first and third time in the window is 60 minutes or less, add the name to the answer.
Sort Result: Return the list of alerted names in alphabetical order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
public:
   vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
      unordered_map<string, vector<int>> mp;
      int n = keyName.size();
      for (int i = 0; i < n; ++i) {
        string name = keyName[i];
        string t = keyTime[i];
        int mins = stoi(t.substr(0,2)) * 60 + stoi(t.substr(3,2));
        mp[name].push_back(mins);
      }
      vector<string> ans;
      for (auto& [name, times] : mp) {
        sort(times.begin(), times.end());
        for (int i = 2; i < times.size(); ++i) {
           if (times[i] - times[i-2] <= 60) {
              ans.push_back(name);
              break;
           }
        }
      }
      sort(ans.begin(), ans.end());
      return ans;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
   public List<String> alertNames(String[] keyName, String[] keyTime) {
      Map<String, List<Integer>> mp = new HashMap<>();
      int n = keyName.length;
      for (int i = 0; i < n; ++i) {
        String name = keyName[i];
        String t = keyTime[i];
        int mins = Integer.parseInt(t.substring(0,2)) * 60 + Integer.parseInt(t.substring(3,5));
        mp.computeIfAbsent(name, k -> new ArrayList<>()).add(mins);
      }
      List<String> ans = new ArrayList<>();
      for (String name : mp.keySet()) {
        List<Integer> times = mp.get(name);
        Collections.sort(times);
        for (int i = 2; i < times.size(); ++i) {
           if (times.get(i) - times.get(i-2) <= 60) {
              ans.add(name);
              break;
           }
        }
      }
      Collections.sort(ans);
      return ans;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
   def alertNames(self, keyName: list[str], keyTime: list[str]) -> list[str]:
      mp: dict[str, list[int]] = {}
      for name, t in zip(keyName, keyTime):
        mins = int(t[:2]) * 60 + int(t[3:])
        if name not in mp:
           mp[name] = []
        mp[name].append(mins)
      ans: list[str] = []
      for name, times in mp.items():
        times.sort()
        for i in range(2, len(times)):
           if times[i] - times[i-2] <= 60:
              ans.append(name)
              break
      ans.sort()
      return ans

Complexity

⏰ Time complexity: O(N log N)
- Grouping and converting times: O(N)
- Sorting times for each user: O(N log N) in total
- Sliding window check: O(N)
- Sorting answer: O(K log K), K = number of unique names
🧺 Space complexity: O(N)
- For storing all times per user and the answer list.

Problem#

Examples#

Solution#

Method 1 – Sorting and Sliding Window#

Intuition#

Approach#

Code#

Complexity#