Find Total Time Spent by Each Employee

Difficulty: Easy | Acceptance: 86.40% | Paid: No Topics: Database

Table: Employees

+---------------+---------+ | Column Name | Type | +---------------+---------+ | emp_id | int | | event_day | date | | in_time | int | | out_time | int | +---------------+---------+ (emp_id, event_day, in_time) is the primary key of this table. The table shows the employees’ entries and exits in an office. event_day is a day in normal DD-MM-YYYY format. in_time and out_time are the number of minutes since midnight of that day. in_time < out_time.

Write an SQL query to calculate the total time in minutes spent by each employee per day. The total time is calculated as the difference between out_time and in_time.

Return the result table ordered by day and emp_id.

The query result format is in the following example.

• Examples
• Constraints
• Hash Map Aggregation
• Sorting and Grouping

Examples

Example 1

Employees table:
+----------+------------+---------+----------+
| emp_id   | event_day  | in_time | out_time |
+----------+------------+---------+----------+
| 1        | 2020-11-28 | 100     | 400      |
| 1        | 2020-11-28 | 300     | 450      |
| 2        | 2020-11-28 | 10      | 50       |
| 1        | 2020-11-29 | 10      | 50       |
| 2        | 2020-11-29 | 20      | 100      |
+----------+------------+---------+----------+

Result table:
+------------+----------+----------+
| day        | emp_id   | total    |
+------------+----------+----------+
| 2020-11-28 | 1        | 450      |
| 2020-11-28 | 2        | 40       |
| 2020-11-29 | 1        | 40       |
| 2020-11-29 | 2        | 80       |
+------------+----------+----------+
Employee 1 has three entries: two on 2020-11-28 with total time (400-100) + (450-300) = 250 + 150 = 400, and one on 2020-11-29 with total time (50-10) = 40.
Employee 2 has two entries: one on 2020-11-28 with total time (50-10) = 40, and one on 2020-11-29 with total time (100-20) = 80.
Note that the result table is ordered by day and emp_id.

Constraints

The size of the Employees table is between 1 and 1000 rows.
in_time and out_time are between 1 and 1440.

Hash Map Aggregation

Intuition We can iterate through the list of employee records and use a hash map (or dictionary) to accumulate the total time for each unique combination of day and employee ID.

Steps

• Initialize an empty hash map.
• Iterate through each record in the input list.
• Construct a composite key using the event day and employee ID.
• Calculate the duration (out_time - in_time) and add it to the value stored in the hash map for that key.
• After processing all records, convert the map entries into a list of results.
• Sort the result list first by day, then by employee ID.

class Solution:
    def totalTime(self, employees: list[list[int]]) -> list[list[int]]:
        counts = {}
        for emp in employees:
            emp_id, day, in_time, out_time = emp
            # Using a tuple (day, emp_id) as the key
            key = (day, emp_id)
            if key in counts:
                counts[key] += out_time - in_time
            else:
                counts[key] = out_time - in_time
        
        # Convert to list of lists and sort
        result = [[k[0], k[1], v] for k, v in counts.items()]
        result.sort(key=lambda x: (x[0], x[1]))
        return result

Complexity

• Time: O(N log N) due to the sorting step, where N is the number of unique (day, emp_id) pairs.
• Space: O(N) to store the aggregated results in the map.
• Notes: This approach is efficient and straightforward, effectively simulating the SQL GROUP BY operation.

Sorting and Grouping

Intuition If we sort the input list first by day and then by employee ID, all records belonging to the same group will be adjacent. We can then iterate through the sorted list and accumulate the time for the current group until the group changes.

Steps

• Sort the input list by day, then by emp_id.
• Initialize an empty list for results.
• Iterate through the sorted list, keeping track of the current day, emp_id, and accumulated time.
• If the day or emp_id changes, push the previous group’s result to the list and reset the accumulator.
• After the loop, push the final group’s result.

class Solution:
    def totalTime(self, employees: list[list[int]]) -> list[list[int]]:
        if not employees:
            return []
        
        # Sort by day, then by emp_id
        employees.sort(key=lambda x: (x[1], x[0]))
        
        result = []
        curr_day, curr_id = employees[0][1], employees[0][0]
        total = 0
        
        for emp in employees:
            emp_id, day, in_time, out_time = emp
            
            if day != curr_day or emp_id != curr_id:
                result.append([curr_day, curr_id, total])
                curr_day = day
                curr_id = emp_id
                total = 0
            
            total += out_time - in_time
            
        # Append the last group
        result.append([curr_day, curr_id, total])
        return result

Complexity

• Time: O(N log N) due to sorting the input list.
• Space: O(1) auxiliary space (excluding the space for the output and the sort operation which might be O(log N) or O(N) depending on the language’s sorting implementation).
• Notes: This approach avoids using a hash map but requires modifying (or copying) the input to sort it.