LeetCode 1789 - Primary Department for Each Employee

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem provides a database table named Employee that stores information about which departments employees belong to. Each row contains three values:

Column	Meaning
`employee_id`	The employee identifier
`department_id`	A department the employee belongs to
`primary_flag`	Whether this department is the employee's primary department

The combination (employee_id, department_id) is unique, meaning the same employee cannot appear twice for the same department.

An employee may belong to one department or multiple departments.

The important rule is:

If an employee belongs to multiple departments, exactly one of those rows will have primary_flag = 'Y'.
If an employee belongs to only one department, the flag will be 'N', but that department should still be considered the primary department in the final answer.

The task is to return exactly one row per employee, containing:

employee_id
the correct primary department_id

The output order does not matter.

For example:

Employee 2 belongs to departments 1 and 2
Department 1 has primary_flag = 'Y'
Therefore the answer for employee 2 is (2, 1)

Another example:

Employee 1 belongs only to department 1
Its flag is 'N'
Since it is the only department, it is automatically treated as the primary department

The problem is classified as an easy database problem because the logic mainly depends on filtering rows correctly.

The key observation is that there are two valid situations for selecting a row:

The row has primary_flag = 'Y'
The employee appears only once in the entire table

Several edge cases are important:

Employees with only one department and flag 'N'
Employees with many departments but only one 'Y'
Employees whose primary department is not the first row in the table
Multiple employees sharing the same department

The problem guarantees valid data, so we do not need to handle invalid cases such as multiple 'Y' rows for the same employee.

Approaches

Brute Force Approach

A brute force solution would process employees one by one.

For every employee:

Scan the entire table to count how many departments they belong to.
Scan again to find whether one row has primary_flag = 'Y'.
If no 'Y' exists, choose the only department.

This approach is correct because it explicitly checks all rows for every employee and applies the problem rules directly.

However, it is inefficient because the table may be scanned repeatedly for the same employee. If there are n rows, repeatedly traversing the table for each employee can lead to quadratic behavior.

Optimal Approach

The better approach uses SQL aggregation.

The main insight is that we only need two categories of rows:

Rows where primary_flag = 'Y'
Rows belonging to employees whose total department count is exactly 1

We can identify employees with only one department using:

GROUP BY employee_id
HAVING COUNT(*) = 1

Then we simply select:

all rows with primary_flag = 'Y'
all rows whose employee belongs to the single-department group

This avoids repeated scans and lets the database engine efficiently perform grouping and filtering.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the table for each employee
Optimal	O(n)	O(n)	Uses grouping and filtering efficiently

Algorithm Walkthrough

Optimal SQL Algorithm

First, identify employees who belong to exactly one department.

We group rows by employee_id and count how many rows each employee has.

GROUP BY employee_id
HAVING COUNT(*) = 1

These employees automatically use their only department as the primary department. 2. Next, select all rows where primary_flag = 'Y'.

These rows already explicitly indicate the primary department. 3. Also select rows whose employee appears in the single-department group.

These rows represent employees with only one department. 4. Combine both conditions using OR. 5. Return only:

employee_id
department_id

Why it works

The solution works because every employee must fall into exactly one of two categories:

The employee belongs to multiple departments, in which case exactly one row has primary_flag = 'Y'
The employee belongs to only one department, in which case that only department is the answer

The query selects precisely those rows and excludes all others, guaranteeing exactly one correct department per employee.

Python Solution

Although this is a database problem, LeetCode database solutions are usually written in SQL. Below is the correct SQL solution.

SELECT employee_id, department_id
FROM Employee
WHERE primary_flag = 'Y'
   OR employee_id IN (
        SELECT employee_id
        FROM Employee
        GROUP BY employee_id
        HAVING COUNT(*) = 1
   );

The query has two major parts.

The outer query retrieves the final rows that should appear in the answer.

The first condition:

primary_flag = 'Y'

handles employees with multiple departments by selecting their designated primary department.

The second condition:

employee_id IN (...)

handles employees who belong to only one department.

The subquery groups rows by employee and keeps only employees whose department count equals one.

Combining the conditions with OR ensures both categories are included.

Go Solution

Go is not applicable for LeetCode database problems because the platform expects a SQL query instead of executable Go code.

The correct submission for this problem is the SQL query shown below.

SELECT employee_id, department_id
FROM Employee
WHERE primary_flag = 'Y'
   OR employee_id IN (
        SELECT employee_id
        FROM Employee
        GROUP BY employee_id
        HAVING COUNT(*) = 1
   );

Unlike algorithmic Go problems, there are no concerns here about slices, maps, memory allocation, or integer overflow because the execution is handled entirely by the SQL engine.

Worked Examples

Example 1

Input 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

Step 1, Find employees with only one department

We group by employee.

employee_id	count
1	1
2	2
3	1
4	3

Employees 1 and 3 qualify because they have exactly one department.

Step 2, Select rows with `primary_flag = 'Y'`

employee_id	department_id
2	1
4	3

Step 3, Select rows for single-department employees

employee_id	department_id
1	1
3	3

Step 4, Combine results

employee_id	department_id
1	1
2	1
3	3
4	3

This matches the expected output.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The table is scanned during grouping and filtering
Space	O(n)	Grouping operations may store employee aggregates

The database engine performs a grouping operation on all rows once and then evaluates the filtering conditions. Modern SQL engines optimize these operations efficiently, so the effective complexity is linear relative to the number of rows.

Test Cases

# Example 1, mixed single and multi department employees
employee = [
    [1, 1, 'N'],
    [2, 1, 'Y'],
    [2, 2, 'N'],
    [3, 3, 'N'],
    [4, 2, 'N'],
    [4, 3, 'Y'],
    [4, 4, 'N']
]

expected = [
    [1, 1],
    [2, 1],
    [3, 3],
    [4, 3]
]

# Single employee with one department
employee = [
    [1, 10, 'N']
]

expected = [
    [1, 10]
]

# Employee with multiple departments and clear primary
employee = [
    [5, 1, 'N'],
    [5, 2, 'Y'],
    [5, 3, 'N']
]

expected = [
    [5, 2]
]

# Multiple employees all with single departments
employee = [
    [1, 1, 'N'],
    [2, 2, 'N'],
    [3, 3, 'N']
]

expected = [
    [1, 1],
    [2, 2],
    [3, 3]
]

# Multiple employees sharing same department
employee = [
    [1, 5, 'N'],
    [2, 5, 'Y'],
    [2, 6, 'N']
]

expected = [
    [1, 5],
    [2, 5]
]

Test	Why
Mixed single and multiple departments	Validates the main problem logic
One employee, one department	Tests smallest valid input
Multiple departments with one primary	Ensures `'Y'` selection works
All employees single department	Ensures single-department logic works repeatedly
Shared department IDs	Confirms grouping is based on employee, not department

Edge Cases

Employee Belongs to Only One Department

This is the most important edge case because the row's primary_flag is 'N', which could incorrectly exclude it if we only searched for 'Y'.

For example:

employee_id	department_id	primary_flag
1	10	N

A naive query filtering only 'Y' rows would miss this employee entirely.

The implementation correctly handles this by explicitly selecting employees whose department count equals one.

Employee Belongs to Multiple Departments

Another important case is when an employee has several departments but only one is primary.

Example:

employee_id	department_id	primary_flag
2	1	N
2	2	Y
2	3	N

The query correctly selects only the 'Y' row and ignores the others.

Department IDs are not unique globally.