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 - 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.

Note: "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.

Input & Output

Example 1 — Mixed Violations

$ 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"]

💡 Note: daniel used keycard at 10:00, 10:40, 11:00 - the span is exactly 60 minutes (11:00 - 10:00), which triggers an alert. luis has times spread across 6 hours, no 3 accesses within 60 minutes.

Example 2 — No Violations

$ 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: []

💡 Note: alice's first 3 times: 12:00, 12:01, 18:00 span 6 hours. bob's tightest 3 times: 21:00, 21:20, 21:30 span only 30 minutes but that's within limit. No violations.

Example 3 — Multiple Violations

$ Input: keyName = ["john","john","john","john","mary","mary","mary"], keyTime = ["23:58","23:59","00:01","00:02","20:00","20:30","20:59"]

› Output: ["john","mary"]

💡 Note: john: times 23:58, 23:59, 00:01 span from 1438 to 1441 minutes (3 minutes apart). mary: 20:00, 20:30, 20:59 span 59 minutes. Both violate the rule.

Constraints

1 ≤ keyName.length, keyTime.length ≤ 10⁵
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

Visualization

Tap to expand

Understanding the Visualization

Input

Employee names and access times throughout the day

Group & Sort

Organize times by employee and sort chronologically

Detect Violations

Find employees with 3+ accesses in any 60-minute window

Key Takeaway

🎯 Key Insight: Sort each employee's times, then sliding window efficiently detects 3+ accesses within 60 minutes

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to group access times by employee, then use sliding window on sorted times to efficiently detect violations. Best approach is Sort + Sliding Window: Time: O(n × k log k), Space: O(n × k) where n is number of employees and k is average accesses per employee.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Combinations	O(n × k³)	O(n)	For each employee, check all possible 3-card combinations to see if any fit within 60 minutes
Sort + Sliding Window	O(n × k log k)	O(n × k)	Sort each employee's access times, then use sliding window to efficiently find 3+ accesses within 60 minutes

Brute Force - Check All Combinations — Algorithm Steps

Group keycard accesses by employee name
For each employee with 3+ accesses, check all combinations of 3 times
Convert time strings to minutes and check if max - min ≤ 60
Add employee to result if any combination violates the rule

Visualization

Tap to expand

Step-by-Step Walkthrough

Group by Employee

Organize access times by worker name

Check Combinations

For each employee, test all 3-time combinations

Find Violations

Mark employees with any combination ≤ 60 minutes apart

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAMES 1000
#define MAX_NAME_LEN 50
#define MAX_TIMES 100

int timeToMinutes(char* time) {
    int hours, minutes;
    sscanf(time, "%d:%d", &hours, &minutes);
    return hours * 60 + minutes;
}

int compare(const void* a, const void* b) {
    return strcmp((char*)a, (char*)b);
}

int compareInts(const void* a, const void* b) {
    return (*(int*)a) - (*(int*)b);
}

char** solution(char** keyName, char** keyTime, int keyNameSize, int* returnSize) {
    char names[MAX_NAMES][MAX_NAME_LEN];
    int times[MAX_NAMES][MAX_TIMES];
    int counts[MAX_NAMES];
    int numEmployees = 0;
    
    // Group times by employee
    for (int i = 0; i < keyNameSize; i++) {
        int found = -1;
        for (int j = 0; j < numEmployees; j++) {
            if (strcmp(names[j], keyName[i]) == 0) {
                found = j;
                break;
            }
        }
        
        if (found == -1) {
            strcpy(names[numEmployees], keyName[i]);
            times[numEmployees][0] = timeToMinutes(keyTime[i]);
            counts[numEmployees] = 1;
            numEmployees++;
        } else {
            times[found][counts[found]] = timeToMinutes(keyTime[i]);
            counts[found]++;
        }
    }
    
    char** result = malloc(MAX_NAMES * sizeof(char*));
    int resultCount = 0;
    
    // Check each employee
    for (int emp = 0; emp < numEmployees; emp++) {
        if (counts[emp] < 3) continue;
        
        // Check all combinations of 3 times
        int foundViolation = 0;
        for (int i = 0; i < counts[emp] && !foundViolation; i++) {
            for (int j = i + 1; j < counts[emp] && !foundViolation; j++) {
                for (int k = j + 1; k < counts[emp]; k++) {
                    int threeTimes[3] = {times[emp][i], times[emp][j], times[emp][k]};
                    qsort(threeTimes, 3, sizeof(int), compareInts);
                    if (threeTimes[2] - threeTimes[0] <= 60) {
                        foundViolation = 1;
                        break;
                    }
                }
            }
        }
        
        if (foundViolation) {
            result[resultCount] = malloc((strlen(names[emp]) + 1) * sizeof(char));
            strcpy(result[resultCount], names[emp]);
            resultCount++;
        }
    }
    
    // Sort result
    qsort(result, resultCount, sizeof(char*), compare);
    
    *returnSize = resultCount;
    return result;
}

int main() {
    // Simple parsing for demonstration
    char** keyName = malloc(MAX_NAMES * sizeof(char*));
    char** keyTime = malloc(MAX_NAMES * sizeof(char*));
    int size = 0;
    
    // Read input (simplified)
    char line[1000];
    fgets(line, sizeof(line), stdin);
    // Parse keyName array - implementation would parse JSON format
    
    fgets(line, sizeof(line), stdin);
    // Parse keyTime array - implementation would parse JSON format
    
    int returnSize;
    char** result = solution(keyName, keyTime, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k³)

For each of n employees, we check C(k,3) combinations where k is number of accesses per employee

✓ Linear Growth

Space Complexity

O(n)

Hash map to group accesses by employee name

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler