LeetCode 1270 - All People Report to the Given Manager

The problem asks us to identify all employees in a company who directly or indirectly report to the head of the company,

leetcodemediumdatabase

LeetCode Problem 1270

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem asks us to identify all employees in a company who directly or indirectly report to the head of the company, whose employee_id is 1. The input is a table Employees containing three columns: employee_id, employee_name, and manager_id. Each row defines an employee and the manager they report to. The expected output is a table listing the employee_id of employees who have a reporting chain leading to the head of the company.

The constraints specify that the company is small, with at most three levels of indirect reporting to the head. This implies we do not need to handle extremely deep or complex hierarchies, but we do need to correctly traverse chains of length up to three.

Important edge cases include employees who report to themselves (like the head), cycles (though unlikely due to the problem setup), employees who report to managers outside the head's chain, and managers with no direct reports.

Approaches

The brute-force approach is to iterate through each employee and recursively or iteratively follow the manager_id chain until we either reach the head of the company (employee_id = 1) or reach a manager outside the chain. While this works correctly, it can involve repeated traversal of the same chains, especially if multiple employees share common managers, making it inefficient for large datasets.

The optimal approach leverages the fact that there are at most three levels of reporting. We can write a SQL query that explicitly joins the Employees table up to three times, checking direct, second-level, and third-level reporting. This avoids repeated traversal and leverages relational database joins to efficiently compute the result.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Iterate through each employee, recursively check manager chains; can repeat work
Optimal O(n) O(n) Use up to three joins to find employees reporting within three levels; leverages SQL joins

Algorithm Walkthrough

  1. Identify employees who directly report to the head of the company by filtering rows where manager_id = 1.
  2. Identify employees who indirectly report to the head through a second-level manager. Join the Employees table with itself where the first table’s manager_id equals the second table’s employee_id, and the second table reports to the head.
  3. Identify employees who indirectly report to the head through a third-level manager. Join the table again for the third level using the same pattern.
  4. Combine all results using UNION to ensure unique employee_id values. This captures employees reporting at any level up to three.
  5. Return the result table with a single column employee_id.

This works because each employee can only be at most three steps away from the head. By explicitly joining for each level, we guarantee that all employees in the hierarchy are considered without missing anyone or double-counting.

Python Solution

# This problem is a SQL problem; Python solution is not applicable

Since this problem is a pure SQL problem, a Python solution would not be meaningful. Instead, the optimal solution uses SQL joins.

Go Solution

// This problem is a SQL problem; Go solution is not applicable

Similarly, a Go solution would not be meaningful because the question expects an SQL table output.

SQL Solution

SELECT employee_id
FROM Employees
WHERE manager_id = 1

UNION

SELECT e1.employee_id
FROM Employees e1
JOIN Employees e2 ON e1.manager_id = e2.employee_id
WHERE e2.manager_id = 1

UNION

SELECT e1.employee_id
FROM Employees e1
JOIN Employees e2 ON e1.manager_id = e2.employee_id
JOIN Employees e3 ON e2.manager_id = e3.employee_id
WHERE e3.manager_id = 1;

This SQL query efficiently retrieves all employees reporting directly or indirectly to the head. The first SELECT captures direct reports. The second SELECT captures second-level reports, and the third SELECT captures third-level reports. UNION ensures uniqueness.

Worked Examples

For the provided input:

+-------------+---------------+------------+
| employee_id | employee_name | manager_id |
+-------------+---------------+------------+
| 1           | Boss          | 1          |
| 3           | Alice         | 3          |
| 2           | Bob           | 1          |
| 4           | Daniel        | 2          |
| 7           | Luis          | 4          |
| 8           | Jhon          | 3          |
| 9           | Angela        | 8          |
| 77          | Robert        | 1          |
+-------------+---------------+------------+

Step 1: Direct reports (manager_id = 1) → employee_id 2 and 77.

Step 2: Second-level reports (manager_id matches employee_id of direct reports) → employee_id 4 (manager_id = 2).

Step 3: Third-level reports (manager_id matches employee_id of second-level reports) → employee_id 7 (manager_id = 4).

Resulting table:

+-------------+
| employee_id |
+-------------+
| 2           |
| 77          |
| 4           |
| 7           |
+-------------+

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each join scans the table once, constant number of joins (3), total O(n)
Space O(n) Storing intermediate join results requires linear space relative to number of employees

The reasoning is that the company is small and the maximum hierarchy depth is bounded. Each join adds a linear pass, not exponential.

Test Cases

# Since this is SQL, test cases are represented as tables
# Example 1
# Employees table:
# | 1 | Boss | 1 |
# | 3 | Alice | 3 |
# | 2 | Bob | 1 |
# | 4 | Daniel | 2 |
# | 7 | Luis | 4 |
# | 8 | Jhon | 3 |
# | 9 | Angela | 8 |
# | 77 | Robert | 1 |
# Expected output: 2, 77, 4, 7
Test Why
Direct reports only Validate that employees directly under head are included
Multi-level reports Validate that employees indirectly reporting (up to 3 levels) are included
Cyclic or self-reporting Ensure head or self-reporting employees do not cause infinite loops

Edge Cases

  1. Employee reporting to themselves: The head has manager_id = 1. Our joins and UNION handle this by not including the head in the output, only employees reporting to them.
  2. Employees outside the head's hierarchy: Some employees may report to managers who ultimately do not link to the head. Our query inherently excludes these because the join conditions require reporting chains to terminate at manager_id = 1.
  3. Maximum indirect depth: An employee reporting indirectly three levels away from the head is included correctly because the query joins up to three levels. Any employee beyond three levels would not be included, which matches the problem constraints.

This solution is robust, handles all expected reporting scenarios, and uses the database efficiently without recursion or procedural logic.