High-Access Employees
High-Access Employees is a medium arrays & hashing problem solved with the sliding window · fixed pattern.
The best approach, optimal (group, sort, check every third), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from count every window up.
Problem
You are given a log accessTimes of badge swipes. Each entry [name, time] says that employee name entered the building at time, written as four digits HHMM in 24-hour format (for example "0905" or "2310"). All swipes are from the same day, and the log is not sorted.
An employee is high-access if they swiped three or more times within a period shorter than one hour, meaning the first and last of those swipes are less than 60 minutes apart (10:00 and 10:59 qualify, 10:00 and 11:00 do not). Swipes at the very start and end of the day are not considered close.
Return the names of all high-access employees, in any order.
Examples
Example 1
- Input
accessTimes = [["teal", "0915"], ["teal", "0950"], ["amber", "1200"], ["teal", "1014"], ["amber", "1300"], ["amber", "1230"]]- Output
["teal"]- Why
- teal's accesses at 09:15, 09:50 and 10:14 span 59 minutes. amber's three accesses span exactly 60 minutes (12:00 to 13:00), which is not strictly less than an hour.
Example 2
- Input
accessTimes = [["rust", "2350"], ["rust", "0005"], ["rust", "0010"]]- Output
[]- Why
- All times are on the same day, so 23:50 and 00:05 are almost a full day apart; no window of under an hour contains three accesses.
Example 3
- Input
accessTimes = [["onyx", "0800"], ["jade", "0100"], ["onyx", "0800"], ["onyx", "0800"]]- Output
["onyx"]- Why
- Three accesses at the very same minute count.
Constraints
1 <= accessTimes.length <= 100accessTimes[i] = [name, time];namehas1to10lowercase English letters.timehas exactly four digitsHHMMin 24-hour format, from0000to2359.- All accesses happen on the same day; the same person may have several accesses at the same time.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Count every window | O(n²) | O(n) |
| Optimal (group, sort, check every third) | O(n log n) | O(n) |
1Count every window
O(n²)For each of up to n times we scan that person's whole list.O(n)The grouped lists hold all n times.Group times per employee. For each access time t of a person, count how many of their accesses lie in [t, t + 59]. If some window holds three or more, the person is high-access.
- Map each name to a list of minutes (
HH * 60 + MM). - For each person and each of their times
t, count timesxwitht <= x < t + 60. - Add the name to the answer as soon as a count reaches 3.
class Solution {
public List<String> findHighAccessEmployees(List<List<String>> accessTimes) {
Map<String, List<Integer>> byName = new HashMap<>();
for (List<String> a : accessTimes) {
String t = a.get(1);
int minutes = Integer.parseInt(t.substring(0, 2)) * 60 + Integer.parseInt(t.substring(2));
byName.computeIfAbsent(a.get(0), k -> new ArrayList<>()).add(minutes);
}
List<String> result = new ArrayList<>();
for (Map.Entry<String, List<Integer>> e : byName.entrySet()) {
boolean high = false;
for (int start : e.getValue()) {
int count = 0;
for (int x : e.getValue()) if (x >= start && x < start + 60) count++;
if (count >= 3) high = true;
}
if (high) result.add(e.getKey());
}
return result;
}
}class Solution:
def findHighAccessEmployees(self, accessTimes: List[List[str]]) -> List[str]:
by_name = defaultdict(list)
for name, t in accessTimes:
by_name[name].append(int(t[:2]) * 60 + int(t[2:]))
result = []
for name, times in by_name.items():
high = False
for start in times:
count = sum(1 for x in times if start <= x < start + 60)
if count >= 3:
high = True
if high:
result.append(name)
return resultclass Solution {
public:
vector<string> findHighAccessEmployees(vector<vector<string>>& accessTimes) {
unordered_map<string, vector<int>> byName;
for (auto& a : accessTimes) {
const string& t = a[1];
byName[a[0]].push_back(stoi(t.substr(0, 2)) * 60 + stoi(t.substr(2)));
}
vector<string> result;
for (auto& [name, times] : byName) {
bool high = false;
for (int start : times) {
int count = 0;
for (int x : times) if (x >= start && x < start + 60) count++;
if (count >= 3) high = true;
}
if (high) result.push_back(name);
}
return result;
}
};function findHighAccessEmployees(accessTimes) {
const byName = new Map();
for (const [name, t] of accessTimes) {
const minutes = parseInt(t.substring(0, 2), 10) * 60 + parseInt(t.substring(2), 10);
if (!byName.has(name)) byName.set(name, []);
byName.get(name).push(minutes);
}
const result = [];
for (const [name, times] of byName) {
let high = false;
for (const start of times) {
let count = 0;
for (const x of times) if (x >= start && x < start + 60) count++;
if (count >= 3) high = true;
}
if (high) result.push(name);
}
return result;
}2Optimal (group, sort, check every third)
O(n log n)Sorting the grouped lists costs O(n log n) in total; the scan is linear.O(n)The grouped lists hold all n times.Sort each person's minutes. Any three accesses inside a window shorter than an hour can be replaced by three consecutive sorted accesses that are at least as tight, so it is enough to test t[i + 2] - t[i] < 60 for each i.
- Group minutes by name.
- Sort each list.
- If some
ihast[i + 2] - t[i] < 60, add the name.
class Solution {
public List<String> findHighAccessEmployees(List<List<String>> accessTimes) {
Map<String, List<Integer>> byName = new HashMap<>();
for (List<String> a : accessTimes) {
String t = a.get(1);
int minutes = Integer.parseInt(t.substring(0, 2)) * 60 + Integer.parseInt(t.substring(2));
byName.computeIfAbsent(a.get(0), k -> new ArrayList<>()).add(minutes);
}
List<String> result = new ArrayList<>();
for (Map.Entry<String, List<Integer>> e : byName.entrySet()) {
List<Integer> times = e.getValue();
Collections.sort(times);
for (int i = 0; i + 2 < times.size(); i++) {
if (times.get(i + 2) - times.get(i) < 60) {
result.add(e.getKey());
break;
}
}
}
return result;
}
}class Solution:
def findHighAccessEmployees(self, accessTimes: List[List[str]]) -> List[str]:
by_name = defaultdict(list)
for name, t in accessTimes:
by_name[name].append(int(t[:2]) * 60 + int(t[2:]))
result = []
for name, times in by_name.items():
times.sort()
for i in range(len(times) - 2):
if times[i + 2] - times[i] < 60:
result.append(name)
break
return resultclass Solution {
public:
vector<string> findHighAccessEmployees(vector<vector<string>>& accessTimes) {
unordered_map<string, vector<int>> byName;
for (auto& a : accessTimes) {
const string& t = a[1];
byName[a[0]].push_back(stoi(t.substr(0, 2)) * 60 + stoi(t.substr(2)));
}
vector<string> result;
for (auto& [name, times] : byName) {
sort(times.begin(), times.end());
for (size_t i = 0; i + 2 < times.size(); i++) {
if (times[i + 2] - times[i] < 60) {
result.push_back(name);
break;
}
}
}
return result;
}
};function findHighAccessEmployees(accessTimes) {
const byName = new Map();
for (const [name, t] of accessTimes) {
const minutes = parseInt(t.substring(0, 2), 10) * 60 + parseInt(t.substring(2), 10);
if (!byName.has(name)) byName.set(name, []);
byName.get(name).push(minutes);
}
const result = [];
for (const [name, times] of byName) {
times.sort((a, b) => a - b);
for (let i = 0; i + 2 < times.length; i++) {
if (times[i + 2] - times[i] < 60) {
result.push(name);
break;
}
}
}
return result;
}Edge cases to test
- Exactly 60 minutes between the first and third access (not high-access)
- Times that would only be close if the day wrapped around midnight
- Duplicate timestamps for one person
- Accesses listed out of chronological order
Hints
Hint 1
Group the times by employee and convert each HHMM string to minutes since midnight.
Hint 2
If any three accesses fit in a window shorter than an hour, then three accesses that are consecutive in sorted order also fit.
Hint 3
After sorting one person's minutes, check whether t[i + 2] - t[i] < 60 for some i.
FAQ
What is the best time complexity for High-Access Employees?
Optimal (group, sort, check every third) runs in O(n log n) time and O(n) extra space. Sorting the grouped lists costs O(n log n) in total; the scan is linear.
Which pattern does High-Access Employees use?
It is a arrays & hashing problem that uses the sliding window · fixed pattern. Other problems with the same pattern: Maximum Average Subarray I, K Radius Subarray Averages, Maximum Number of Vowels in a Substring of Given Length.
Is there a brute force solution for High-Access Employees?
Yes. Count every window takes O(n²) time and O(n) space. Group times per employee.
Which edge cases should I test for High-Access Employees?
Exactly 60 minutes between the first and third access (not high-access); Times that would only be close if the day wrapped around midnight; Duplicate timestamps for one person; Accesses listed out of chronological order.