Problem

Table: Employees

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| emp_id      | int     |
| emp_name    | varchar |
| dep_id      | int     |
| position    | varchar |
+-------------+---------+
emp_id is column of unique values for this table.
This table contains emp_id, emp_name, dep_id, and position.

Write a solution to find the name of the manager from the largest department. There may be multiple largest departments when the number of employees in those departments is the same.

Return the result table sorted bydep_id inascending order .

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Input: 
Employees table:
+--------+----------+--------+---------------+
| emp_id | emp_name | dep_id | position      | 
+--------+----------+--------+---------------+
| 156    | Michael  | 107    | Manager       |
| 112    | Lucas    | 107    | Consultant    |    
| 8      | Isabella | 101    | Manager       | 
| 160    | Joseph   | 100    | Manager       | 
| 80     | Aiden    | 100    | Engineer      | 
| 190    | Skylar   | 100    | Freelancer    | 
| 196    | Stella   | 101    | Coordinator   |
| 167    | Audrey   | 100    | Consultant    |
| 97     | Nathan   | 101    | Supervisor    |
| 128    | Ian      | 101    | Administrator |
| 81     | Ethan    | 107    | Administrator |
+--------+----------+--------+---------------+
**Output**
+--------------+--------+
| manager_name | dep_id | 
+--------------+--------+
| Joseph       | 100    | 
| Isabella     | 101    | 
+--------------+--------+
**Explanation**
- Departments with IDs 100 and 101 each has a total of 4 employees, while department 107 has 3 employees. Since both departments 100 and 101 have an equal number of employees, their respective managers will be included.
Output table is ordered by dep_id in ascending order.

Solution

Method 1 – SQL Aggregation and Filtering

Intuition

To find the manager(s) of the largest department(s), we first count the number of employees in each department, find the maximum size, and then select the manager(s) from those departments. We filter by position = ‘Manager’ and sort by dep_id.

Approach

  1. Count the number of employees in each department using GROUP BY dep_id.
  2. Find the maximum department size.
  3. Select the manager(s) from departments with the maximum size.
  4. Sort the result by dep_id ascending.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

SELECT e.emp_name AS manager_name, e.dep_id
FROM Employees e
JOIN (
    SELECT dep_id, COUNT(*) AS cnt
    FROM Employees
    GROUP BY dep_id
) d ON e.dep_id = d.dep_id
WHERE e.position = 'Manager'
  AND d.cnt = (
    SELECT MAX(cnt) FROM (
      SELECT COUNT(*) AS cnt FROM Employees GROUP BY dep_id
    ) t
  )
ORDER BY e.dep_id ASC;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

SELECT e.emp_name AS manager_name, e.dep_id
FROM Employees e
JOIN (
    SELECT dep_id, COUNT(*) AS cnt
    FROM Employees
    GROUP BY dep_id
) d ON e.dep_id = d.dep_id
WHERE e.position = 'Manager'
  AND d.cnt = (
    SELECT MAX(cnt) FROM (
      SELECT COUNT(*) AS cnt FROM Employees GROUP BY dep_id
    ) t
  )
ORDER BY e.dep_id ASC;
1
2
3
4
5
6
7

class Solution:
    def manager_of_largest_department(self, employees: 'pd.DataFrame') -> 'pd.DataFrame':
        dep_counts = employees.groupby('dep_id').size()
        max_size = dep_counts.max()
        largest_deps = dep_counts[dep_counts == max_size].index
        managers = employees[(employees['dep_id'].isin(largest_deps)) & (employees['position'] == 'Manager')]
        return managers[['emp_name', 'dep_id']].rename(columns={'emp_name': 'manager_name'}).sort_values('dep_id').reset_index(drop=True)

Complexity

  • ⏰ Time complexity: O(n), where n is the number of employees, as we scan the table a constant number of times.
  • 🧺 Space complexity: O(d), where d is the number of departments, for storing department counts.