Primary Department for Each Employee - Solution & Explanation
Problem Statement
Table: Employee
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| employee_id | int |
| department_id | int |
| primary_flag | varchar |
+---------------+---------+
(employee_id, department_id) is the primary key (combination of columns with unique values) for this table.
employee_id is the id of the employee.
department_id is the id of the department to which the employee belongs.
primary_flag is an ENUM (category) of type ('Y', 'N'). If the flag is 'Y', the department is the primary department for the employee. If the flag is 'N', the department is not the primary.
Employees can belong to multiple departments. When the employee joins other departments, they need to decide which department is their primary department. Note that when an employee belongs to only one department, their primary column is 'N'.
Write a solution to report all the employees with their primary department. For employees who belong to one department, report their only department.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Employee table: +-------------+---------------+--------------+ | employee_id | department_id | primary_flag | +-------------+---------------+--------------+ | 1 | 1 | N | | 2 | 1 | Y | | 2 | 2 | N | | 3 | 3 | N | | 4 | 2 | N | | 4 | 3 | Y | | 4 | 4 | N | +-------------+---------------+--------------+ Output: +-------------+---------------+ | employee_id | department_id | +-------------+---------------+ | 1 | 1 | | 2 | 1 | | 3 | 3 | | 4 | 3 | +-------------+---------------+ Explanation: - The Primary department for employee 1 is 1. - The Primary department for employee 2 is 1. - The Primary department for employee 3 is 3. - The Primary department for employee 4 is 3.
Approach Overview
Problem Overview: Each row in the Employee table stores an employee_id, department_id, and a primary_flag. If an employee belongs to multiple departments, exactly one row has primary_flag = 'Y'. If the employee belongs to only one department, that row is considered the primary department even if the flag is 'N'. The task is to return the primary department for every employee.
Approach 1: SQL with Conditional Selection (O(n) time, O(1) space)
This approach filters rows directly using conditional logic. First select rows where primary_flag = 'Y'. These rows already represent the correct department for employees with multiple departments. The second case handles employees who appear only once in the table. You can detect them using GROUP BY employee_id and HAVING COUNT(*) = 1. Combining these conditions with an OR filter returns the correct department for both scenarios. The query scans the table once and relies on simple filtering and aggregation from SQL. Time complexity is O(n) and space complexity is O(1) excluding the result set.
Approach 2: SQL with Subqueries (O(n) time, O(1) space)
This method uses a subquery to identify employees that belong to exactly one department. The subquery groups by employee_id and filters with COUNT(*) = 1. The outer query then selects rows where either the employee is in this single-department set or the row has primary_flag = 'Y'. Subqueries make the logic explicit and often easier to read in interview settings. The database engine still performs a full scan with grouping, so the overall complexity remains O(n) time and O(1) extra space. This pattern appears frequently when solving filtering problems in database interview questions.
Approach 3: Aggregation and Conditional Selection (O(n) time, O(1) space)
Aggregation can also be used to compute the correct department during grouping. Group rows by employee_id and apply conditional expressions such as MAX(CASE WHEN primary_flag = 'Y' THEN department_id END). If a primary department exists, this expression returns it. If not, the employee must have only one row, so you can fall back to MAX(department_id). This approach keeps everything inside one grouped query and avoids explicit filtering. It’s a common pattern in SQL aggregation problems where conditional values must be selected.
Approach 4: Self-Join and Filtering (O(n) time, O(n) space)
A self-join can be used to detect whether an employee has multiple department records. Join the table with itself on employee_id and compare row counts or conditions that reveal duplicates. If multiple rows exist, keep the one with primary_flag = 'Y'. If no duplicates exist, return the single row. Although this works, it introduces additional joins and intermediate rows, making it less efficient than aggregation-based solutions.
Recommended for interviews: The conditional filtering or aggregation approach is typically expected. It shows you understand how to combine GROUP BY, conditional expressions, and filtering in SQL. A brute-force self-join demonstrates reasoning but is rarely the cleanest solution.
Approach 1: Using SQL with Conditional Selection
This approach involves utilizing SQL queries to select the primary department for each employee effectively. The idea is to select the department_id directly if the primary_flag is 'Y'. For cases with a single department, we forcefully set the primary_flag to 'N' but choose that department.
This solution makes use of a subquery to determine the employees who belong to only one department. We use a simple GROUP BY and HAVING clause to get such employees. The WHERE clause merges this subquery result with employees who have their primary_flag set to 'Y'.
Code
SQL
Complexity
Time Complexity: O(n), where n is the number of records in the Employee table. The query involves a single pass through the data for filtering and an additional pass for the group operation.
Space Complexity: O(n) for storing intermediate results during grouping.
Approach 2: Using SQL with Subqueries
This approach leverages SQL subqueries to determine if an employee belongs to only one department and selects the sole department as the primary. For employees with more than one department, the department marked with 'Y' is considered primary.
This query uses a CASE statement to differentiate between employees with multiple departments and those with a single one. When there are multiple departments, the query picks the one with primary_flag = 'Y'. For employees with only one department, it simply selects that department as primary.
Code
SQL
Complexity
Time Complexity: O(n), where n is the number of records in the Employee table. The inner subquery is efficient due to indexing and specific filtering.
Space Complexity: O(1) if indexing is used on employee_id and department_id.
Approach 3: Approach 1: Aggregation and Conditional Selection
This approach involves determining whether an employee has multiple departments or a single department by using aggregation. We can group the records by employee_id and use a COUNT function to find out the number of departments each employee belongs to. If an employee only belongs to one department, we select it regardless of the primary_flag. Otherwise, we pick the department where primary_flag is 'Y'.
This SQL query uses a CASE statement, aggregation, and conditional max to determine which department an employee belongs to primarily. If the employee belongs to just one department, that department_id is selected. Else, it chooses the department with 'Y' as primary_flag.
Code
SQL
Complexity
Time Complexity: O(N), where N is the number of rows in the Employee table. This is due to the need to scan through all rows once for the aggregation.
Space Complexity: O(M), where M is the number of unique employee_ids due to the storage required for the result set.
Approach 4: Approach 2: Self-Join and Filtering
This approach requires joining the Employee table with itself to identify employees with multiple department entries. We select the department where the primary_flag is 'Y'. For cases where all entries for an employee have primary_flag as 'N', the logic select the minimal department_id. This approach might involve more steps compared to the aggregation method but helps emphasize filtering techniques.
This SQL query performs a self-join on the Employee table to identify employees' primary departments. If no primary department is specified via the primary_flag, it defaults to any (here the minimal) department_id available for those employees. This takes advantage of the LEFT JOIN and COALESCE to ensure all employees are returned.
Code
SQL
Complexity
Time Complexity: O(N^2), where N is the number of rows in the Employee table due to the self-join operation.
Space Complexity: O(N) for storing results where N is the number of unique employee_ids.
Approach 5: Merging
We can first query all employees who already have a direct department, and then query all employees who belong to only one department. Finally, we can merge the two results using UNION.
Code
MySQL
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using SQL with Conditional Selection | Time Complexity: O(n), where n is the number of records in the Employee table. The query involves a single pass through the data for filtering and an additional pass for the group operation. |
| Using SQL with Subqueries | Time Complexity: O(n), where n is the number of records in the Employee table. The inner subquery is efficient due to indexing and specific filtering. |
| Approach 1: Aggregation and Conditional Selection | Time Complexity: O(N), where N is the number of rows in the Employee table. This is due to the need to scan through all rows once for the aggregation. Space Complexity: O(M), where M is the number of unique employee_ids due to the storage required for the result set. |
| Approach 2: Self-Join and Filtering | Time Complexity: O(N^2), where N is the number of rows in the Employee table due to the self-join operation. Space Complexity: O(N) for storing results where N is the number of unique employee_ids. |
| Merging | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| SQL with Conditional Selection | O(n) | O(1) | Best general solution when simple filtering and grouping can identify primary rows |
| SQL with Subqueries | O(n) | O(1) | Useful when separating logic for single-department employees improves readability |
| Aggregation and Conditional Selection | O(n) | O(1) | Preferred when solving with grouped aggregation and CASE expressions |
| Self-Join and Filtering | O(n) | O(n) | Works when detecting duplicates via joins but generally less efficient |
Video Solution
Primary Department for Each Employee | Leetcode 1789 | Crack SQL Interviews in 50 Qs #mysql • Learn With Chirag • 10,610 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Primary Department for Each Employee easy or hard?
Primary Department for Each Employee Python/Java solution
How to solve Primary Department for Each Employee in O(n)?
What is the best approach for Primary Department for Each Employee?
Is Primary Department for Each Employee asked at Google/Amazon/Meta?
What data structure is used in Primary Department for Each Employee?
What is the time complexity of Primary Department for Each Employee?
Ready to solve this problem?
Practice Primary Department for Each Employee with our built-in code editor and test cases.
Practice on FleetCode