Problem Description

You are given a 2D array access_times where each element contains an employee's name and their access time to a system. Each access_times[i] has two parts:

• access_times[i][0]: employee name
• access_times[i][1]: access time in 24-hour format (e.g., "0800", "2250")

All access times are from the same day.

An employee is considered high-access if they accessed the system three or more times within any one-hour period.

Important rules for the one-hour period:

• The one-hour period is strictly less than 60 minutes. For example, accesses at "0815" and "0915" are NOT within the same one-hour period (exactly 60 minutes apart).
• Access times at the start and end of the day don't wrap around. For example, "0005" and "2350" are NOT considered within the same one-hour period.

Your task is to return a list of names of all high-access employees. The order of names in the output doesn't matter.

For example, if an employee has access times at "0810", "0820", and "0830", they would be high-access since all three times fall within a 60-minute window (from 0810 to before 0910). However, if the times were "0810", "0820", and "0910", they would NOT be high-access since the third access is exactly 60 minutes after the first.

Intuition

The key insight is that we need to check if any employee has 3 or more accesses within a sliding window of less than 60 minutes.

First, we need to group all access times by employee name since the same employee might appear multiple times in the input. A hash table (dictionary) is perfect for this grouping.

For time comparisons, working with the string format "HHMM" is cumbersome. Converting each time to minutes since midnight makes calculations much simpler. For example, "0830" becomes 8 * 60 + 30 = 510 minutes. This conversion allows us to easily check if times are within 60 minutes of each other.

Once we have all access times for each employee, we need to find if there are 3 or more accesses within any 60-minute window. A naive approach would be to check every possible window, but there's a clever optimization: after sorting the access times, we only need to check if any 3 consecutive accesses fall within 60 minutes.

Why does checking consecutive accesses work? Because if we have accesses at times t1 < t2 < t3 < t4, and t1, t2, t4 are within 60 minutes, then t1, t2, t3 must also be within 60 minutes (since t3 < t4). So we won't miss any valid windows by only checking consecutive groups of 3.

The condition ts[i] - ts[i-2] < 60 elegantly checks if the current access and the access two positions before are within 60 minutes. If true, then these three consecutive accesses (ts[i-2], ts[i-1], ts[i]) form a high-access pattern.

Learn more about Sorting patterns.

Solution Approach

The implementation follows these steps:

1. Create a hash table to group access times by employee: We use a defaultdict(list) where the key is the employee name and the value is a list to store all their access times.

2. Convert time strings to minutes: For each access record [name, time], we parse the time string and convert it to minutes since midnight:

   • Extract hours: int(t[:2]) gets the first two characters as hours
   • Extract minutes: int(t[2:]) gets the last two characters as minutes
   • Total minutes: hours * 60 + minutes

   This conversion is stored in the hash table: d[name].append(int(t[:2]) * 60 + int(t[2:]))

3. Process each employee's access times: Iterate through the hash table entries:

   • Sort each employee's access times in ascending order using ts.sort()
   • This sorting is crucial as it allows us to check only consecutive groups of 3 accesses

4. Check for high-access pattern: For each employee's sorted times, we check if any three consecutive accesses are within 60 minutes:

   • Start from index 2 (since we need to look back 2 positions)
   • Check condition: ts[i] - ts[i-2] < 60
   • If the difference between the current time and the time two positions back is less than 60, then these three consecutive times (ts[i-2], ts[i-1], ts[i]) form a high-access window
   • Use any() function to check if at least one such window exists

5. Build the result: If an employee has at least one high-access window, add their name to the answer list.

The time complexity is O(n log n) for each employee due to sorting, where n is the number of accesses per employee. The space complexity is O(n) to store all access times.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input: access_times = [["Alice","0845"], ["Alice","0910"], ["Alice","0920"], ["Bob","1000"], ["Bob","1040"], ["Bob","1050"]]

Step 1: Group access times by employee We create a hash table to store each employee's access times:

• Initialize empty dictionary d
• Process each entry:
  • ["Alice","0845"] → d["Alice"] = [525] (where 525 = 8×60 + 45)
  • ["Alice","0910"] → d["Alice"] = [525, 550] (where 550 = 9×60 + 10)
  • ["Alice","0920"] → d["Alice"] = [525, 550, 560] (where 560 = 9×60 + 20)
  • ["Bob","1000"] → d["Bob"] = [600] (where 600 = 10×60 + 0)
  • ["Bob","1040"] → d["Bob"] = [600, 640] (where 640 = 10×60 + 40)
  • ["Bob","1050"] → d["Bob"] = [600, 640, 650] (where 650 = 10×60 + 50)

Step 2: Check each employee for high-access pattern

For Alice:

• Times in minutes: [525, 550, 560] (already sorted)
• Check windows of 3 consecutive accesses:
  • At index 2: Check if 560 - 525 < 60
  • 560 - 525 = 35 < 60 ✓
  • This means times at 0845, 0910, and 0920 are all within 60 minutes
• Alice is a high-access employee

For Bob:

• Times in minutes: [600, 640, 650] (already sorted)
• Check windows of 3 consecutive accesses:
  • At index 2: Check if 650 - 600 < 60
  • 650 - 600 = 50 < 60 ✓
  • This means times at 1000, 1040, and 1050 are all within 60 minutes
• Bob is a high-access employee

Step 3: Return result Both Alice and Bob are high-access employees.

Output: ["Alice", "Bob"]

The key insight here is that by converting times to minutes and sorting them, we only need to check if the first and third accesses in any consecutive group of three are less than 60 minutes apart. This efficiently identifies all employees who accessed the system three or more times within any one-hour window.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm consists of the following steps:

1. Iterating through all access records to build the dictionary: O(n), where n is the total number of access records
2. For each employee, sorting their access times: Let's say there are k unique employees, and each employee has on average n/k access times. The sorting for each employee takes O((n/k) × log(n/k)). For all employees combined: O(k × (n/k) × log(n/k)) = O(n × log(n/k))
3. Checking consecutive access times for each employee: O(n) in total across all employees

In the worst case, when one employee has all n access records, the sorting step becomes O(n × log n), which dominates the overall time complexity.

Space Complexity: O(n)

The space is used for:

1. The dictionary d which stores all access times for each employee: O(n) space to store n access records
2. The answer list ans: O(k) space where k is the number of unique employees, and k ≤ n
3. The sorted lists are created in-place using the existing storage in the dictionary

Therefore, the total space complexity is O(n).

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

Common Pitfalls

1. Misunderstanding the "within one hour" requirement

Pitfall: Many developers incorrectly interpret "within one hour" as including exactly 60 minutes. For instance, they might consider accesses at "0815" and "0915" as being within the same one-hour period.

Why it happens: The natural inclination is to use <= when checking time differences, thinking that 60 minutes equals one hour.

Incorrect implementation:

# WRONG: This includes exactly 60 minutes
if time_list[i] - time_list[i - 2] <= 60:  # Bug: should be < 60
    high_access_employees.append(name)

Correct approach: Use strict inequality (< 60) since the problem specifies "strictly less than 60 minutes":

# CORRECT: Strictly less than 60 minutes
if time_list[i] - time_list[i - 2] < 60:
    high_access_employees.append(name)

2. Not handling duplicate names in the result

Pitfall: If an employee has multiple high-access windows, they might be added to the result list multiple times without the break statement.

Example scenario: An employee with times ["0800", "0810", "0820", "0830", "0840"] has multiple overlapping windows where 3 accesses occur within 60 minutes.

Incorrect implementation:

for i in range(2, len(time_list)):
    if time_list[i] - time_list[i - 2] < 60:
        high_access_employees.append(name)
        # Missing break - employee could be added multiple times

Correct approach: Add a break statement once a high-access pattern is found:

for i in range(2, len(time_list)):
    if time_list[i] - time_list[i - 2] < 60:
        high_access_employees.append(name)
        break  # Prevent duplicate entries

3. Forgetting to sort the access times

Pitfall: Processing access times in the order they appear in the input without sorting can miss valid high-access patterns.

Example: If input is [["Alice", "0830"], ["Alice", "0810"], ["Alice", "0820"]], checking consecutive pairs without sorting would fail to detect the high-access pattern.

Solution: Always sort each employee's access times before checking for patterns:

time_list.sort()  # Critical step - don't skip this!

4. Incorrect time string parsing

Pitfall: Assuming time format or using incorrect string slicing indices.

Common mistakes:

# WRONG: Incorrect slicing
hours = int(time_str[0:2])    # Works but inconsistent
minutes = int(time_str[2:4])   # Should use [2:] for clarity

# WRONG: Not handling potential edge cases
hours = int(time_str.split(':')[0])  # Assumes colon separator

Correct approach: Use consistent and clear slicing:

hours = int(time_str[:2])    # First two characters
minutes = int(time_str[2:])   # Last two characters