LeetCode 2933 - High-Access Employees

The problem gives us a list of employee access records. Each record contains two strings: - The employee's name - A timestamp in 24-hour "HHMM" format We need to determine which employees accessed the system at least three times within a time window that is strictly less than…

leetcodemediumarrayhash-tablestringsorting

LeetCode Problem 2933

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Sorting

Solution

Problem Understanding

The problem gives us a list of employee access records. Each record contains two strings:

  • The employee's name
  • A timestamp in 24-hour "HHMM" format

We need to determine which employees accessed the system at least three times within a time window that is strictly less than one hour.

The important detail is that exactly 60 minutes apart does not count. For example:

  • 08:15 and 09:14 are within one hour
  • 08:15 and 09:15 are not within one hour

The input guarantees that all access times occur within the same day, so we do not need to worry about wrapping across midnight. This means "2350" and "0005" should never be considered close in time.

The output should contain all employee names that satisfy the condition. The order does not matter.

Because the input size is relatively small, at most 100 access records, many approaches would technically pass. However, the goal is to design a clean and scalable solution that efficiently groups employee records and checks time windows correctly.

A useful way to think about the problem is this:

For each employee individually, can we find three timestamps such that the difference between the earliest and latest timestamp is less than 60 minutes?

If yes, that employee belongs in the result.

Several edge cases are important:

  • An employee may have fewer than three accesses total
  • Accesses may not be given in chronological order
  • Times exactly 60 minutes apart must be rejected
  • Multiple employees may interleave in the input
  • Duplicate timestamps are allowed and should count separately

Approaches

Brute Force Approach

The brute force solution begins by grouping all access times by employee. After that, for every employee, we examine every possible combination of three access times and check whether the maximum and minimum times differ by less than 60 minutes.

To do this correctly, the timestamps should first be converted into minutes since midnight. For example:

  • "0549" becomes 5 * 60 + 49 = 349
  • "1410" becomes 14 * 60 + 10 = 850

For each employee with k timestamps, we could test all triplets:

  • Choose first time
  • Choose second time
  • Choose third time
  • Compute max_time - min_time
  • If the difference is less than 60, mark the employee as high-access

This approach is correct because it explicitly checks every valid group of three accesses. However, it is inefficient because checking all triplets costs O(k^3) time per employee.

Even though the constraints are small enough for this to pass, the algorithm does unnecessary work.

Key Insight for the Optimal Solution

The important observation is that once an employee's timestamps are sorted, we only need to check consecutive groups of three accesses.

Why does this work?

Suppose we have sorted times:

t0 <= t1 <= t2 <= t3 <= ...

If any three accesses fall within one hour, then some consecutive group of three accesses must also fall within one hour.

This means we can simply:

  1. Group times by employee
  2. Convert timestamps to minutes
  3. Sort each employee's times
  4. Slide through the sorted list and check:
times[i + 2] - times[i] < 60

If this condition holds, then the employee qualifies.

This reduces the checking phase from cubic complexity to linear complexity after sorting.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) in worst case O(n) Checks every triplet of accesses
Optimal O(n log n) O(n) Sort timestamps and check consecutive windows

Algorithm Walkthrough

  1. Create a hash map where the key is the employee name and the value is a list of access times.

We use a hash map because we need to efficiently group records belonging to the same employee. 2. Convert each timestamp from "HHMM" format into minutes since midnight.

This simplifies time comparisons. Instead of comparing strings or handling hour and minute logic repeatedly, we work with simple integers.

For example:

"1046" -> 10 * 60 + 46 = 646
  1. Insert each converted timestamp into that employee's list.

After processing the input, each employee will have a collection of numeric timestamps. 4. For every employee, sort their list of timestamps in ascending order.

Sorting allows us to efficiently examine chronological windows. 5. Traverse the sorted timestamps and check every consecutive group of three accesses.

For index i, compare:

times[i + 2] - times[i]

If the difference is strictly less than 60, then those three accesses occurred within one hour. 6. If an employee satisfies the condition once, add their name to the result list.

There is no need to continue checking additional windows for that employee. 7. Return the result list.

Why it works

After sorting the timestamps, any valid set of three accesses within one hour must appear as a consecutive window somewhere in the list. If a non-consecutive group satisfies the condition, then the timestamps between them must also lie inside the same interval, which guarantees the existence of a valid consecutive triple. Therefore, checking only consecutive windows of size three is sufficient and complete.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
        employee_times = defaultdict(list)

        # Group access times by employee
        for employee, time_str in access_times:
            hours = int(time_str[:2])
            minutes = int(time_str[2:])
            total_minutes = hours * 60 + minutes

            employee_times[employee].append(total_minutes)

        result = []

        # Check each employee
        for employee, times in employee_times.items():
            times.sort()

            for i in range(len(times) - 2):
                if times[i + 2] - times[i] < 60:
                    result.append(employee)
                    break

        return result

The implementation starts by using a defaultdict(list) to group timestamps by employee name. This avoids needing to manually initialize lists for new employees.

Each timestamp string is converted into minutes since midnight. This transformation is essential because arithmetic comparisons become straightforward integer subtraction operations.

After grouping, the algorithm iterates through every employee's timestamps and sorts them chronologically.

The critical logic appears in this condition:

if times[i + 2] - times[i] < 60:

This checks whether three consecutive accesses fit inside a strictly smaller-than-60-minute interval.

As soon as one valid window is found, the employee is added to the answer and we stop checking further windows for that employee.

Go Solution

package main

import (
	"sort"
	"strconv"
)

func findHighAccessEmployees(access_times [][]string) []string {
	employeeTimes := make(map[string][]int)

	// Group access times by employee
	for _, entry := range access_times {
		employee := entry[0]
		timeStr := entry[1]

		hours, _ := strconv.Atoi(timeStr[:2])
		minutes, _ := strconv.Atoi(timeStr[2:])

		totalMinutes := hours*60 + minutes

		employeeTimes[employee] = append(employeeTimes[employee], totalMinutes)
	}

	result := []string{}

	// Check each employee
	for employee, times := range employeeTimes {
		sort.Ints(times)

		for i := 0; i+2 < len(times); i++ {
			if times[i+2]-times[i] < 60 {
				result = append(result, employee)
				break
			}
		}
	}

	return result
}

The Go implementation follows the same overall strategy as the Python version.

Instead of defaultdict, Go uses a regular map from string to []int. Appending to a nil slice works automatically in Go, so explicit initialization is unnecessary.

The sort.Ints function sorts each employee's timestamps in ascending order.

Because all time values are small integers, integer overflow is not a concern.

The returned slice may appear in any order, which matches the problem requirements.

Worked Examples

Example 1

Input:
[["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]

Step 1: Convert Times

Employee Original Minutes
a 0549 349
b 0457 297
a 0532 332
a 0621 381
b 0540 340

Step 2: Group by Employee

Employee Times
a [349, 332, 381]
b [297, 340]

Step 3: Sort

Employee Sorted Times
a [332, 349, 381]
b [297, 340]

Step 4: Check Windows

For employee a:

Window Difference
332, 349, 381 381 - 332 = 49

Since 49 < 60, employee a qualifies.

For employee b:

There are fewer than 3 accesses.

Final result:

["a"]

Example 2

Input:
[["d","0002"],["c","0808"],["c","0829"],["e","0215"],
 ["d","1508"],["d","1444"],["d","1410"],["c","0809"]]

After Conversion and Grouping

Employee Times
c [488, 509, 489]
d [2, 908, 884, 850]
e [135]

After Sorting

Employee Sorted
c [488, 489, 509]
d [2, 850, 884, 908]
e [135]

Window Checks

For c:

509 - 488 = 21

Valid.

For d:

First window:

884 - 2 = 882

Invalid.

Second window:

908 - 850 = 58

Valid.

For e:

Only one access.

Final result:

["c", "d"]

Example 3

Input:
[["cd","1025"],["ab","1025"],["cd","1046"],
 ["cd","1055"],["ab","1124"],["ab","1120"]]

After Conversion

Employee Sorted Times
cd [625, 646, 655]
ab [625, 680, 684]

Window Checks

For cd:

655 - 625 = 30

Valid.

For ab:

684 - 625 = 59

Valid.

Final result:

["ab", "cd"]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting employee access times dominates the runtime
Space O(n) Hash map stores all timestamps

The grouping phase processes every record once, which costs O(n) time.

The sorting phase dominates the runtime. In the worst case, all timestamps belong to one employee, producing a sort cost of O(n log n).

The sliding window checks are linear because each employee's list is scanned once after sorting.

The space complexity is O(n) because we store all converted timestamps inside the hash map.

Test Cases

from typing import List

class Solution:
    def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
        from collections import defaultdict

        employee_times = defaultdict(list)

        for employee, time_str in access_times:
            total_minutes = int(time_str[:2]) * 60 + int(time_str[2:])
            employee_times[employee].append(total_minutes)

        result = []

        for employee, times in employee_times.items():
            times.sort()

            for i in range(len(times) - 2):
                if times[i + 2] - times[i] < 60:
                    result.append(employee)
                    break

        return result

sol = Solution()

# Example 1
assert sorted(sol.findHighAccessEmployees([
    ["a","0549"],
    ["b","0457"],
    ["a","0532"],
    ["a","0621"],
    ["b","0540"]
])) == ["a"]  # basic valid case

# Example 2
assert sorted(sol.findHighAccessEmployees([
    ["d","0002"],
    ["c","0808"],
    ["c","0829"],
    ["e","0215"],
    ["d","1508"],
    ["d","1444"],
    ["d","1410"],
    ["c","0809"]
])) == ["c", "d"]  # multiple qualifying employees

# Example 3
assert sorted(sol.findHighAccessEmployees([
    ["cd","1025"],
    ["ab","1025"],
    ["cd","1046"],
    ["cd","1055"],
    ["ab","1124"],
    ["ab","1120"]
])) == ["ab", "cd"]  # boundary under 60 minutes

# Exactly 60 minutes apart should fail
assert sorted(sol.findHighAccessEmployees([
    ["x","0815"],
    ["x","0845"],
    ["x","0915"]
])) == []  # exactly 60 minutes difference

# Fewer than three accesses
assert sorted(sol.findHighAccessEmployees([
    ["y","1000"],
    ["y","1030"]
])) == []  # insufficient accesses

# Duplicate timestamps
assert sorted(sol.findHighAccessEmployees([
    ["z","1200"],
    ["z","1200"],
    ["z","1200"]
])) == ["z"]  # duplicate accesses count separately

# Unsorted input
assert sorted(sol.findHighAccessEmployees([
    ["m","1100"],
    ["m","1000"],
    ["m","1030"]
])) == ["m"]  # sorting required

# Midnight edge case
assert sorted(sol.findHighAccessEmployees([
    ["n","2350"],
    ["n","0005"],
    ["n","0010"]
])) == []  # no cross-day wrapping

# Multiple windows
assert sorted(sol.findHighAccessEmployees([
    ["p","0900"],
    ["p","0910"],
    ["p","0920"],
    ["p","1500"],
    ["p","1510"],
    ["p","1520"]
])) == ["p"]  # multiple valid windows

# Large gap between accesses
assert sorted(sol.findHighAccessEmployees([
    ["q","0100"],
    ["q","0500"],
    ["q","0900"]
])) == []  # accesses too spread out

Test Summary

Test Why
Example 1 Validates basic functionality
Example 2 Verifies multiple employees can qualify
Example 3 Confirms intervals under 60 minutes work
Exactly 60 minutes apart Ensures strict inequality is enforced
Fewer than three accesses Verifies minimum access count requirement
Duplicate timestamps Confirms repeated times are counted
Unsorted input Ensures sorting is correctly implemented
Midnight edge case Prevents accidental cross-day handling
Multiple windows Confirms early detection works
Large gap between accesses Verifies invalid wide intervals

Edge Cases

One important edge case occurs when timestamps are exactly 60 minutes apart. This is easy to implement incorrectly because many developers instinctively use <= 60 instead of < 60. The problem explicitly states that exactly one hour does not count. The implementation handles this correctly with:

times[i + 2] - times[i] < 60

Another critical edge case involves unsorted input. Access records may appear in arbitrary order, even for the same employee. Without sorting, consecutive accesses in the input would not necessarily represent chronological windows. The implementation explicitly sorts every employee's timestamps before checking intervals.

A third important edge case is midnight handling. Since all accesses occur within the same day, timestamps near midnight should not wrap around. For example, "2350" and "0005" are not considered 15 minutes apart. By converting timestamps directly into minutes since midnight and using ordinary subtraction, the implementation naturally prevents cross-day wrapping.

Another subtle edge case is duplicate timestamps. An employee might access the system multiple times at the exact same minute. These should count as separate accesses. Because the algorithm stores every timestamp independently in the list, duplicates are preserved and processed correctly.