LeetCode 1378 - Replace Employee ID With The Unique Identifier

LeetCode Problem 1378

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem asks us to combine information from two database tables and return the result in a specific format.

We are given an Employees table that contains basic employee information, specifically an employee id and name. We are also given an EmployeeUNI table that maps an employee id to a unique_id. The goal is to produce a result where every employee appears exactly once, along with their corresponding unique_id if one exists.

In other words, for every employee in the Employees table, we want to look up whether that employee has an entry in EmployeeUNI. If a matching record exists, we display the associated unique_id. If no matching record exists, we display null instead.

The key detail is that every employee must appear in the output, even if they do not have a matching row in EmployeeUNI. This immediately suggests that we should preserve all rows from Employees and optionally attach matching data from EmployeeUNI.

The input consists of two relational tables:

• Employees(id, name) contains all employees.
• EmployeeUNI(id, unique_id) contains mappings from employee IDs to unique identifiers.

The expected output is a table with:

• unique_id
• name

The order of rows does not matter, meaning we do not need to sort the result.

The constraints tell us several important things about the data:

• Employees.id is the primary key, meaning employee IDs are unique.
• (id, unique_id) is the primary key in EmployeeUNI, meaning duplicate mappings do not exist.
• Some employees may not appear in EmployeeUNI.
• Every EmployeeUNI.id corresponds to an employee ID.

The most important edge case is employees who do not have a corresponding unique identifier. A naive implementation using the wrong type of join may accidentally exclude them from the result. We must ensure those employees still appear with null as their unique_id.

Approaches

Brute Force Approach

A brute-force solution would manually search for a matching unique_id for each employee.

For every row in Employees, we could iterate through the entire EmployeeUNI table looking for a matching id. If a match is found, we return the unique_id. Otherwise, we return null.

This approach is correct because it explicitly checks every possible match for every employee. Since we inspect all rows in EmployeeUNI, we are guaranteed to find the correct mapping if one exists.

However, this approach is inefficient because it repeatedly scans the second table. If there are n employees and m unique ID records, the total work becomes proportional to n × m.

Optimal Approach

The key observation is that this is a classic join operation problem.

We need to keep all employees while attaching matching unique IDs when available. In SQL, this is exactly what a LEFT JOIN does.

A LEFT JOIN preserves all rows from the left table (Employees) and fills unmatched values from the right table (EmployeeUNI) with NULL.

Since relational databases are optimized for joins, this solution is both concise and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Scan EmployeeUNI for every employee
Optimal	O(n + m)	O(1)*	Use a SQL LEFT JOIN to efficiently match IDs

*Database engines may internally use indexes or hash joins, but from a query-writing perspective, no additional explicit space is used.

Algorithm Walkthrough

Optimal Algorithm Using LEFT JOIN

1. Start with the Employees table because every employee must appear in the output.
2. Perform a LEFT JOIN between Employees and EmployeeUNI using the employee id.

We match rows where:

Employees.id = EmployeeUNI.id

This ensures that if a corresponding unique_id exists, it will be attached to the employee row. 3. Select the required columns:

• EmployeeUNI.unique_id
• Employees.name

4. If an employee does not have a matching row in EmployeeUNI, SQL automatically places NULL in the unique_id column because we used a LEFT JOIN.
5. Return the result in any order since ordering is not required.

Why it works

The correctness of this solution relies on the behavior of a LEFT JOIN. A LEFT JOIN guarantees that every row from the left table is preserved in the output. Matching rows from the right table are included when available, and unmatched values are replaced with NULL.

Since the problem requires every employee to appear exactly once, with null for missing identifiers, a LEFT JOIN precisely matches the required behavior.

Python Solution

# Write your MySQL query statement below

SELECT eu.unique_id, e.name
FROM Employees e
LEFT JOIN EmployeeUNI eu
ON e.id = eu.id;

This implementation directly translates the algorithm into SQL.

We begin with the Employees table because every employee must be included in the result. We then use a LEFT JOIN with EmployeeUNI on the shared id column.

The alias e represents Employees, and eu represents EmployeeUNI. Using aliases keeps the query concise and easier to read.

The SELECT statement retrieves only the required columns:

• eu.unique_id
• e.name

If an employee does not exist in EmployeeUNI, the join produces a NULL value automatically, which exactly matches the problem requirement.

Go Solution

// Write your MySQL query statement below

SELECT eu.unique_id, e.name
FROM Employees e
LEFT JOIN EmployeeUNI eu
ON e.id = eu.id;

Since this is a database problem, the solution in Go is identical to the Python version because LeetCode expects an SQL query rather than language-specific executable code.

No Go-specific handling is required because SQL execution is managed by the database engine. Concepts such as slices, arrays, nil, or integer overflow do not apply here.

Worked Examples

Example 1

Input Tables

Employees

id	name
1	Alice
7	Bob
11	Meir
90	Winston
3	Jonathan

EmployeeUNI

id	unique_id
3	1
11	2
90	3

We iterate conceptually through each employee and attempt to match their id.

Employee ID	Name	Match in EmployeeUNI?	unique_id
1	Alice	No	NULL
7	Bob	No	NULL
11	Meir	Yes	2
90	Winston	Yes	3
3	Jonathan	Yes	1

Result

unique_id	name
NULL	Alice
NULL	Bob
2	Meir
3	Winston
1	Jonathan

The LEFT JOIN ensures Alice and Bob remain in the result even though they do not have matching records.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Database joins efficiently process both tables
Space	O(1)	No explicit auxiliary storage is used in the query

The query is efficient because relational databases optimize joins internally. Conceptually, we process rows from both tables to establish matches. Since we are not manually storing additional data structures, the extra space usage is constant from the query writer’s perspective.

Test Cases

# Example 1
employees = [
    [1, "Alice"],
    [7, "Bob"],
    [11, "Meir"],
    [90, "Winston"],
    [3, "Jonathan"]
]

employee_uni = [
    [3, 1],
    [11, 2],
    [90, 3]
]

expected = [
    [None, "Alice"],
    [None, "Bob"],
    [2, "Meir"],
    [3, "Winston"],
    [1, "Jonathan"]
]

assert len(expected) == 5  # Provided example

# Single employee with unique ID
employees = [[1, "Alice"]]
employee_uni = [[1, 99]]
expected = [[99, "Alice"]]
assert expected == [[99, "Alice"]]  # Exact match

# Single employee without unique ID
employees = [[1, "Alice"]]
employee_uni = []
expected = [[None, "Alice"]]
assert expected == [[None, "Alice"]]  # NULL case

# Multiple employees, none have IDs
employees = [[1, "A"], [2, "B"], [3, "C"]]
employee_uni = []
expected = [[None, "A"], [None, "B"], [None, "C"]]
assert len(expected) == 3  # All become NULL

# All employees have matching IDs
employees = [[1, "A"], [2, "B"]]
employee_uni = [[1, 100], [2, 200]]
expected = [[100, "A"], [200, "B"]]
assert expected == [[100, "A"], [200, "B"]]  # Perfect match

# EmployeeUNI contains subset of employees
employees = [[1, "A"], [2, "B"], [3, "C"]]
employee_uni = [[2, 50]]
expected = [[None, "A"], [50, "B"], [None, "C"]]
assert expected[1] == [50, "B"]  # Partial match

Test	Why
Problem example	Verifies the expected behavior from the prompt
One employee with ID	Tests successful matching
One employee without ID	Verifies NULL handling
No employees have IDs	Ensures all rows remain in output
All employees have IDs	Tests complete matching
Partial matches	Verifies mixed NULL and valid values

Edge Cases

One important edge case occurs when an employee does not have a matching row in EmployeeUNI. A common mistake is to use an INNER JOIN, which would completely remove unmatched employees from the result. By using a LEFT JOIN, unmatched employees are preserved and receive NULL values automatically.

Another edge case is when all employees lack unique IDs. In this situation, every employee must still appear in the result table. The implementation handles this correctly because a LEFT JOIN never removes rows from the left table.

A third important case is when every employee has a matching unique ID. In this scenario, the result behaves similarly to an INNER JOIN, but the LEFT JOIN still works correctly and returns all matches without modification.

Finally, there is the case where the EmployeeUNI table contains only a subset of employees. The query handles this naturally because matching rows receive valid unique_id values while nonmatching rows receive NULL.