2933. High-Access Employees

MediumArrayHash TableStringSorting
Leetcode Link

Problem Description

The goal is to identify employees who have accessed a system frequently within short periods of time. Assuming we have each employee's access records for a single day, we are to determine which of them have accessed the system three or more times within any one-hour period.

To clarify, the period must be less than or equal to 60 minutes, but cannot span across the start and end of the day. For example, times such as "0815" and "0915" are not considered within the same hour, and neither are times like "0005" and "2350" since they are at the start and end of the day, respectively.

We are presented with a 2D array access_times, where each entry contains an employee's name and their access time. The access time is given in 24-hour format without a colon, so "0800" represents 8:00 AM and "2250" represents 10:50 PM. We need to return a list of names of employees who are considered high-access, without any specific order of the names.

Intuition

To solve this problem, we use a hashmap (or in Python, a defaultdict) to group all access times by the employee’s name. The keys in this hashmap are the names of the employees, and the corresponding values are lists containing all their access times converted to minutes since midnight. This conversion simplifies the comparison of times by translating all access times into a single numerical format.

Once we've grouped all the access times for each employee, the next step is to sort these times in ascending order to easily check for any instances where three or more accesses occurred within a 60-minute window.

After sorting, we iterate over the access times for each employee. If at any point we find three consecutive times t1, t2, and t3 such that t3 - t1 is less than 60 minutes, it implies that those accesses happened within the same one-hour period, and we can conclude that the employee is a 'high-access' employee.

The intuition behind this approach is that if an employee has accessed the system three or more times in any one-hour period, sorting the times makes it straightforward to check for a 60-minute window containing at least three timestamps.

In summary, the solution involves:

  1. Grouping and converting all access times to a numerical format.
  2. Sorting the access times to identify potential one-hour periods.
  3. Checking for the presence of three accesses within these periods for each employee.
  4. Collecting the names of employees who meet the 'high-access' criteria.

Learn more about Sorting patterns.

Solution Approach

The solution uses a hash table (specifically a defaultdict from Python's collections module), which is an ideal data structure for grouping elements based on a key. In this implementation, the key for the hash table is the employee's name, and the value is a list of their access times in minutes.

The first step is iterating over the access_times array to build the hash table with the employees and their respective access times. Within this loop, we convert the access time to minutes by taking the first two characters of the access time string as hours, converting them to an integer and multiplying by 60 to obtain the equivalent minutes, and adding the minutes, which are obtained by converting the last two characters of the access time string to an integer.

Now, the key aspect of this solution is to sort the times to make the checks for the one-hour period straightforward. Sorting ensures that we can look at each consecutive triplet of access times to check if they are within 60 minutes of each other.

After sorting each employee's access times, we loop through the sorted times and use a sliding window approach to check for consecutive triplets. The sliding window comprises three consecutive elements at a time because we are interested in periods where there are at least three accesses.

We check if the difference between the first and the third access time in the sliding window is less than 60 minutes. If this condition is true for any triplet, the employee's name is added to the ans list which records the names of high-access employees.

The final step is to return the list ans, containing all the high-access employee names identified by the algorithm.

Here's the approach translated into pseudo code:

  1. Initialize hash table d for grouping access times by employee names.
  2. For each name and time in access_times:
    • Calculate total minutes from 00:00 and group it under the equivalent employee name in d.
  3. Initialize ans as an empty list to store results.
  4. For each employee name and its access times in d:
    • Sort the list of times.
    • For i from 2 to the length of the list of times:
      • If the time at index i minus time at index i - 2 is less than 60:
        • Add employee name to ans.
  5. Return the ans list.

By combining the hash table for organization, the sorting for temporal ordering, and a simple iteration with conditional checks, we elegantly solve the problem without the need for complex algorithms. This approach is efficient as it takes advantage of the easily sortable nature of times and the straightforward conditions set by the problem to identify high-access employees.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's take an example access records data:

1Alice 0800
2Bob   0830
3Alice 0835
4Carol 0855
5Alice 0900
6Bob   0840
7Carol 0905
8Bob   0920
9Carol 0950
10Alice 0915

Following the solution approach, we'll process the records:

  1. Initialize hash table d for grouping access times by employee names. d would look like this after processing:

    1{
    2  "Alice": [],
    3  "Bob": [],
    4  "Carol": []
    5}
  2. For each name and time in access_times: We convert access times for Alice, Bob, and Carol to minutes: Alice's times: [480, 515, 540, 555] (8:00 AM, 8:35 AM, 9:00 AM, 9:15 AM) Bob's times: [510, 540, 560] (8:30 AM, 9:00 AM, 9:20 AM) Carol's times: [535, 545, 590] (8:55 AM, 9:05 AM, 9:50 AM)

    Now, d would look like this:

    1{
    2  "Alice": [480, 515, 540, 555],
    3  "Bob": [510, 540, 560],
    4  "Carol": [535, 545, 590]
    5}
  3. Initialize ans as an empty list to store results. ans = []

  4. For each employee name and its access times in d:

    • Sort the list of times. (In our case, times are already sorted)
    • Loop through each employee's times checking for a window where three accesses are within 60 minutes.

    For Alice:

    • We check at index 2 (540) - index 0 (480) = 60 minutes, but we need less than 60.
    • Move to next window and check index 3 (555) - index 1 (515) = 40 minutes. It's within 60 minutes, so we identify Alice as a high-access employee and add her to ans.

    For Bob:

    • We check at index 2 (560) - index 0 (510) = 50 minutes. It's within 60 minutes, so we add Bob to ans.

    For Carol:

    • Since there are only three records and the difference between the last and first is greater than 60 minutes (590 - 535 = 55 minutes), Carol is not added.

So the ans list after the checks:

1["Alice", "Bob"]
  1. Return the ans list. The returned result is the list of employees who accessed the system three or more times in any one-hour period. For our example, the final output is:
    1["Alice", "Bob"]

Through this example, we've illustrated how the solution approach effectively identifies 'high-access' employees by leveraging a hash table, sorting, and a sliding window check.

Solution Implementation

1from collections import defaultdict  # required for defaultdict usage
2
3class Solution:
4    def findHighAccessEmployees(self, access_times):
5        """
6        Identifies employees with high access frequency within any one-hour window.
7
8        :param access_times: List of lists containing employee names and corresponding access times
9        :type access_times: List[List[str]]
10        :return: List of employee names with high access frequency
11        """
12        access_dict = defaultdict(list)  # Create a default dictionary to hold access times for each employee
13
14        # Convert access times to minutes and store in the dictionary
15        for name, time_str in access_times:
16            # Convert timestamp 'HHMM' to total minutes since 00:00
17            total_minutes = int(time_str[:2]) * 60 + int(time_str[2:])
18            access_dict[name].append(total_minutes)
19
20        high_access_employees = []  # List to hold the names of high access frequency employees
21
22        # Iterate over each employee's access times to detect high frequency
23        for name, timestamps in access_dict.items():
24            timestamps.sort()  # Sort timestamps for each employee
25            # Check for any three consecutive timestamps within a 60-minute window
26            for i in range(2, len(timestamps)):
27                if timestamps[i] - timestamps[i - 2] < 60:
28                    high_access_employees.append(name)
29                    break  # We already know this employee has high access, no need to check further
30          
31        return high_access_employees  # Return the list of names
32
1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.HashMap;
4import java.util.List;
5import java.util.Map;
6
7class Solution {
8
9    // Method to find employees who have accessed a system frequently in a short time frame
10    public List<String> findHighAccessEmployees(List<List<String>> accessTimes) {
11        // Create a map to track the access times for each employee
12        Map<String, List<Integer>> employeeAccessMap = new HashMap<>();
13
14        // Loop through all provided access times
15        for (List<String> entry : accessTimes) {
16            String employeeName = entry.get(0);
17            String time = entry.get(1);
18
19            // Convert access time from String to minutes as Integer
20            int timeInMinutes = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(2));
21
22            // Add the access time to the list for the corresponding employee in the map
23            // If no list exists yet for the employee, create it
24            employeeAccessMap.computeIfAbsent(employeeName, k -> new ArrayList<>()).add(timeInMinutes);
25        }
26
27        // List to hold the names of employees with frequent accesses
28        List<String> frequentAccessEmployees = new ArrayList<>();
29
30        // Iterate through each employee's entry in the map
31        for (Map.Entry<String, List<Integer>> entry : employeeAccessMap.entrySet()) {
32            String employeeName = entry.getKey();
33            List<Integer> accessTimesList = entry.getValue();
34
35            // Sort the access times in ascending order to check for three consecutive accesses within a 60-minute window
36            Collections.sort(accessTimesList);
37
38            // Check for three or more consecutive accesses within a 60-minute window
39            for (int i = 2; i < accessTimesList.size(); ++i) {
40                if (accessTimesList.get(i) - accessTimesList.get(i - 2) < 60) {
41                    // If such a pattern is found, add the employee's name to the result list
42                    frequentAccessEmployees.add(employeeName);
43                    break; // No need to check the rest of the times for this employee
44                }
45            }
46        }
47        // Return the list of employees with frequent access patterns
48        return frequentAccessEmployees;
49    }
50}
51
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9    // Method to find employees with high access frequency within any 1-hour period
10    vector<string> findHighAccessEmployees(vector<vector<string>>& accessTimes) {
11        // Map to store access times for each employee
12        unordered_map<string, vector<int>> employeeAccessMap;
13
14        // Iterate over each access record
15        for (const auto& record : accessTimes) {
16            const string& employeeName = record[0];
17            const string& timeStr = record[1];
18          
19            // Convert HHMM format string to total minutes
20            int timeMinutes = stoi(timeStr.substr(0, 2)) * 60 + stoi(timeStr.substr(3, 2));
21          
22            // Add this time to the list of times for this employee
23            employeeAccessMap[employeeName].emplace_back(timeMinutes);
24        }
25
26        // Vector to store the names of high access frequency employees
27        vector<string> highFrequencyEmployees;
28      
29        // Iterate over each employee's access records
30        for (auto& [employeeName, times] : employeeAccessMap) {
31            // Sort the access times in ascending order
32            sort(times.begin(), times.end());
33
34            // Look for three consecutive times within a 60 minute period
35            for (int i = 2; i < times.size(); ++i) {
36                if (times[i] - times[i - 2] < 60) { // Found 3 accesses within a 60-min window
37                    highFrequencyEmployees.emplace_back(employeeName);
38                    break; // No need to check further for this employee
39                }
40            }
41        }
42
43        // Return the list of employees with high access frequency
44        return highFrequencyEmployees;
45    }
46};
47
1function findHighAccessEmployees(accessTimes: string[][]): string[] {
2  // Create a map to hold employee names as keys and an array of
3  // access times in minutes as values.
4  const employeeAccessMap: Map<string, number[]> = new Map();
5
6  // Loop over each access record in the input array.
7  for (const [name, timeString] of accessTimes) {
8    // Convert hour part of the time string to minutes.
9    const hours = parseInt(timeString.slice(0, 2), 10);
10    // Convert minute part of the time string to integer.
11    const minutes = parseInt(timeString.slice(2), 10);
12    // Calculate the total minutes since midnight.
13    const totalTime = hours * 60 + minutes;
14
15    // If the employee name does not exist in the map, add it.
16    if (!employeeAccessMap.has(name)) {
17      employeeAccessMap.set(name, []);
18    }
19
20    // Append the access time to the employee's list of access times.
21    employeeAccessMap.get(name)!.push(totalTime);
22  }
23
24  // Initialize an array to hold the names of employees with high access frequency.
25  const highAccessEmployees: string[] = [];
26
27  // Iterate over each employee and their corresponding access times.
28  for (const [name, accessTimes] of employeeAccessMap) {
29    // Sort the access times in ascending order.
30    accessTimes.sort((a, b) => a - b);
31
32    // Go through the sorted access times to find employees who accessed 3 times within a 60-minute window.
33    for (let i = 2; i < accessTimes.length; ++i) {
34      // Check if there is a 60-minute window between the current and two prior access times.
35      if (accessTimes[i] - accessTimes[i - 2] < 60) {
36        // Add employee name to the result list and break out of the loop as we have found a valid access pattern.
37        highAccessEmployees.push(name);
38        break;
39      }
40    }
41  }
42
43  // Return the names of employees with high access frequency.
44  return highAccessEmployees;
45}
46

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is composed of several parts:

  1. Creating the defaultdict for employees' access times — This takes O(n) time where n is the number of access records, as we loop through the access_times list once.

  2. Casting times to minutes and appending to the list in the dictionary — Each conversion takes constant time, so with n access records this part is also O(n).

  3. Sorting the timestamps for each employee — Sorting is commonly O(k \times log(k)) where k is the number of timestamps for an employee. As we need to perform this for all employees, the total time is O(m \times k \times log(k)) where m is the number of unique employees. In the worst case, where all timestamps belong to the same employee, this is equivalent to O(n \log n).

  4. Checking within each sorted list for the violation condition — We iterate over sorted timestamps for each employee which could be at worst O(n) if all timestamps are for a single employee. However, since the comparison is a constant time operation, it does not change the sorting time complexity we calculated earlier.

Hence, we combine the time complexities: O(n) + O(n \log n) which simplifies to O(n \log n) because O(n \log n) is the dominant term.

Space Complexity

The space complexity can be analyzed as follows:

  1. The dictionary storing employee names and their access times — If m is the number of unique employees and k is the average number of access timestamps per employee, the space complexity would be O(m \times k). However, as m \times k is essentially n, we get O(n) space complexity.

  2. The sorted list of timestamps — This doesn't take additional space beyond what is used in the dictionary as it sorts the timestamps in place.

  3. The answer list — In the worst case, where every employee name is added to the answer list, the space complexity would again be O(m), which is a subset of O(n).

Combining all parts, the space complexity of this algorithm is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄