Problem Description

You are given a list of logs, where each log entry is represented as a pair [employee_id, time_spent]. Each entry indicates that the employee with ID employee_id has spent time_spent minutes working on a certain task. Your task is to compute the total time spent by each employee, and return the result as a list of pairs [employee_id, total_time], sorted by employee_id in increasing order.

• Each employee_id is unique per employee, but may appear multiple times in the logs.
• You must aggregate the time for each employee across all their log entries.
• The input is typically given as a list of lists or a 2D array.
• Return a list of [employee_id, total_time] pairs, sorted by employee_id.

Thought Process

The core of the problem is to group all the time entries by employee and sum their times. A naive approach would be to iterate through the logs for each employee, but that would be inefficient. Instead, we recognize this as a classic "group by and sum" problem, which is best solved using a hash map (dictionary) for quick lookups and aggregation.

The process involves:

• Reading each log entry and adding its time_spent to the running total for that employee_id.
• After processing all logs, collecting the results and sorting by employee_id.

Solution Approach

Let's break down the solution step-by-step:

1. Initialize a Hash Map:
   • Create an empty hash map (dictionary) where the keys are employee_id and the values are the total time spent.
2. Aggregate Time Spent:
   • Iterate through each log entry.
   • For each entry, if the employee_id is not in the hash map, initialize it to 0.
   • Add the time_spent to the corresponding employee_id in the hash map.
3. Prepare the Output:
   • Convert the hash map into a list of [employee_id, total_time] pairs.
   • Sort this list by employee_id in increasing order.
4. Return the Result:
   • Return the sorted list as the final answer.

This method uses a hash map for efficient grouping and summing, and a simple sort for the final output.

Example Walkthrough

Let's walk through an example. Suppose the input logs are:

    logs = [
      [1, 60],
      [2, 30],
      [2, 20],
      [1, 15],
      [3, 45]
    ]
  

Step-by-step process:

• Start with an empty hash map: {}
• Process [1, 60]: Add 60 to employee 1 → {1: 60}
• Process [2, 30]: Add 30 to employee 2 → {1: 60, 2: 30}
• Process [2, 20]: Add 20 to employee 2 → {1: 60, 2: 50}
• Process [1, 15]: Add 15 to employee 1 → {1: 75, 2: 50}
• Process [3, 45]: Add 45 to employee 3 → {1: 75, 2: 50, 3: 45}

Convert the hash map to a list and sort by employee_id: [[1, 75], [2, 50], [3, 45]]

Time and Space Complexity

Brute-force approach:

• For each unique employee, scan the entire logs list to sum times: O(n * m), where n is number of employees and m is number of logs.

• We process each log entry once: O(m)
• Building the output list is O(n) (n = number of unique employees)
• Sorting the output is O(n log n)
• Space: O(n) for the hash map

Overall complexity: O(m + n log n) time, O(n) space.

Summary

We solved the problem by grouping log entries by employee using a hash map to efficiently accumulate total time per employee. After aggregation, we sorted the results by employee ID. This approach is both simple and efficient, leveraging hash maps for O(1) updates and a final sort for ordered output. The solution is elegant because it cleanly separates aggregation from sorting, and scales well with large input sizes.

Code Implementation

def findTotalTime(logs):
    total_time = {}
    for emp_id, time in logs:
        if emp_id not in total_time:
            total_time[emp_id] = 0
        total_time[emp_id] += time
    return [[emp_id, total_time[emp_id]] for emp_id in sorted(total_time.keys())]
      

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<vector<int>> findTotalTime(vector<vector<int>>& logs) {
    unordered_map<int, int> total_time;
    for (const auto& log : logs) {
        int emp_id = log[0];
        int time = log[1];
        total_time[emp_id] += time;
    }
    vector<vector<int>> result;
    for (const auto& entry : total_time) {
        result.push_back({entry.first, entry.second});
    }
    sort(result.begin(), result.end());
    return result;
}
      

import java.util.*;

public class Solution {
    public List<List<Integer>> findTotalTime(int[][] logs) {
        Map<Integer, Integer> totalTime = new HashMap<>();
        for (int[] log : logs) {
            int empId = log[0];
            int time = log[1];
            totalTime.put(empId, totalTime.getOrDefault(empId, 0) + time);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int empId : totalTime.keySet()) {
            result.add(Arrays.asList(empId, totalTime.get(empId)));
        }
        result.sort(Comparator.comparingInt(a -> a.get(0)));
        return result;
    }
}
      

function findTotalTime(logs) {
    const totalTime = {};
    for (const [empId, time] of logs) {
        if (!(empId in totalTime)) {
            totalTime[empId] = 0;
        }
        totalTime[empId] += time;
    }
    const result = [];
    for (const empId in totalTime) {
        result.push([parseInt(empId), totalTime[empId]]);
    }
    result.sort((a, b) => a[0] - b[0]);
    return result;
}