Watch 10 video solutions for The Employee That Worked on the Longest Task, a easy level problem involving Array. This walkthrough by Gopala Krishna Reddy Maguluri has 593 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n employees, each with a unique id from 0 to n - 1.
You are given a 2D integer array logs where logs[i] = [idi, leaveTimei] where:
idi is the id of the employee that worked on the ith task, andleaveTimei is the time at which the employee finished the ith task. All the values leaveTimei are unique.Note that the ith task starts the moment right after the (i - 1)th task ends, and the 0th task starts at time 0.
Return the id of the employee that worked the task with the longest time. If there is a tie between two or more employees, return the smallest id among them.
Example 1:
Input: n = 10, logs = [[0,3],[2,5],[0,9],[1,15]] Output: 1 Explanation: Task 0 started at 0 and ended at 3 with 3 units of times. Task 1 started at 3 and ended at 5 with 2 units of times. Task 2 started at 5 and ended at 9 with 4 units of times. Task 3 started at 9 and ended at 15 with 6 units of times. The task with the longest time is task 3 and the employee with id 1 is the one that worked on it, so we return 1.
Example 2:
Input: n = 26, logs = [[1,1],[3,7],[2,12],[7,17]] Output: 3 Explanation: Task 0 started at 0 and ended at 1 with 1 unit of times. Task 1 started at 1 and ended at 7 with 6 units of times. Task 2 started at 7 and ended at 12 with 5 units of times. Task 3 started at 12 and ended at 17 with 5 units of times. The tasks with the longest time is task 1. The employee that worked on it is 3, so we return 3.
Example 3:
Input: n = 2, logs = [[0,10],[1,20]] Output: 0 Explanation: Task 0 started at 0 and ended at 10 with 10 units of times. Task 1 started at 10 and ended at 20 with 10 units of times. The tasks with the longest time are tasks 0 and 1. The employees that worked on them are 0 and 1, so we return the smallest id 0.
Constraints:
2 <= n <= 5001 <= logs.length <= 500logs[i].length == 20 <= idi <= n - 11 <= leaveTimei <= 500idi != idi+1leaveTimei are sorted in a strictly increasing order.Problem Overview: You receive a list of logs where logs[i] = [employeeId, leaveTime]. Tasks are executed sequentially, and each employee works on exactly one task at a time. The duration of a task is the difference between the current leaveTime and the previous task's finish time. Your goal is to find the employee who worked on the longest single task. If multiple employees have the same longest duration, return the smallest employee ID.
The logs are already sorted by completion time. That means you can process them in order and compute each task's duration using the difference between consecutive timestamps. The problem mainly tests careful array traversal and comparison logic using basic operations on a array.
Approach 1: Iterative Comparison Approach (O(n) time, O(1) space)
Traverse the log array once while tracking the previous task's finish time. For each log entry, compute the task duration using duration = leaveTime - previousLeave. Maintain two variables: the maximum duration seen so far and the employee ID associated with that duration. When a new duration exceeds the current maximum, update both values. If the duration ties with the maximum, choose the smaller employee ID. Since the logs are processed sequentially, a single pass is enough. This approach uses constant extra memory and relies purely on comparisons and arithmetic.
This technique is essentially a simple simulation of the execution timeline. Because each duration depends only on the previous timestamp, you don't need additional structures beyond a few variables. Many interview problems involving sequential events follow this exact pattern of "compute difference and track best".
Approach 2: Prefix Sum Optimization (O(n) time, O(n) space)
Another way to structure the logic is to explicitly store task durations using a prefix-difference idea. First iterate through the logs and compute an auxiliary array where duration[i] = logs[i][1] - logs[i-1][1] (with the first duration being logs[0][1]). Once durations are precomputed, perform a second pass to find the maximum duration and apply the same tie-breaking rule for employee IDs. This approach separates duration calculation from comparison logic, which can make debugging easier in some cases.
The method borrows the idea behind prefix sum transformations: convert cumulative timestamps into per-task durations so each entry becomes independent. However, the extra array means additional O(n) space, which is unnecessary for this problem.
Recommended for interviews: The iterative comparison approach is the expected solution. It runs in O(n) time with O(1) space and demonstrates that you understand how to derive task durations from sequential timestamps. Showing the brute reasoning (difference between consecutive times) first and then implementing the single-pass comparison proves strong fundamentals in array traversal and event timeline problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Comparison Approach | O(n) | O(1) | Best general solution. Single pass over the logs with constant memory. |
| Prefix Sum Optimization | O(n) | O(n) | Useful when you want explicit duration storage or easier debugging of intermediate values. |