High-Access Employees

Medium Arrays & Hashing Sliding Window · Fixed Original on LeetCode

Reported atAtlassian

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 <= 100
  • accessTimes[i] = [name, time]; name has 1 to 10 lowercase English letters.
  • time has exactly four digits HHMM in 24-hour format, from 0000 to 2359.
  • 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.

00:00
Testcase

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.

ApproachTimeSpace
Count every windowO(n²)O(n)
Optimal (group, sort, check every third)O(n log n)O(n)

1Count every window

TimeO(n²)For each of up to n times we scan that person's whole list.
SpaceO(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.

  1. Map each name to a list of minutes (HH * 60 + MM).
  2. For each person and each of their times t, count times x with t <= x < t + 60.
  3. 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;
    }
}

2Optimal (group, sort, check every third)

TimeO(n log n)Sorting the grouped lists costs O(n log n) in total; the scan is linear.
SpaceO(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.

  1. Group minutes by name.
  2. Sort each list.
  3. If some i has t[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;
    }
}

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.