Table: Employee
+-------------+---------+ | Column Name | Type | +-------------+---------+ | id | int | | name | varchar | | department | varchar | | managerId | int | +-------------+---------+ id is the primary key (column with unique values) for this table. Each row of this table indicates the name of an employee, their department, and the id of their manager. If managerId is null, then the employee does not have a manager. No employee will be the manager of themself.
Write a solution to find managers with at least five direct reports.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Employee table: +-----+-------+------------+-----------+ | id | name | department | managerId | +-----+-------+------------+-----------+ | 101 | John | A | null | | 102 | Dan | A | 101 | | 103 | James | A | 101 | | 104 | Amy | A | 101 | | 105 | Anne | A | 101 | | 106 | Ron | B | 101 | +-----+-------+------------+-----------+ Output: +------+ | name | +------+ | John | +------+
This approach uses SQL's GROUP BY and HAVING clause to count the number of employees managed by each manager. We group the employees by their managerId and count the occurrences to determine the number of direct reports. We then filter the groups having at least five direct reports and join back with the Employee table to get the names of these managers.
First, we select the managers who have at least five direct reports by counting the number of employees corresponding to each managerId in the subquery. We then use this list to filter the original table and retrieve the names of these managers from the Employee table.
The time complexity of this query depends on the indexing and size of the original table. In general, it's O(n) for counting and filtering operations, where n is the number of rows in the Employee table.
This approach utilizes a join between the table itself, followed by a GROUP BY and filter with a HAVING clause. We join the Employee table with itself on the condition of matching the managerId to id. This join helps to create pairs of managers and their direct reports. By grouping based on the manager's id and applying a HAVING clause, we fetch managers with five or more reports.
In this implementation, we first join the table Employee with itself to create pairs between managers and their direct reports. We then group by the manager's id, counting the number of reports for each manager to filter those with at least five.
The time complexity for this query is similar to the previous approach, influenced by both the number of rows to join and then group. Generally, it would be about O(n) constrained within the database engine optimizations.
This approach involves using a SQL query to group employees by their managerId and then counting how many employees report to each manager. From this, we can filter out managers who have less than five direct reports.
We first create a subquery to select managerId from the Employee table, grouping by managerId and including only those managerIds with five or more entries. Then, we join this result with the Employee table to get the names of these managers.
Time Complexity: O(n), where n is the number of employees as we scan the list and group it.
Space Complexity: O(m), where m is the number of unique managerId entries that meet the criteria.
This solution uses a self join within the table and counts the direct reports for each manager by referring to the managerId.
Here, we perform a self join on the Employee table. We join on e1.id and e2.managerId, essentially matching each manager with their subordinates. We then group by the manager's id to count how many subordinates each has, and filter to keep those with at least 5 subordinates.
Time Complexity: O(n), due to the need to scan and join the relationships within the table.
Space Complexity: O(m), where m is the number of distinct managers in the table.
| Approach | Complexity |
|---|---|
| SQL Group By and Having Clause | The time complexity of this query depends on the indexing and size of the original table. In general, it's O(n) for counting and filtering operations, where n is the number of rows in the |
| Combination of Join and Group By | The time complexity for this query is similar to the previous approach, influenced by both the number of rows to join and then group. Generally, it would be about O(n) constrained within the database engine optimizations. |
| Grouping and Counting Managers | Time Complexity: O(n), where n is the number of employees as we scan the list and group it. |
| Using Self Join | Time Complexity: O(n), due to the need to scan and join the relationships within the table. |
Managers with at Least 5 Direct Reports | Leetcode 570 | Crack SQL Interviews in 50 Qs #mysql • Learn With Chirag • 10,048 views views
Watch 9 more video solutions →Practice Managers with at Least 5 Direct Reports with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor