Primary Department for Each Employee - Solution & Explanation

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.