Practice/Amazon/Leetcode 1270. All People Report to the Given Manager

Leetcode 1270. All People Report to the Given Manager

CodingOptional

Problem

You are given information about the reporting structure in a company. The structure is represented as a list of relationships, where each relationship is a pair [manager_id, employee_id] indicating that the employee with employee_id directly reports to the manager with manager_id.

Given a specific manager_id, return a list of all employee IDs who report to this manager, either directly or indirectly (through their own managers). The order of employees in the result does not matter.

Requirements

1. Build a representation of the organizational hierarchy from the given relationships
2. Find all employees at any level below the given manager
3. Handle multi-level reporting chains correctly
4. Return an empty list if the manager has no subordinates
5. Each employee ID appears at most once in the relationships as an employee (no circular reporting)

Constraints

• 1 ≤ relationships.length ≤ 1000
• relationships[i].length == 2
• 1 ≤ manager_id, employee_id ≤ 10000
• All employee IDs are unique in the employee position of relationships
• There are no cycles in the reporting structure
• Expected time complexity: O(n) where n is the number of relationships
• Expected space complexity: O(n)

Examples

Example 1:

Input: relationships = [[1, 2], [1, 3], [2, 4], [2, 5]], manager_id = 1 Output: [2, 3, 4, 5] Explanation: Manager 1 has direct reports 2 and 3. Employee 2 manages employees 4 and 5. So all of 2, 3, 4, and 5 report to manager 1 either directly or indirectly.

Example 2:

Input: relationships = [[1, 2], [2, 3], [3, 4]], manager_id = 2 Output: [3, 4] Explanation: Manager 2 directly manages employee 3, who in turn manages employee 4. Both 3 and 4 report to manager 2.

Example 3:

Input: relationships = [[1, 2], [3, 4]], manager_id = 5 Output: [] Explanation: Manager 5 is not managing anyone in this organization, so the result is empty.