Problem Description

You are given a list of employees in a company. Each employee has a unique id and a managerId indicating the employee they report to. The company's structure forms a tree (no cycles, one root). Your task is to compute, for every employee, the total number of employees that report to them directly or indirectly (i.e., in their subtree), excluding themselves.

• Each employee appears once in the input.
• There is exactly one root (an employee with managerId = -1).
• All id and managerId values are integers.
• The result should be a mapping from id to the number of reports for each employee.

Constraints: The tree is valid and connected. All IDs are unique. There is one valid solution.

Thought Process

The core of this problem is to count, for each employee, how many employees are in their management chain beneath them (excluding themselves). At first glance, you might consider, for each employee, traversing the entire tree to find all their reports. However, this approach would be inefficient, especially for large trees, since it would repeat work for overlapping subtrees.

Instead, we can recognize that the company structure is a tree, and for each employee, their total reports is the sum of the reports of their direct subordinates, plus the number of direct subordinates themselves. This suggests a recursive (or stack-based) post-order traversal, where we compute the answer for children before their manager.

To make lookups and traversals fast, it's helpful to build a mapping from each manager to their direct reports. This allows us to efficiently traverse the tree from the root down.

Solution Approach

• Step 1: Parse the input to build a mapping from managerId to a list of direct report ids. This is often called an adjacency list in tree/graph terminology.
• Step 2: Identify the root of the tree (the employee with managerId = -1).
• Step 3: For each employee, recursively compute the total number of employees in their subtree (excluding themselves). This can be done using Depth-First Search (DFS), either recursively or using a stack.
• Step 4: Store the computed report count for each employee in a result mapping.
• Step 5: Return or output the result mapping.

We use a hash map (dictionary) for the adjacency list because lookups and insertions are O(1) on average. The post-order DFS ensures we only compute each subtree once, avoiding redundant work.

Example Walkthrough

Input:

  employees = [
    { "id": 1, "managerId": -1 },
    { "id": 2, "managerId": 1 },
    { "id": 3, "managerId": 1 },
    { "id": 4, "managerId": 2 },
    { "id": 5, "managerId": 2 }
  ]
  

Tree structure:

• 1 is the root (CEO)
• 2 and 3 report to 1
• 4 and 5 report to 2

DFS Traversal:

• Start at 1. Its direct reports are 2 and 3.
• Go to 2: its direct reports are 4 and 5.
• 4 and 5 have no reports. So, reports[4] = 0, reports[5] = 0.
• reports[2] = reports[4] + reports[5] + 2 (for 4 and 5) = 0 + 0 + 2 = 2.
• 3 has no reports. So, reports[3] = 0.
• reports[1] = reports[2] + reports[3] + 2 (for 2 and 3) = 2 + 0 + 2 = 4.

• 1: 4
• 2: 2
• 3: 0
• 4: 0
• 5: 0

Code Implementation

def count_reports(employees):
    from collections import defaultdict

    # Build adjacency list: managerId -> [list of direct reports]
    tree = defaultdict(list)
    id_set = set()
    root = None
    for emp in employees:
        emp_id = emp['id']
        mgr = emp['managerId']
        id_set.add(emp_id)
        if mgr == -1:
            root = emp_id
        else:
            tree[mgr].append(emp_id)

    # Result dictionary
    reports = {}

    def dfs(emp_id):
        total = 0
        for sub in tree.get(emp_id, []):
            total += 1 + dfs(sub)
        reports[emp_id] = total
        return total

    dfs(root)
    return reports
      

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

struct Employee {
    int id;
    int managerId;
};

void dfs(int empId, unordered_map<int, vector<int>>& tree, unordered_map<int, int>& reports) {
    int total = 0;
    for (int sub : tree[empId]) {
        dfs(sub, tree, reports);
        total += 1 + reports[sub];
    }
    reports[empId] = total;
}

unordered_map<int, int> countReports(vector<Employee>& employees) {
    unordered_map<int, vector<int>> tree;
    int root = -1;
    for (auto& emp : employees) {
        if (emp.managerId == -1) {
            root = emp.id;
        } else {
            tree[emp.managerId].push_back(emp.id);
        }
    }
    unordered_map<int, int> reports;
    dfs(root, tree, reports);
    return reports;
}
      

import java.util.*;

class Employee {
    int id, managerId;
    Employee(int id, int managerId) {
        this.id = id;
        this.managerId = managerId;
    }
}

public class Solution {
    public Map<Integer, Integer> countReports(List<Employee> employees) {
        Map<Integer, List<Integer>> tree = new HashMap<>();
        int root = -1;
        for (Employee emp : employees) {
            if (emp.managerId == -1) {
                root = emp.id;
            } else {
                tree.computeIfAbsent(emp.managerId, k -> new ArrayList<>()).add(emp.id);
            }
        }
        Map<Integer, Integer> reports = new HashMap<>();
        dfs(root, tree, reports);
        return reports;
    }

    private int dfs(int empId, Map<Integer, List<Integer>> tree, Map<Integer, Integer> reports) {
        int total = 0;
        for (int sub : tree.getOrDefault(empId, new ArrayList<>())) {
            total += 1 + dfs(sub, tree, reports);
        }
        reports.put(empId, total);
        return total;
    }
}
      

function countReports(employees) {
    const tree = {};
    let root = null;
    for (const emp of employees) {
        if (emp.managerId === -1) {
            root = emp.id;
        } else {
            if (!tree[emp.managerId]) tree[emp.managerId] = [];
            tree[emp.managerId].push(emp.id);
        }
    }
    const reports = {};

    function dfs(empId) {
        let total = 0;
        if (tree[empId]) {
            for (const sub of tree[empId]) {
                total += 1 + dfs(sub);
            }
        }
        reports[empId] = total;
        return total;
    }

    dfs(root);
    return reports;
}
      

Time and Space Complexity

• Brute-force approach: For each employee, traverse the entire tree to count their reports. For n employees, this results in O(n^2) time complexity.
• Optimized (DFS) approach: We visit each employee exactly once, and for each employee, we process their direct reports. So the total time is O(n), where n is the number of employees.
• Space complexity: We use O(n) space for the adjacency list and O(n) for the result mapping, giving O(n) total space.

The optimized approach is efficient and scalable for large trees.

Summary

This problem leverages tree traversal and mapping techniques to efficiently compute the number of reports for each employee. By building an adjacency list and using post-order DFS, we avoid redundant computations and ensure that each employee's report count is calculated only once. The elegance of the solution comes from recognizing the recursive nature of the problem and using a hash map to represent the reporting structure.