# Alert Using Same Key-Card Three or More Times in a One Hour Period
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period)
Canonical: https://scaleengineer.com/dsa/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
**Companies:** [Karat](https://scaleengineer.com/companies/karat), [Wayfair](https://scaleengineer.com/companies/wayfair)
---
## 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.

**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 <= 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.`

# Approaches
## Brute-Force Approach
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.
**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.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient due to the cubic time complexity, making it infeasible for large inputs.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- 1. Create a `HashMap<String, List<Integer>>` to store access times for each worker. Convert time strings to minutes from midnight.
- 2. Iterate through the input `keyName` and `keyTime` arrays, populating the map.
- 3. Create a `HashSet<String>` to store the names of workers who trigger an alert.
- 4. 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 the `HashSet` and break the loops for this worker.
- 5. Convert the `HashSet` to a `List`.
- 6. Sort the list alphabetically and return it.

## Optimized Approach using Sorting and Sliding Window
This is an efficient approach that first groups access times by worker, then sorts these times. A sliding window is then used to check for three or more uses within a one-hour period. This avoids the costly triple nested loop of the brute-force method.
**Time:** O(N log N), where N is the total number of key-card entries. The breakdown is as follows: O(N) to populate the map. Then, for each user with `k` entries, we sort their times in O(k log k). The sum of `k log k` over all users is bounded by O(N log N). The final result collection in a `TreeSet` also contributes to this complexity but does not exceed it. · **Space:** O(N), where N is the total number of entries. This space is required to store the `HashMap` mapping names to their list of access times.
**Pros:** Highly efficient with a time complexity of O(N log N).; Scales well for large datasets, easily passing the given constraints.; The logic is clean and directly models the problem after sorting.
**Cons:** Requires extra space for the map, which can be up to O(N).; The sorting step for each user's times is the main performance bottleneck, though it's an efficient one.
### Explanation
The first step is to organize the data. We use a `HashMap` where keys are worker names and values are lists of their access times. As we populate this map, we convert the time strings ("HH:MM") into a numerical format, specifically the total minutes past midnight. This allows for easy arithmetic comparisons.

Once all times are grouped by worker, we iterate through each worker's list of times. For an alert to be possible, a worker must have at least three entries. The crucial optimization is to sort each worker's list of access times in ascending order.

With the times sorted, we can efficiently check for the alert condition. We iterate through the sorted list of times, starting from the third entry (index 2). For each time `t_i`, we look back two positions to `t_{i-2}`. If the difference `t_i - t_{i-2}` is less than or equal to 60, it means that the three times `t_{i-2}`, `t_{i-1}`, and `t_i` all occurred within a one-hour window. When this condition is met, we've found an alert for this worker. We add their name to a `TreeSet` and can immediately stop checking this worker and move to the next.

Finally, the `TreeSet` of alerted names is converted into a list and returned. The `TreeSet` ensures the names are unique and sorted alphabetically.

```java
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);
        }

        // Use a TreeSet to store names in sorted order and ensure uniqueness
        Set<String> alertNames = new TreeSet<>();
        for (Map.Entry<String, List<Integer>> entry : map.entrySet()) {
            String name = entry.getKey();
            List<Integer> times = entry.getValue();
            
            if (times.size() < 3) {
                continue;
            }
            
            Collections.sort(times);
            
            for (int i = 2; i < times.size(); i++) {
                if (times.get(i) - times.get(i - 2) <= 60) {
                    alertNames.add(name);
                    break; // Found an alert for this user, move to the next
                }
            }
        }

        return new ArrayList<>(alertNames);
    }
}
```
### Algorithm
- 1. Create a `HashMap<String, List<Integer>>` to map each worker to a list of their access times in minutes.
- 2. Iterate through the input arrays and populate the map. Convert time strings to minutes.
- 3. Create an empty `TreeSet<String>` to store the names of alerted workers, which will automatically handle uniqueness and sorting.
- 4. Iterate through each entry (worker and their times) in the map:
   - a. Get the list of access times for the current worker.
   - b. If the list size is less than 3, skip to the next worker.
   - c. Sort the list of times in ascending order.
   - d. Iterate through the sorted times from the third element (index 2) to the end.
   - e. For each time `times[i]`, check if `times[i] - times[i-2] <= 60`.
   - f. If the condition is true, add the worker's name to the `TreeSet` and break the inner loop to proceed to the next worker.
- 5. Convert the `TreeSet` to a `List` and return it.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> alertNames(vector<string> &keyName, vector<string> &keyTime) {
    unordered_map<string, vector<int>> d;
    for (int i = 0; i < keyName.size(); ++i) {
      auto name = keyName[i];
      auto time = keyTime[i];
      int a, b;
      sscanf(time.c_str(), "%d:%d", &a, &b);
      int t = a * 60 + b;
      d[name].emplace_back(t);
    }
    vector<string> ans;
    for (auto &[name, ts] : d) {
      int n = ts.size();
      if (n > 2) {
        sort(ts.begin(), ts.end());
        for (int i = 0; i < n - 2; ++i) {
          if (ts[i + 2] - ts[i] <= 60) {
            ans.emplace_back(name);
            break;
          }
        }
      }
    }
    sort(ans.begin(), ans.end());
    return ans;
  }
};

```

### Python

```python
class Solution:
    def alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]: d = defaultdict(list) for name, t in zip(keyName, keyTime): t = int(t[: 2]) * 60 + int(t[3:]) d[name]. append(t) ans = [] for name, ts in d . items(): if (n: = len(ts)) > 2: ts . sort() for i in range(n - 2): if ts[i + 2] - ts[i] <= 60: ans . append(name) break ans . sort() return ans

```