#2432

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

The Employee That Worked on the Longest Task

Identify which employee spent the longest time on a task using an array-driven approach, analyzing each log entry efficiently.

array

Problem Statement

You are given an integer n representing the number of employees, each uniquely identified from 0 to n - 1. You also receive a 2D array logs where each logs[i] = [idi, leaveTimei] represents that employee idi finished a task at time leaveTimei. The first task starts at time 0, and each subsequent task starts immediately after the previous task ends.

Your goal is to find the employee who worked on the single longest task. If multiple employees have tasks with the same longest duration, return the smallest employee ID. Each leaveTimei in logs is strictly increasing, and no employee works on two consecutive tasks.

Examples

Example 1

Input: n = 10, logs = [[0,3],[2,5],[0,9],[1,15]]

Output: 1

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

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

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 <= 500
1 <= logs.length <= 500
logs[i].length == 2
0 <= idi <= n - 1
1 <= leaveTimei <= 500
idi != idi+1
leaveTimei are sorted in a strictly increasing order.

Solution Approach

Iterate through logs to calculate durations

Start with a previous time of 0 and iterate through the logs array. For each task, subtract the previous time from the current leave time to determine the task duration. Update the previous time to the current leave time after each iteration.

Track maximum duration and corresponding employee

Maintain variables to store the longest duration seen so far and the employee ID who worked it. Compare each task's duration to the current maximum, updating both duration and employee ID whenever a longer task is found, or use the smaller ID if durations are equal.

Return the result efficiently

After scanning all logs, the tracked employee ID represents the one with the longest single task. This array-driven solution ensures O(n) time and O(1) additional space without sorting or extra data structures.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m) where m is the number of tasks in logs since we iterate once through the array. Space complexity is O(1) because we only maintain a few variables regardless of input size.

What Interviewers Usually Probe

Expect array-driven calculations without sorting logs again.
Check for tie-breaking using the smallest employee ID for identical durations.
Ensure edge cases handle the first task starting at time 0 correctly.

Common Pitfalls or Variants

Common pitfalls

Forgetting that the first task duration is just leaveTime[0] minus 0.
Not handling ties correctly when multiple employees have the same longest task.
Using previous employee IDs incorrectly instead of comparing task durations properly.

Follow-up variants

Find the employee with the shortest task instead of the longest using the same array approach.
Return all employees tied for the longest task as a list, sorted by ID.
Given logs are unsorted, first sort by leaveTime before applying the same array-driven method.

FAQ

How do I handle the first task when calculating durations?

Use 0 as the previous time to compute the duration of the first task as leaveTime[0] minus 0.

What if multiple employees share the longest task duration?

Return the employee with the smallest ID to resolve ties, as required by the problem.

Does the array need sorting before processing?

No, the logs are strictly increasing by leaveTime, so direct iteration is sufficient.

What is the time complexity for this array-driven solution?

It is O(m), where m is the number of tasks in logs, because each log entry is processed once.

Can GhostInterview explain why the Array-driven solution works for this problem?

Yes, it emphasizes sequentially computing task durations and updating the maximum efficiently using the array pattern.

terminal

Solution

Solution 1: Direct Traversal

We use a variable $last$ to record the end time of the last task, a variable $mx$ to record the longest working time, and a variable $ans$ to record the employee with the longest working time and the smallest $id$. Initially, all three variables are $0$.

1

2

3

4

5

6

7

8

9

class Solution:
    def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
        last = mx = ans = 0
        for uid, t in logs:
            t -= last
            if mx < t or (mx == t and ans > uid):
                ans, mx = uid, t
            last += t
        return ans

Solution 2

#### Rust

1

2

3

4

5

6

7

8

9

class Solution:
    def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
        last = mx = ans = 0
        for uid, t in logs:
            t -= last
            if mx < t or (mx == t and ans > uid):
                ans, mx = uid, t
            last += t
        return ans

Continue Practicing

#2433 find the original array of prefix xor #2435 paths in matrix whose sum is divisible by k #2428 maximum sum of an hourglass