LeetCode 2933 - High-Access Employees
This problem provides a list of employee access records. Each record contains two pieces of information: - The employee's name. - A timestamp in 24-hour "HHMM" format. All timestamps belong to the same day, so there is no need to handle dates or day transitions.
Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Sorting
Solution
LeetCode 2933 - High-Access Employees
Problem Understanding
This problem provides a list of employee access records. Each record contains two pieces of information:
- The employee's name.
- A timestamp in 24-hour
"HHMM"format.
All timestamps belong to the same day, so there is no need to handle dates or day transitions.
An employee is considered high-access if they accessed the system at least three times within a period shorter than one hour. A key detail is that a difference of exactly 60 minutes does not qualify. The interval must be strictly less than 60 minutes.
For example:
08:15and09:14are 59 minutes apart, so they are within the same one-hour period.08:15and09:15are exactly 60 minutes apart, so they are not within the same one-hour period.
The input consists of up to 100 access records. Each employee may appear multiple times, and the records are not guaranteed to be sorted.
The goal is to return the names of all employees who have at least one set of three or more accesses occurring within a time window shorter than one hour.
The constraints are quite small. With at most 100 records total, even moderately inefficient solutions would work. However, there is a clean and efficient approach based on sorting each employee's access times and checking consecutive groups of three accesses.
Several edge cases are important:
- An employee may have fewer than three accesses, making them automatically ineligible.
- Multiple accesses may occur at the exact same time.
- Exactly 60 minutes apart does not count.
- Accesses near midnight should not wrap around to the next day because all records belong to the same day.
- Records are not sorted initially.
Approaches
Brute Force
A straightforward solution is to group access times by employee, convert them into minutes, and sort them.
For each employee, we could examine every possible subset of three access times and determine whether the earliest and latest access occur within less than 60 minutes.
This works because an employee is high-access if any three accesses satisfy the condition.
The problem with this approach is that it performs unnecessary checks. If an employee has many accesses, checking all triplets becomes cubic in the number of accesses for that employee.
Key Observation
After sorting an employee's access times, we only need to check consecutive groups of three accesses.
Suppose the sorted times are:
t0 < t1 < t2 < t3 < ...
If there exists any set of three accesses within less than 60 minutes, then there must exist some consecutive triple whose first and third elements differ by less than 60 minutes.
This follows because sorting places all accesses in chronological order. Any valid group of three accesses must contain three consecutive positions in the sorted sequence whose span is less than 60 minutes.
Therefore, after sorting, we can slide a window of size three and check:
times[i + 2] - times[i] < 60
If this condition is true for any position, the employee is high-access.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n³) per employee in the worst case | O(n) | Checks all possible triplets |
| Optimal | O(n log n) | O(n) | Sort times and check consecutive triples |
Here, n denotes the total number of access records.
Algorithm Walkthrough
Optimal Algorithm
- Create a hash map where each employee name maps to a list of access times.
- Convert every
"HHMM"timestamp into minutes since midnight. For example,"0549"becomes5 * 60 + 49 = 349. - Store each converted time in the corresponding employee's list.
- For every employee, sort their list of access times in ascending order.
- Scan the sorted list using a window of size three.
- For each position
i, compute the difference between:
- The first access in the window,
times[i] - The third access in the window,
times[i + 2]
- If:
times[i + 2] - times[i] < 60
then the employee has three accesses within a period shorter than one hour. 8. Add that employee to the answer list and stop checking further windows for that employee. 9. Return the collected employee names.
Why it works
After sorting, every group of three accesses appears in chronological order. If an employee has any valid set of three accesses within less than one hour, then the earliest and latest access among those three must appear as the endpoints of some consecutive triple in the sorted sequence. Therefore checking every consecutive triple is sufficient to detect every valid case. The algorithm never misses a valid employee and never incorrectly includes an invalid one.
Python Solution
from typing import List
from collections import defaultdict
class Solution:
def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
employee_times = defaultdict(list)
for name, time_str in access_times:
hours = int(time_str[:2])
minutes = int(time_str[2:])
total_minutes = hours * 60 + minutes
employee_times[name].append(total_minutes)
result = []
for name, times in employee_times.items():
times.sort()
for i in range(len(times) - 2):
if times[i + 2] - times[i] < 60:
result.append(name)
break
return result
The implementation begins by grouping access records by employee using a defaultdict.
Each timestamp is converted from "HHMM" format into minutes since midnight. This makes time comparisons simple integer subtraction instead of string manipulation.
After grouping, the access times for each employee are sorted chronologically.
The code then checks every consecutive triple of accesses. If the first and third accesses in the triple differ by less than 60 minutes, the employee satisfies the high-access condition and is added to the result list.
The break statement is important because once an employee is confirmed as high-access, there is no need to continue scanning their remaining access times.
Go Solution
package main
import "sort"
func findHighAccessEmployees(access_times [][]string) []string {
employeeTimes := make(map[string][]int)
for _, record := range access_times {
name := record[0]
timeStr := record[1]
hours := int(timeStr[0]-'0')*10 + int(timeStr[1]-'0')
minutes := int(timeStr[2]-'0')*10 + int(timeStr[3]-'0')
totalMinutes := hours*60 + minutes
employeeTimes[name] = append(employeeTimes[name], totalMinutes)
}
var result []string
for name, times := range employeeTimes {
sort.Ints(times)
for i := 0; i+2 < len(times); i++ {
if times[i+2]-times[i] < 60 {
result = append(result, name)
break
}
}
}
return result
}
The Go implementation follows the same logic as the Python version. A map from employee name to a slice of integer timestamps is used for grouping. Time conversion is performed directly from the string characters. After sorting each slice with sort.Ints, consecutive triples are checked.
There are no integer overflow concerns because the largest timestamp is 23:59, which converts to only 1439 minutes.
Worked Examples
Example 1
Input:
[["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]
After grouping and conversion:
| Employee | Times (minutes) |
|---|---|
| a | [349, 332, 381] |
| b | [297, 340] |
After sorting:
| Employee | Sorted Times |
|---|---|
| a | [332, 349, 381] |
| b | [297, 340] |
Checking employee a:
| Window | Difference |
|---|---|
| [332,349,381] | 381 - 332 = 49 |
Since 49 < 60, employee a is high-access.
Checking employee b:
Only two accesses exist, so no triple can be formed.
Result:
["a"]
Example 2
Input:
[["d","0002"],["c","0808"],["c","0829"],["e","0215"],
["d","1508"],["d","1444"],["d","1410"],["c","0809"]]
After conversion and sorting:
| Employee | Sorted Times |
|---|---|
| c | [488, 489, 509] |
| d | [2, 850, 884, 908] |
| e | [135] |
Employee c:
| Window | Difference |
|---|---|
| [488,489,509] | 21 |
Valid.
Employee d:
| Window | Difference |
|---|---|
| [2,850,884] | 882 |
| [850,884,908] | 58 |
Second window is valid.
Employee e:
Only one access.
Result:
["c", "d"]
Example 3
Input:
[["cd","1025"],["ab","1025"],["cd","1046"],
["cd","1055"],["ab","1124"],["ab","1120"]]
After conversion:
| Employee | Sorted Times |
|---|---|
| cd | [625, 646, 655] |
| ab | [625, 680, 684] |
Employee cd:
| Window | Difference |
|---|---|
| [625,646,655] | 30 |
Valid.
Employee ab:
| Window | Difference |
|---|---|
| [625,680,684] | 59 |
Valid.
Result:
["ab", "cd"]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting dominates the running time |
| Space | O(n) | Hash map stores all converted timestamps |
Let n be the total number of access records. Every record is inserted once into the hash map. If an employee has k accesses, sorting costs O(k log k). Summed across all employees, the total sorting cost is bounded by O(n log n). The subsequent scans are linear. The hash map and timestamp lists store all records, requiring O(n) extra space.
Test Cases
from collections import Counter
s = Solution()
assert Counter(
s.findHighAccessEmployees(
[["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]
)
) == Counter(["a"]) # example 1
assert Counter(
s.findHighAccessEmployees(
[["d","0002"],["c","0808"],["c","0829"],["e","0215"],
["d","1508"],["d","1444"],["d","1410"],["c","0809"]]
)
) == Counter(["c", "d"]) # example 2
assert Counter(
s.findHighAccessEmployees(
[["cd","1025"],["ab","1025"],["cd","1046"],
["cd","1055"],["ab","1124"],["ab","1120"]]
)
) == Counter(["ab", "cd"]) # example 3
assert s.findHighAccessEmployees(
[["a","0800"],["a","0830"]]
) == [] # fewer than three accesses
assert Counter(
s.findHighAccessEmployees(
[["a","0800"],["a","0800"],["a","0800"]]
)
) == Counter(["a"]) # identical timestamps
assert s.findHighAccessEmployees(
[["a","0800"],["a","0830"],["a","0900"]]
) == [] # exactly 60 minutes apart
assert Counter(
s.findHighAccessEmployees(
[["a","0800"],["a","0830"],["a","0859"]]
)
) == Counter(["a"]) # 59 minute span
assert s.findHighAccessEmployees(
[["a","0005"],["a","2350"],["a","2359"]]
) == [] # no midnight wraparound
assert Counter(
s.findHighAccessEmployees(
[["a","1000"],["a","1010"],["a","1020"],
["b","1200"],["b","1300"],["b","1400"]]
)
) == Counter(["a"]) # one qualifying employee
assert Counter(
s.findHighAccessEmployees(
[["x","0800"],["x","0810"],["x","0820"],
["x","1000"],["x","1010"],["x","1020"]]
)
) == Counter(["x"]) # multiple qualifying windows
Test Case Summary
| Test | Why |
|---|---|
| Example 1 | Basic qualifying employee |
| Example 2 | Multiple qualifying employees |
| Example 3 | Qualification near one-hour boundary |
| Two accesses only | Cannot form a valid triple |
| Three identical timestamps | Handles duplicates correctly |
| Exactly 60 minutes span | Confirms strict inequality |
| 59 minute span | Valid qualifying window |
| Midnight-related times | Ensures no day wraparound |
| Mixed qualifying and non-qualifying employees | Correct employee selection |
| Multiple valid windows | Stops correctly after qualification |
Edge Cases
One important edge case occurs when an employee has fewer than three access records. Such an employee can never satisfy the requirement because the definition explicitly requires at least three accesses. The implementation naturally handles this because the loop checking triples only runs when at least three timestamps exist.
Another important edge case is when the earliest and latest timestamps in a triple are exactly 60 minutes apart. The problem states that exactly one hour does not count. A common bug is using <= 60 instead of < 60. The implementation correctly uses strict inequality, ensuring that a span of exactly 60 minutes is rejected.
Duplicate timestamps are also important. An employee may access the system multiple times at the exact same minute. After sorting, duplicates remain adjacent, and the difference between the first and third access may still be less than 60 minutes, often even zero. Since the problem counts accesses rather than distinct timestamps, the implementation correctly treats duplicate timestamps as separate accesses.
A final subtle case involves timestamps near midnight. Because all accesses occur within the same day, times such as 23:50 and 00:05 should not be considered only 15 minutes apart. Converting times to minutes since midnight and sorting them numerically preserves the correct chronological ordering and prevents accidental wraparound logic.