# High-Access Employees
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/high-access-employees)
Canonical: https://scaleengineer.com/dsa/problems/high-access-employees
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian)
---
## Problem
You are given a 2D **0-indexed** array of strings, `access_times`, with size `n`. For each `i` where `0 <= i <= n - 1`, `access_times[i][0]` represents the name of an employee, and `access_times[i][1]` represents the access time of that employee. All entries in `access_times` are within the same day.

The access time is represented as **four digits** using a **24-hour** time format, for example, `"0800"` or `"2250"`.

An employee is said to be **high-access** if he has accessed the system **three or more** times within a **one-hour period**.

Times with exactly one hour of difference are **not** considered part of the same one-hour period. For example, `"0815"` and `"0915"` are not part of the same one-hour period.

Access times at the start and end of the day are **not** counted within the same one-hour period. For example, `"0005"` and `"2350"` are not part of the same one-hour period.

Return _a list that contains the names of **high-access** employees with any order you want._

**Example 1:**

**Input:** access_times = [["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]
**Output:** ["a"]
**Explanation:** "a" has three access times in the one-hour period of [05:32, 06:31] which are 05:32, 05:49, and 06:21.
But "b" does not have more than two access times at all.
So the answer is ["a"].

**Example 2:**

**Input:** access_times = [["d","0002"],["c","0808"],["c","0829"],["e","0215"],["d","1508"],["d","1444"],["d","1410"],["c","0809"]]
**Output:** ["c","d"]
**Explanation:** "c" has three access times in the one-hour period of [08:08, 09:07] which are 08:08, 08:09, and 08:29.
"d" has also three access times in the one-hour period of [14:10, 15:09] which are 14:10, 14:44, and 15:08.
However, "e" has just one access time, so it can not be in the answer and the final answer is ["c","d"].

**Example 3:**

**Input:** access_times = [["cd","1025"],["ab","1025"],["cd","1046"],["cd","1055"],["ab","1124"],["ab","1120"]]
**Output:** ["ab","cd"]
**Explanation:** "ab" has three access times in the one-hour period of [10:25, 11:24] which are 10:25, 11:20, and 11:24.
"cd" has also three access times in the one-hour period of [10:25, 11:24] which are 10:25, 10:46, and 10:55.
So the answer is ["ab","cd"].

**Constraints:**

* `1 <= access_times.length <= 100`
* `access_times[i].length == 2`
* `1 <= access_times[i][0].length <= 10`
* `access_times[i][0]` consists only of English small letters.
* `access_times[i][1].length == 4`
* `access_times[i][1]` is in 24-hour time format.
* `access_times[i][1]` consists only of `'0'` to `'9'`.

# Approaches
## Brute-Force Check with Grouping
This approach first groups all access times by employee. Then, for each employee with at least three accesses, it checks every possible combination of three access times to see if they fall within a one-hour period. This is a straightforward but computationally expensive method.
**Time:** O(N + E * k_max^3), where `N` is the total number of access records, `E` is the number of unique employees, and `k_max` is the maximum number of accesses for a single employee. In the worst case, one employee has all `N` accesses, leading to a complexity of `O(N^3)`. · **Space:** O(N), where N is the total number of access records. This space is used to store the map of employees and their access times.
**Pros:** Conceptually simple and easy to understand.; Correctly solves the problem by exhaustively checking all possibilities.
**Cons:** Highly inefficient due to the cubic time complexity (`O(k^3)`) for checking combinations for each employee.; For the given constraints (`N <= 100`), it might pass, but it's not a scalable solution for larger datasets.
### Explanation
The core idea is to systematically check all possibilities. 

1.  **Group by Employee**: We start by iterating through the `access_times` list. We use a `HashMap` where keys are employee names and values are lists of their access times. To make comparisons easier, we convert the time strings (e.g., "0830") into integers (e.g., 830).
2.  **Iterate and Check Combinations**: After grouping, we iterate through each employee in the map. If an employee has fewer than three access records, they cannot be a high-access employee, so we skip them.
3.  **Validate Time Window**: For employees with three or more accesses, we generate all unique combinations of three access times using three nested loops. For each combination of three times (`t1`, `t2`, `t3`), we find the earliest (`min_time`) and latest (`max_time`). We then check if `max_time - min_time < 100`. The difference of 100 corresponds to exactly one hour (e.g., 0815 to 0915 is a difference of 100). A difference less than 100 means the accesses are within a one-hour period.
4.  **Add to Result**: If we find such a combination, we mark the employee as high-access, add their name to a result set, and break the inner loops to check the next employee.

```java
import java.util.*;

class Solution {
    public List<String> findHighAccessEmployees(List<List<String>> access_times) {
        Map<String, List<Integer>> employeeAccesses = new HashMap<>();
        for (List<String> access : access_times) {
            String name = access.get(0);
            // Convert "HHMM" string to an integer for easy comparison
            int time = Integer.parseInt(access.get(1));
            employeeAccesses.computeIfAbsent(name, k -> new ArrayList<>()).add(time);
        }

        Set<String> highAccessEmployees = new HashSet<>();
        for (Map.Entry<String, List<Integer>> entry : employeeAccesses.entrySet()) {
            String name = entry.getKey();
            List<Integer> times = entry.getValue();

            if (times.size() < 3) {
                continue;
            }

            // Brute-force check for every combination of 3 times
            for (int i = 0; i < times.size(); i++) {
                for (int j = i + 1; j < times.size(); j++) {
                    for (int k = j + 1; k < times.size(); k++) {
                        int t1 = times.get(i);
                        int t2 = times.get(j);
                        int t3 = times.get(k);
                        
                        int minTime = Math.min(t1, Math.min(t2, t3));
                        int maxTime = Math.max(t1, Math.max(t2, t3));

                        if (maxTime - minTime < 100) {
                            highAccessEmployees.add(name);
                            // Break loops for this employee as they are already identified
                            i = times.size();
                            j = times.size();
                            k = times.size();
                        }
                    }
                }
            }
        }

        return new ArrayList<>(highAccessEmployees);
    }
}
```
### Algorithm
- Create a `HashMap<String, List<Integer>>` to store access times for each employee.
- Iterate through the input `access_times`, parse the time string (e.g., "0830") to an integer (e.g., 830), and populate the map.
- Create a `HashSet<String>` to store the names of high-access employees, which helps in avoiding duplicate entries.
- For each employee in the map:
    - If they have fewer than 3 accesses, continue to the next employee.
    - Use three nested loops to iterate through all unique combinations of three access times.
    - For each combination, find the minimum and maximum time.
    - If `max_time - min_time < 100`, it means the three accesses are within a one-hour period. Add the employee's name to the set and break all three loops for this employee to proceed to the next.
- Convert the set of names to a list and return it.

## Grouping, Sorting, and Sliding Window
This is a much more efficient approach. It also starts by grouping access times per employee. However, instead of checking all combinations, it sorts the access times for each employee. With a sorted list, we can efficiently check for three accesses within an hour using a sliding window of size three.
**Time:** O(N * log K), where `N` is the total number of access records and `K` is the maximum number of accesses by a single employee. The grouping takes `O(N)`. Then, for each employee with `k` accesses, we sort in `O(k log k)` and scan in `O(k)`. The total time is dominated by sorting. In the worst case where one employee has all `N` accesses, the complexity is `O(N log N)`. · **Space:** O(N), where N is the total number of access records. This space is required to build the map of employees to their access times.
**Pros:** Much more efficient than the brute-force approach.; The `O(N log K)` complexity is well-suited for the given constraints and scales much better.; The logic is clean and easy to follow once the sorting idea is established.
**Cons:** The sorting step adds a `log K` factor to the complexity, but this is a minor drawback compared to the significant performance gain over the brute-force method.
### Explanation
This optimized approach leverages sorting to avoid the costly combination checks.

1.  **Group by Employee**: Same as the first approach, we use a `HashMap` to group access times by employee, converting time strings to integers.
2.  **Sort Access Times**: For each employee, we take their list of access times and sort it in ascending order. This is the key step that enables an efficient check. If there are three accesses within an hour, they will be adjacent in the sorted list.
3.  **Sliding Window Check**: After sorting, we can iterate through the list of times with a fixed-size window of 3. We start from the first access time (`times[0]`) and check the window `(times[0], times[1], times[2])`.
4.  **Validate Time Window**: Because the list is sorted, the first element of any window is the minimum and the last is the maximum. So, for a window starting at index `i`, we only need to check if `times[i+2] - times[i] < 100`. If this condition holds, we have found three accesses within a one-hour period.
5.  **Add to Result and Continue**: If the condition is met, we add the employee's name to our result list and immediately move on to the next employee, as we have already confirmed their high-access status. This avoids redundant checks.

```java
import java.util.*;

class Solution {
    public List<String> findHighAccessEmployees(List<List<String>> access_times) {
        Map<String, List<Integer>> employeeAccesses = new HashMap<>();
        for (List<String> access : access_times) {
            String name = access.get(0);
            int time = Integer.parseInt(access.get(1));
            employeeAccesses.computeIfAbsent(name, k -> new ArrayList<>()).add(time);
        }

        List<String> highAccessEmployees = new ArrayList<>();
        for (Map.Entry<String, List<Integer>> entry : employeeAccesses.entrySet()) {
            String name = entry.getKey();
            List<Integer> times = entry.getValue();

            if (times.size() < 3) {
                continue;
            }

            // Sort the access times for the employee
            Collections.sort(times);

            // Use a sliding window of size 3 to check for high-access condition
            for (int i = 0; i <= times.size() - 3; i++) {
                // If the difference between the third and first time in the window is less than an hour (100)
                if (times.get(i + 2) - times.get(i) < 100) {
                    highAccessEmployees.add(name);
                    // Found a high-access period, no need to check further for this employee
                    break;
                }
            }
        }

        return highAccessEmployees;
    }
}
```
### Algorithm
- Create a `HashMap<String, List<Integer>>` to store access times for each employee.
- Iterate through the input `access_times`, parse the time string to an integer, and populate the map.
- Create a `List<String>` to store the names of high-access employees.
- For each employee in the map:
    - Get the list of their access times.
    - If the list size is less than 3, skip to the next employee.
    - Sort the list of times in ascending order.
    - Iterate from `i = 0` to `list.size() - 3`.
    - In each iteration, check if `times.get(i + 2) - times.get(i) < 100`.
    - If the condition is true, it means three consecutive accesses in the sorted list fall within an hour. Add the employee's name to the result list and `break` the loop to proceed to the next employee.
- Return the result list.

# Solutions
### Java

```java
class Solution {
public
  List<String> findHighAccessEmployees(List<List<String>> access_times) {
    Map<String, List<Integer>> d = new HashMap<>();
    for (var e : access_times) {
      String name = e.get(0), s = e.get(1);
      int t = Integer.valueOf(s.substring(0, 2)) * 60 +
              Integer.valueOf(s.substring(2));
      d.computeIfAbsent(name, k->new ArrayList<>()).add(t);
    }
    List<String> ans = new ArrayList<>();
    for (var e : d.entrySet()) {
      String name = e.getKey();
      var ts = e.getValue();
      Collections.sort(ts);
      for (int i = 2; i < ts.size(); ++i) {
        if (ts.get(i) - ts.get(i - 2) < 60) {
          ans.add(name);
          break;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> findHighAccessEmployees(vector<vector<string>> &access_times) {
    unordered_map<string, vector<int>> d;
    for (auto &e : access_times) {
      auto name = e[0];
      auto s = e[1];
      int t = stoi(s.substr(0, 2)) * 60 + stoi(s.substr(2, 2));
      d[name].emplace_back(t);
    }
    vector<string> ans;
    for (auto &[name, ts] : d) {
      sort(ts.begin(), ts.end());
      for (int i = 2; i < ts.size(); ++i) {
        if (ts[i] - ts[i - 2] < 60) {
          ans.emplace_back(name);
          break;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def findHighAccessEmployees ( self , access_times : List [ List [ str ]]) -> List [ str ]: d = defaultdict ( list ) for name , t in access_times : d [ name ]. append ( int ( t [: 2 ]) * 60 + int ( t [ 2 :])) ans = [] for name , ts in d . items (): ts . sort () if any ( ts [ i ] - ts [ i - 2 ] < 60 for i in range ( 2 , len ( ts ))): ans . append ( name ) return ans
```