Problem Description

You are given two string arrays, keyName and keyTime, where keyName[i] represents the name of the employee who used their key card at time keyTime[i]. The keyTime[i] is a string in the format "HH:MM" (24-hour clock).

A key card alert is triggered for an employee if they use their key card three or more times in any one-hour period (inclusive). That is, if any three or more uses fall within a 60-minute window, the employee should be added to the alert list.

Return a list of employee names who triggered the alert, sorted in lexicographical order. Each name should appear only once in the output, and you must not reuse or ignore key card usages.

• Each keyName[i] is a string of uppercase and lowercase English letters.
• keyTime[i] is always valid and in "HH:MM" format.
• There is one valid solution per input.
• You must not reuse or ignore any key card usage.

Thought Process

To solve this problem, we need to identify, for each employee, if there exists any group of three or more key card usages that all fall within a single 60-minute window. The brute-force way would be to check all possible triplets for each person, but that's inefficient.

Instead, we can optimize by grouping all times for each employee, sorting them, and then using a sliding window to check for any three usages within an hour. This approach is similar to checking for a sequence of events within a rolling time frame, which is a common pattern in log analysis.

We use a hash map (dictionary) to group times by employee, sort each list, and then scan with a window of size 3 to see if the time difference between the first and third usage is at most 60 minutes.

Solution Approach

• Step 1: Create a mapping from each employee's name to a list of their key card usage times (converted to minutes past midnight for easy comparison).
• Step 2: For each employee, sort their list of usage times in ascending order.
• Step 3: For each sorted list, use a sliding window of size 3: for each index i, compare the time at i+2 to the time at i. If the difference is 60 minutes or less, the employee is flagged for alert.
• Step 4: Collect all such employee names, remove duplicates, and return the result sorted lexicographically.

We use a hash map for grouping because it allows O(1) lookups and appends. Sorting is required to easily check consecutive usages. The sliding window ensures we only check minimal necessary combinations.

Example Walkthrough

Input:
keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"]
keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]

1. Group times by employee:
   • daniel: ["10:00", "10:40", "11:00"]
   • luis: ["09:00", "11:00", "13:00", "15:00"]
2. Convert to minutes:
   • daniel: [600, 640, 660]
   • luis: [540, 660, 780, 900]
3. Sort (already sorted in this example).
4. For daniel:
   - 660 (third usage) - 600 (first usage) = 60 minutes.
   - Since 3 usages in 60 minutes, daniel is alerted.
5. For luis:
   - 780 - 540 = 240 (not within 60 minutes).
   - Check next window: 900 - 660 = 240.
   - No group of 3 within 1 hour. luis is not alerted.
6. Output: ["daniel"]

Time and Space Complexity

• Brute-force: For each employee with n usages, check all triplets: O(n³) per employee. Too slow for large data.
• Optimized:
  • Grouping usages: O(N), where N is total number of records.
  • Sorting each employee's times: O(K log K) per employee, where K is their usage count.
  • Sliding window: O(K) per employee.
  • Total: O(N log K) where K is the maximum number of usages by any employee.
  • Space: O(N) for storing all usage times.

The optimization is possible because sorting and sliding window reduce redundant checks and exploit the structure of the problem.

Summary

The solution groups key card usages by employee, sorts the times, and uses a sliding window to efficiently check for three or more usages within any one-hour period. By leveraging hash maps and sorted lists, we avoid brute-force checks and achieve an elegant, efficient solution. This approach is a practical application of grouping, sorting, and the sliding window pattern, which is valuable in many real-world logging and alert scenarios.

Code Implementation

from collections import defaultdict

def alertNames(keyName, keyTime):
    def to_minutes(t):
        h, m = map(int, t.split(':'))
        return h * 60 + m

    times = defaultdict(list)
    for name, t in zip(keyName, keyTime):
        times[name].append(to_minutes(t))
    
    res = []
    for name in times:
        tlist = sorted(times[name])
        for i in range(len(tlist) - 2):
            if tlist[i+2] - tlist[i] <= 60:
                res.append(name)
                break
    return sorted(res)
      

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

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

import java.util.*;

class Solution {
    public List<String> alertNames(String[] keyName, String[] keyTime) {
        Map<String, List<Integer>> times = new HashMap<>();
        for (int i = 0; i < keyName.length; ++i) {
            String name = keyName[i];
            String[] parts = keyTime[i].split(":");
            int minutes = Integer.parseInt(parts[0]) * 60 + Integer.parseInt(parts[1]);
            times.computeIfAbsent(name, k -> new ArrayList<>()).add(minutes);
        }
        List<String> res = new ArrayList<>();
        for (String name : times.keySet()) {
            List<Integer> tlist = times.get(name);
            Collections.sort(tlist);
            for (int i = 0; i + 2 < tlist.size(); ++i) {
                if (tlist.get(i+2) - tlist.get(i) <= 60) {
                    res.add(name);
                    break;
                }
            }
        }
        Collections.sort(res);
        return res;
    }
}
      

var alertNames = function(keyName, keyTime) {
    const toMinutes = t => {
        const [h, m] = t.split(':').map(Number);
        return h * 60 + m;
    };
    const times = {};
    for (let i = 0; i < keyName.length; ++i) {
        if (!times[keyName[i]]) times[keyName[i]] = [];
        times[keyName[i]].push(toMinutes(keyTime[i]));
    }
    const res = [];
    for (const name in times) {
        const tlist = times[name].sort((a, b) => a - b);
        for (let i = 0; i + 2 < tlist.length; ++i) {
            if (tlist[i+2] - tlist[i] <= 60) {
                res.push(name);
                break;
            }
        }
    }
    return res.sort();
};