LeetCode 2988 - Manager of the Largest Department

Difficulty: 🟡 Medium
Topics: Database

Solution

You included two different problems in one message, and the second prompt overrides the first at the end. I will answer for LeetCode 2988 - Manager of the Largest Department.

Problem Understanding

This problem asks us to identify the manager or managers of the department(s) with the highest employee count.

We are given a single database table named Employees, which stores employee information. Each row represents one employee and contains:

emp_id: a unique employee identifier
emp_name: the employee's name
dep_id: the department ID the employee belongs to
position: the employee's job title

The goal is to determine which department or departments have the largest number of employees, then return the manager's name for each of those departments.

An important detail is that multiple departments can tie for the largest size. In that case, we must return the manager for every tied department.

The output must contain:

manager_name
dep_id

The result must be sorted by dep_id in ascending order.

The problem guarantees that each department has a manager, otherwise it would not be possible to return the requested result consistently.

A naive implementation can easily make mistakes in a few situations. One common issue is assuming only one largest department exists. Another is filtering managers before determining department size, which could lead to incorrect counting. We must first compute department sizes, determine the maximum size, then retrieve the corresponding managers.

Since this is a database problem, constraints are generally handled efficiently by SQL engines. The main challenge is expressing the logic correctly and cleanly.

Approaches

Brute Force Approach

A brute-force strategy would first iterate through each department and, for every department, repeatedly scan the entire Employees table to count employees.

After computing counts for every department, we would determine the maximum department size. Then we would scan the table again to locate managers for departments matching that maximum size.

This approach is correct because it explicitly computes department sizes and selects managers only from departments with the largest count. However, it performs repeated scans of the table, which becomes inefficient for large datasets.

Optimal Approach

The key insight is that SQL is designed for aggregation and filtering.

We can solve this efficiently in three steps:

Use GROUP BY dep_id to count employees in every department.
Find the maximum department size.
Join back to Employees and filter only managers belonging to departments whose count equals the maximum.

This avoids repeated rescanning and expresses the logic declaratively.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(d)	Repeatedly scans employees for each department
Optimal	O(n log n)	O(d)	Uses aggregation and filtering in SQL

Here, n represents the number of employees and d represents the number of departments.

Algorithm Walkthrough

First, group employees by dep_id and count how many employees belong to each department. This gives us the size of every department.
Next, determine the maximum employee count among all departments. This tells us what qualifies as a "largest department".
Filter the departments to keep only those whose employee count equals the maximum value.
Join these departments back to the Employees table and select rows where position = 'Manager'. This retrieves the manager for each largest department.
Rename the selected employee name as manager_name and sort the final result by dep_id in ascending order.

Why it works

The correctness comes from separating the problem into two independent requirements:

identifying the largest department size
retrieving managers for those departments

Because department counts are computed before filtering for managers, every department is evaluated fairly. Selecting only departments whose count equals the maximum guarantees that tied largest departments are included. Filtering by position = 'Manager' ensures only managers are returned.

SQL Solution

WITH DepartmentCounts AS (
    SELECT
        dep_id,
        COUNT(*) AS employee_count
    FROM Employees
    GROUP BY dep_id
),
LargestDepartments AS (
    SELECT dep_id
    FROM DepartmentCounts
    WHERE employee_count = (
        SELECT MAX(employee_count)
        FROM DepartmentCounts
    )
)

SELECT
    e.emp_name AS manager_name,
    e.dep_id
FROM Employees e
JOIN LargestDepartments ld
    ON e.dep_id = ld.dep_id
WHERE e.position = 'Manager'
ORDER BY e.dep_id;

Implementation Explanation

The solution uses two Common Table Expressions (CTEs) to make the logic easier to understand.

The first CTE, DepartmentCounts, computes the number of employees in each department using GROUP BY dep_id.

The second CTE, LargestDepartments, filters those department counts and keeps only departments whose employee count matches the maximum department size.

Finally, we join the filtered departments back to the Employees table. Since we only want managers, we filter rows where position = 'Manager'. The employee name is renamed to manager_name, and the result is ordered by department ID.

This structure keeps each logical step separate and easy to reason about.

Worked Example

Consider the example input:

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

Step 1: Count employees per department

dep_id	employee_count
100	4
101	4
107	3

Step 2: Find the maximum size

The maximum employee count is:

4

Step 3: Select largest departments

dep_id
100
101

Step 4: Retrieve managers

Filter employees where:

dep_id is 100 or 101
position = 'Manager'

manager_name	dep_id
Joseph	100
Isabella	101

Final Output

manager_name	dep_id
Joseph	100
Isabella	101

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Aggregation and sorting dominate execution
Space	O(d)	Stores department counts

The aggregation step scans the employee table once to compute department sizes. Finding the maximum department size is proportional to the number of departments. The final sorting by dep_id contributes logarithmic overhead. Since we only store aggregated information per department, the additional space depends on the number of departments rather than employees.

Test Cases

Although LeetCode database problems are validated through SQL execution rather than Python assertions, the following logical test cases cover important scenarios.

# Largest department tie
# Departments 100 and 101 both have 4 employees
assert True

# Single largest department
# Only department 200 has the most employees
assert True

# One employee department
# Manager should still be returned if largest
assert True

# All departments same size
# Return all managers sorted by dep_id
assert True

# Exactly two departments tied
# Ensure both managers are returned
assert True

# Sorting validation
# Output must be ascending by dep_id
assert True

Test	Why
Example with tie	Validates multiple largest departments
Single largest department	Ensures only one manager is returned
Department with one employee	Confirms minimal department handling
All equal department sizes	Verifies all managers are included
Two-way tie	Ensures tied departments are preserved
Sorting check	Validates ascending `dep_id` ordering

Edge Cases

Multiple Largest Departments

A common bug is assuming there is only one largest department. If two or more departments share the same employee count, all corresponding managers must be returned.

The implementation handles this correctly by filtering departments whose employee count equals the global maximum, rather than selecting only one department.

Department With a Single Employee

A department may contain only one employee, who is also the manager. If every department has one employee, then all departments are tied for largest size.

The query still works because COUNT(*) correctly counts all rows, including single-row departments.

Sorting Requirements

Even when the correct managers are identified, forgetting to sort the result can fail test cases.

The implementation explicitly uses ORDER BY e.dep_id to guarantee ascending order in the final output.