LeetCode Solutions Blog

High-Access Employees

Number: 3202

Difficulty: Medium

Paid? No

Problem Description

Given a list of employee access records with employee names and times (in HHMM format), determine which employees accessed the system at least three times within any one-hour period (where one-hour is defined as any period strictly less than 60 minutes apart).

Key Insights

Group the access times by employee name.
Convert the access times from string (HHMM) to a numeric value (minutes since midnight) for easier arithmetic comparisons.
Sort each employee's list of access times.
For each sorted list, use a sliding window technique to check any contiguous segment where the difference between the earliest and the latest time in the window is less than 60 minutes and the count is at least three.
Return the list of employees that meet the high-access condition.

Space and Time Complexity

Time Complexity: O(n log n) where n is the number of access records, due to the sorting step for each employee. Space Complexity: O(n) for storing access time data grouped by employee.

Solution

We first group the access times by employee using a hash table (or dictionary). For each employee, we convert the given HHMM string into minutes since midnight to simplify time difference computations. Next, we sort these time values. Then, using a sliding window approach, we iterate through the sorted list. For each window, we check if the difference between the current time and the time at the beginning of the window is strictly less than 60 minutes. If we find a window containing three or more entries, we mark that employee as high-access. Finally, we return the list of such employees.

Code Solutions

# Python solution for the High-Access Employees problem

def high_access_employees(access_times):
    # Helper function to convert HHMM string to minutes since midnight
    def time_to_minutes(time_str):
        hours = int(time_str[:2])
        minutes = int(time_str[2:])
        return hours * 60 + minutes
        
    # Dictionary to store employee names and their corresponding access times in minutes
    employee_times = {}
    # Group access times by employee
    for record in access_times:
        name, time_str = record[0], record[1]
        minutes = time_to_minutes(time_str)
        if name not in employee_times:
            employee_times[name] = []
        employee_times[name].append(minutes)
    
    # List to hold the result - employees with high-access occurrence
    result = []
    # Checking for each employee if there exists a one-hour window with 3 or more access times
    for name, times in employee_times.items():
        # Sort the times for sliding window approach
        times.sort()
        i = 0  # start of the sliding window
        # Iterate over each time as the end of the window
        for j in range(len(times)):
            # Move the start pointer so that the difference is less than 60 minutes
            while times[j] - times[i] >= 60:
                i += 1
            # If the window size is at least 3, mark the employee as high-access
            if j - i + 1 >= 3:
                result.append(name)
                break  # No need to check further for this employee
    return result

# Example usage:
print(high_access_employees([["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]))