LeetCode 2394 - Employees With Deductions

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to identify employees whose monthly working time is less than the required number of hours. Each employee has a minimum number of hours they must work during October 2022 to avoid salary deductions. Employees can work in multiple sessions, and the total worked time is calculated by summing the duration of all sessions.

The tricky part is that each work session is measured in minutes, and the duration of every session must be rounded up to the nearest whole minute before summing. This means even a single extra second counts as a full additional minute.

For example:

A session lasting exactly 60 minutes contributes 60 minutes.
A session lasting 60 minutes and 1 second contributes 61 minutes.

We are given two database tables:

The Employees table stores each employee’s unique identifier and the minimum number of hours they are required to work.

The Logs table contains working sessions, where each row records when an employee started (in_time) and stopped (out_time) working. Sessions may cross midnight, meaning out_time can occur on the next day.

The goal is to return the IDs of employees whose total rounded working time is strictly less than their required hours.

An employee who never appears in the Logs table must still be considered, since their total work time is effectively zero.

Since this is a database problem, the real task is to write an SQL query that efficiently aggregates work durations, converts them into minutes, rounds correctly, and compares against required hours.

Important Observations

The required hours are stored in hours, but logs are naturally measured in seconds or minutes. To compare correctly, we should convert required hours into minutes by multiplying by 60.

Each work session must be rounded individually. This is important because rounding after summing would produce incorrect results.

For example:

Session A = 59 minutes 30 seconds → 60 minutes
Session B = 59 minutes 30 seconds → 60 minutes

Correct total = 120 minutes

If we summed first:

119 minutes → 119 minutes

This would incorrectly undercount time.

Employees with no logs are another important edge case. Since they never worked, their total should be treated as 0, meaning they should be deducted unless needed_hours = 0.

Because out_time may be the next day, we must compute actual timestamp differences rather than assuming sessions always stay within a single calendar day.

Approaches

Brute Force Approach

A brute force approach would iterate through every employee and, for each employee, scan the entire Logs table to find matching sessions. For every session, we would calculate its duration in seconds, round up to minutes, sum everything, and finally compare against the required hours.

This approach is straightforward and easy to reason about because it directly mirrors the problem statement. For each employee, we independently compute their total working time.

However, this becomes inefficient because for every employee we repeatedly scan the entire logs dataset. If there are E employees and L log records, the complexity becomes O(E × L).

In a database setting, repeatedly rescanning large tables is expensive and unnecessary.

Optimal Approach

The key insight is that we should aggregate log durations once per employee, rather than repeatedly recalculating them.

We can group logs by employee_id, compute each session’s rounded duration, sum those values for every employee, and then join the result with the Employees table.

This works efficiently because aggregation naturally fits SQL operations:

Compute session duration in minutes using timestamp difference.
Apply ceiling rounding to each session.
Group by employee and sum total minutes.
Left join with Employees so employees without logs are included.
Compare total worked minutes against needed_hours × 60.

A LEFT JOIN is essential because employees with no logs would otherwise disappear from the result.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(E × L)	O(1)	Rescans all logs for every employee
Optimal	O(E + L)	O(E)	Aggregate logs once and compare totals

Algorithm Walkthrough

Start with the Logs table and calculate the duration of every work session.

For each session, compute the difference between out_time and in_time in seconds. Since durations must be rounded up to the nearest minute, divide by 60 and apply a ceiling operation. 2. Group sessions by employee.

After calculating rounded minutes for each session, sum all session durations for the same employee. This gives the employee’s total worked minutes. 3. Join aggregated results with the Employees table.

Use a LEFT JOIN so every employee appears in the final dataset, even if they have no logs. 4. Replace missing totals with zero.

Employees without sessions will have NULL for worked minutes. Convert this value to 0 using COALESCE. 5. Compare worked time against required time.

Convert needed_hours into minutes by multiplying by 60.

If:

worked_minutes < needed_hours × 60

then the employee should be deducted. 6. Return only employee IDs.

The output requires only the employee_id column.

Why it works

The algorithm works because every session is rounded independently before aggregation, which exactly matches the problem definition. Grouping by employee ensures all work sessions contribute to the correct total. Using a LEFT JOIN guarantees employees with no sessions are still evaluated, and comparing total worked minutes against required minutes correctly identifies employees who failed to meet their target.

SQL Solution

SELECT e.employee_id
FROM Employees e
LEFT JOIN (
    SELECT
        employee_id,
        SUM(CEILING(TIMESTAMPDIFF(SECOND, in_time, out_time) / 60.0)) AS total_minutes
    FROM Logs
    GROUP BY employee_id
) l
ON e.employee_id = l.employee_id
WHERE COALESCE(l.total_minutes, 0) < e.needed_hours * 60;

Implementation Explanation

The subquery processes the Logs table first. For every log entry, it computes the duration in seconds using TIMESTAMPDIFF(SECOND, in_time, out_time).

The division by 60.0 converts seconds into fractional minutes, and CEILING() ensures every session is rounded up individually.

After computing session durations, the query groups by employee_id and sums all rounded minutes.

The result is then LEFT JOINed with the Employees table. This step is important because employees who never worked would otherwise not appear.

COALESCE(l.total_minutes, 0) converts missing totals into zero minutes.

Finally, the WHERE clause filters employees whose worked minutes are less than the required threshold in minutes.

Worked Examples

Example 1

Input

Employees

employee_id	needed_hours
1	20
2	12
3	2

Logs

employee_id	in_time	out_time
1	2022-10-01 09:00:00	2022-10-01 17:00:00
1	2022-10-06 09:05:04	2022-10-06 17:09:03
1	2022-10-12 23:00:00	2022-10-13 03:00:01
2	2022-10-29 12:00:00	2022-10-29 23:58:58

Step 1: Compute Rounded Session Minutes

Employee	Session Duration	Rounded Minutes
1	8h 0m 0s	480
1	8h 3m 59s	484
1	4h 0m 1s	241
2	11h 58m 58s	719

Step 2: Aggregate Totals

Employee	Total Minutes
1	1205
2	719
3	0

Step 3: Compare Against Required Minutes

Employee	Required Minutes	Worked Minutes	Deducted?
1	1200	1205	No
2	720	719	Yes
3	120	0	Yes

Final result:

employee_id
2
3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(E + L)	Each employee and log row is processed once
Space	O(E)	Aggregated employee totals are stored

The dominant cost comes from scanning the Logs table and grouping by employee. The Employees table is scanned once during the join. Since aggregation is done a single time rather than repeatedly, the solution scales efficiently for large datasets.

Test Cases

-- Example 1
Employees:
(1, 20)
(2, 12)
(3, 2)

Logs:
(1, '2022-10-01 09:00:00', '2022-10-01 17:00:00')
(1, '2022-10-06 09:05:04', '2022-10-06 17:09:03')
(1, '2022-10-12 23:00:00', '2022-10-13 03:00:01')
(2, '2022-10-29 12:00:00', '2022-10-29 23:58:58')

Expected:
(2)
(3)

-- Employee exactly meets required hours
Employees:
(1, 8)

Logs:
(1, '2022-10-01 09:00:00', '2022-10-01 17:00:00')

Expected:
(empty result)

-- Employee slightly below due to rounding
Employees:
(1, 1)

Logs:
(1, '2022-10-01 09:00:00', '2022-10-01 09:59:59')

Expected:
(empty result)

-- Employee with no logs
Employees:
(1, 5)

Logs:
(empty)

Expected:
(1)

-- Multiple short sessions needing per-session rounding
Employees:
(1, 2)

Logs:
(1, '2022-10-01 09:00:00', '2022-10-01 09:00:01')
(1, '2022-10-01 10:00:00', '2022-10-01 10:00:01')

Expected:
(1)

Test	Why
Problem example	Validates the main scenario
Exact threshold	Ensures equality does not trigger deduction
Rounding edge	Verifies ceiling behavior
No logs	Confirms `LEFT JOIN` correctness
Multiple short sessions	Ensures per-session rounding is applied

Edge Cases

Employees With No Logs

An employee may never appear in the Logs table. A naive inner join would exclude them entirely, causing incorrect results. This implementation uses a LEFT JOIN and converts missing totals to 0 using COALESCE, ensuring such employees are correctly deducted.

Sessions Crossing Midnight

A work session may start on one day and end after midnight on the next day. A naive implementation that compares only hours or dates could fail. Using TIMESTAMPDIFF(SECOND, in_time, out_time) guarantees the actual elapsed time is measured correctly.

Per Session Rounding

A subtle but important requirement is that every session must be rounded independently. Rounding only after summing all durations produces incorrect totals. The implementation applies CEILING() to each session before aggregation, exactly matching the problem statement.

Exact Threshold Matching

Employees should only be deducted if they worked less than the required amount. If an employee worked exactly the required time, they should not appear in the result. The implementation correctly uses the < comparison operator instead of <=.