LeetCode 1741 - Find Total Time Spent by Each Employee

The problem asks us to calculate the total time each employee spends in the office per day based on a table of their in and out times.

leetcodeeasydatabase

LeetCode Problem 1741

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem asks us to calculate the total time each employee spends in the office per day based on a table of their in and out times. Each row in the Employees table represents a single period that an employee was in the office, with columns for emp_id, event_day, in_time, and out_time. The in_time and out_time are in minutes, and in_time < out_time is guaranteed. The same employee can have multiple entries on the same day, meaning we need to sum all their time intervals for that day.

The expected output is a table with three columns: day, emp_id, and total_time, where total_time is the sum of all out_time - in_time intervals for that employee on that day. The order of rows does not matter.

Important observations and constraints are:

  1. Each entry is guaranteed to have in_time < out_time.
  2. Entries for the same employee on the same day do not overlap.
  3. The primary key ensures uniqueness for (emp_id, event_day, in_time).
  4. We can safely sum intervals without worrying about overlaps.

Edge cases that could trip up a naive implementation include employees with multiple entries on the same day, days with only one entry, or employees who appear on only one day. Empty tables should return an empty result.

Approaches

A brute-force approach would be to iterate through all entries for each employee, group them by emp_id and event_day, then sum the intervals manually. While this works correctly, in SQL it can be done more efficiently using aggregation functions rather than nested loops.

The key observation for an optimal solution is that SQL supports GROUP BY and arithmetic operations directly. By grouping entries by emp_id and event_day, we can calculate the total time per employee per day using SUM(out_time - in_time).

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Iterate manually for each employee-day, summing times
Optimal O(n) O(n) Use SQL aggregation with GROUP BY and SUM

Algorithm Walkthrough

  1. Select the relevant columns event_day and emp_id to group by.
  2. For each group, calculate the total time spent using SUM(out_time - in_time). This automatically handles multiple entries per day.
  3. Alias the sum as total_time to match the expected output column.
  4. Return the result. SQL does not require explicit sorting unless specified, so ordering can be arbitrary.

Why it works: Grouping by emp_id and event_day ensures that all intervals for the same employee on the same day are aggregated together. Summing the differences out_time - in_time correctly computes the total minutes spent in the office per day because intervals do not overlap.

Python Solution

import sqlite3
from typing import List, Tuple

def total_time_per_employee(conn: sqlite3.Connection) -> List[Tuple[str, int, int]]:
    """
    Calculates total time spent by each employee per day.

    Args:
    conn (sqlite3.Connection): Connection to the SQLite database containing Employees table.

    Returns:
    List[Tuple[str, int, int]]: List of tuples (day, emp_id, total_time)
    """
    query = """
    SELECT event_day AS day, emp_id, SUM(out_time - in_time) AS total_time
    FROM Employees
    GROUP BY event_day, emp_id
    """
    cursor = conn.cursor()
    cursor.execute(query)
    result = cursor.fetchall()
    return result

In this Python implementation, we use a standard SQLite connection. We execute an SQL query that groups the entries by event_day and emp_id, computing the sum of out_time - in_time for each group. The result is returned as a list of tuples.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "log"
)

type EmployeeTime struct {
    Day       string
    EmpID     int
    TotalTime int
}

func TotalTimePerEmployee(db *sql.DB) ([]EmployeeTime, error) {
    query := `
    SELECT event_day AS day, emp_id, SUM(out_time - in_time) AS total_time
    FROM Employees
    GROUP BY event_day, emp_id
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results []EmployeeTime
    for rows.Next() {
        var et EmployeeTime
        if err := rows.Scan(&et.Day, &et.EmpID, &et.TotalTime); err != nil {
            return nil, err
        }
        results = append(results, et)
    }
    return results, nil
}

In Go, we execute the same SQL query, scan the results into a struct, and append them to a slice. Care is taken to handle potential errors from the database query and row scanning.

Worked Examples

For the example:

+--------+------------+---------+----------+
| emp_id | event_day  | in_time | out_time |
+--------+------------+---------+----------+
| 1      | 2020-11-28 | 4       | 32       |
| 1      | 2020-11-28 | 55      | 200      |
| 1      | 2020-12-03 | 1       | 42       |
| 2      | 2020-11-28 | 3       | 33       |
| 2      | 2020-12-09 | 47      | 74       |
+--------+------------+---------+----------+

After grouping by event_day and emp_id:

day emp_id intervals
2020-11-28 1 (32-4), (200-55)
2020-12-03 1 (42-1)
2020-11-28 2 (33-3)
2020-12-09 2 (74-47)

Summing the intervals:

day emp_id total_time
2020-11-28 1 28 + 145 = 173
2020-12-03 1 41
2020-11-28 2 30
2020-12-09 2 27

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed once to compute the sum
Space O(n) Space for the result set storing one entry per employee-day

The SQL GROUP BY aggregates in linear time with respect to the number of table rows, and the result set size depends on the number of unique (emp_id, event_day) combinations.

Test Cases

# test cases
assert total_time_per_employee(sqlite3.connect(":memory:")) == []  # Empty table

# Basic example from the problem
# Populate SQLite table first for a complete test
conn = sqlite3.connect(":memory:")
conn.execute("""
CREATE TABLE Employees(
    emp_id INT,
    event_day DATE,
    in_time INT,
    out_time INT
)
""")
conn.executemany("INSERT INTO Employees VALUES (?, ?, ?, ?)", [
    (1, "2020-11-28", 4, 32),
    (1, "2020-11-28", 55, 200),
    (1, "2020-12-03", 1, 42),
    (2, "2020-11-28", 3, 33),
    (2, "2020-12-09", 47, 74)
])
result = total_time_per_employee(conn)
expected = [
    ("2020-11-28", 1, 173),
    ("2020-11-28", 2, 30),
    ("2020-12-03", 1, 41),
    ("2020-12-09", 2, 27)
]
assert sorted(result) == sorted(expected)  # Order can vary
Test Why
Empty table Handles no data gracefully
Multiple entries per day Checks correct summation of intervals
Single entry Verifies simple case works
Multiple employees Ensures grouping by employee works

Edge Cases

One edge case is an employee with only a single entry for the day. The implementation handles this correctly because summing a single interval still produces the correct total.

Another edge case is an employee with multiple non-overlapping entries on the same day. Since the problem guarantees no overlaps, summing all out_time - in_time intervals produces the exact total without any additional logic.

Finally, an empty Employees table should return an empty result. The SQL aggregation handles this naturally, as GROUP BY on an empty table produces no rows. This avoids runtime errors or null handling issues.