High-Access Employees
MedPrompt
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 <= 100access_times[i].length == 21 <= access_times[i][0].length <= 10access_times[i][0]consists only of English small letters.access_times[i][1].length == 4access_times[i][1]is in 24-hour time format.access_times[i][1]consists only of'0'to'9'.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
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.
Walkthrough
The core idea is to systematically check all possibilities.
- Group by Employee: We start by iterating through the
access_timeslist. We use aHashMapwhere 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). - 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.
- 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 ifmax_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. - 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.
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); }}Complexity
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.
Trade-offs
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.
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.
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 = 0tolist.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
breakthe loop to proceed to the next employee.
- Return the result list.
Walkthrough
This optimized approach leverages sorting to avoid the costly combination checks.
- Group by Employee: Same as the first approach, we use a
HashMapto group access times by employee, converting time strings to integers. - 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.
- 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]). - 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 iftimes[i+2] - times[i] < 100. If this condition holds, we have found three accesses within a one-hour period. - 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.
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; }}Complexity
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.
Trade-offs
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 Kfactor to the complexity, but this is a minor drawback compared to the significant performance gain over the brute-force method.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.