LeetCode 1350 - Students With Invalid Departments
This problem asks us to identify students who are enrolled in university departments that no longer exist in the departm
Difficulty: 🟢 Easy
Topics: Database
Solution
Problem Understanding
This problem asks us to identify students who are enrolled in university departments that no longer exist in the department registry.
We are given two database tables. The Departments table stores valid university departments, where each department has a unique id and a name. The Students table stores student records, where each student has a unique id, a name, and a department_id indicating which department they belong to.
The task is to find all students whose department_id does not correspond to any existing department in the Departments table. In other words, we need to identify students whose referenced department record is missing.
This is essentially a referential integrity problem. Normally, a student's department_id should point to a valid department. However, because departments may have been deleted or no longer exist, some students may reference invalid department IDs. We need to return only those students.
The expected output contains the id and name of all students with invalid departments. The order of the result does not matter, meaning any ordering is accepted.
From the schema, we know that id is the primary key in both tables, so department IDs are unique and student IDs are unique. Since the problem is categorized as an Easy database problem, the input size is likely manageable, but we should still aim for an efficient query.
Several edge cases are important to consider. If every student's department exists, the result should be empty. If the Departments table itself is empty, then every student becomes invalid because no departments exist. Another case is when multiple students reference the same missing department, in which case all of them should appear in the output. The problem guarantees valid table structures and primary keys, so we do not need to handle malformed data or duplicate department IDs.
Approaches
Brute Force Approach
A straightforward way to solve this problem is to check every student against every department manually.
For each student in the Students table, we scan through the entire Departments table to see whether a matching department ID exists. If no matching department is found, we include that student in the result.
This approach is correct because it explicitly verifies whether each student's department exists. However, it is inefficient because for every student, we potentially scan every department. If there are S students and D departments, this results in a nested scan.
In SQL terms, this resembles repeatedly checking membership through a full scan rather than using joins or indexed lookup mechanisms.
Key Insight for an Optimal Solution
The key observation is that this is fundamentally a matching problem between two tables. SQL databases are designed to handle these relationships efficiently using joins.
We want to identify students whose department_id has no matching row in Departments. A LEFT JOIN is ideal for this situation.
With a LEFT JOIN, we keep every student record and attempt to match it with a department. If no matching department exists, the joined department fields become NULL. We can then filter for rows where the department is missing.
Another elegant alternative is using NOT IN, but LEFT JOIN tends to be clearer and avoids pitfalls with NULL handling in SQL.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(S × D) | O(1) | Compare every student against every department |
| Optimal | O(S + D) | O(1) extra | Use LEFT JOIN to efficiently detect missing departments |
Algorithm Walkthrough
Optimal Algorithm Using LEFT JOIN
- Start with the
Studentstable because every student must be checked for validity. - Perform a
LEFT JOINbetweenStudentsandDepartmentsusing the condition:
Students.department_id = Departments.id
This step attempts to match each student's department with an existing department.
3. Because we use a LEFT JOIN, all students remain in the result, even if no matching department exists.
4. For students whose department does not exist, the joined Departments columns will contain NULL.
5. Filter the results using:
Departments.id IS NULL
This condition ensures we only keep students whose department lookup failed. 6. Select only the required columns:
Students.id and Students.name
since the problem requests only these fields.
Why it works
The correctness comes from the behavior of LEFT JOIN. Every student row is preserved, and matching department information is attached only when a department exists. If no match is found, SQL fills department columns with NULL. Therefore, filtering for Departments.id IS NULL precisely identifies students whose department reference is invalid.
Python Solution
LeetCode Database problems use SQL rather than executable Python. The following query is the complete LeetCode-submittable solution.
SELECT s.id, s.name
FROM Students s
LEFT JOIN Departments d
ON s.department_id = d.id
WHERE d.id IS NULL;
This query begins with the Students table because every student must be checked. A LEFT JOIN attempts to match each student's department_id with a department record. If a department exists, the row contains valid department information. If no department exists, the department columns become NULL.
The WHERE d.id IS NULL condition filters the results to include only students whose departments do not exist. Finally, we select only the student's id and name, which matches the required output format.
Go Solution
Since this is a Database problem, LeetCode expects an SQL query instead of Go code. The same SQL solution applies regardless of programming language selection.
SELECT s.id, s.name
FROM Students s
LEFT JOIN Departments d
ON s.department_id = d.id
WHERE d.id IS NULL;
There are no Go-specific implementation concerns here because this problem is solved entirely with SQL. Concepts such as slices, nil handling, or integer overflow do not apply.
Worked Examples
Example 1
Input Tables
Departments
| id | name |
|---|---|
| 1 | Electrical Engineering |
| 7 | Computer Engineering |
| 13 | Bussiness Administration |
Students
| id | name | department_id |
|---|---|---|
| 23 | Alice | 1 |
| 1 | Bob | 7 |
| 5 | Jennifer | 13 |
| 2 | John | 14 |
| 4 | Jasmine | 77 |
| 3 | Steve | 74 |
| 6 | Luis | 1 |
| 8 | Jonathan | 7 |
| 7 | Daiana | 33 |
| 11 | Madelynn | 1 |
We perform a LEFT JOIN between students and departments.
| Student | department_id | Matching Department Exists? | Included in Result? |
|---|---|---|---|
| Alice | 1 | Yes | No |
| Bob | 7 | Yes | No |
| Jennifer | 13 | Yes | No |
| John | 14 | No | Yes |
| Jasmine | 77 | No | Yes |
| Steve | 74 | No | Yes |
| Luis | 1 | Yes | No |
| Jonathan | 7 | Yes | No |
| Daiana | 33 | No | Yes |
| Madelynn | 1 | Yes | No |
After filtering rows where Departments.id IS NULL, the final result becomes:
| id | name |
|---|---|
| 2 | John |
| 7 | Daiana |
| 4 | Jasmine |
| 3 | Steve |
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(S + D) | Database joins efficiently process both tables |
| Space | O(1) extra | No additional data structures are explicitly used |
In practice, SQL databases optimize joins internally using indexes and execution plans. Conceptually, we process students and departments once to determine matches, making the solution effectively linear relative to input size.
Test Cases
Since this is a SQL problem, test cases are represented conceptually rather than executable Python assertions.
# Example 1
# Invalid departments: 14, 77, 74, 33
assert result == [
[2, "John"],
[7, "Daiana"],
[4, "Jasmine"],
[3, "Steve"]
]
# All departments valid
assert result == []
# Empty departments table
# Every student is invalid
assert result == [
[1, "Alice"],
[2, "Bob"]
]
# No students table rows
assert result == []
# Multiple students share same invalid department
assert result == [
[1, "Alice"],
[2, "Bob"]
]
| Test | Why |
|---|---|
| Provided example | Validates the main scenario with mixed valid and invalid departments |
| All departments valid | Ensures empty result handling |
| Empty departments table | Confirms all students become invalid |
| Empty students table | Verifies no output is returned |
| Shared invalid department | Ensures multiple affected students are included |
Edge Cases
Every Student Has a Valid Department
If all department_id values exist in Departments, the LEFT JOIN successfully finds matches for every student. As a result, no row will have NULL department values, and the query correctly returns an empty result set.
The Departments Table Is Empty
If there are no departments at all, every student's department reference becomes invalid. During the LEFT JOIN, every department column becomes NULL, so all students are included in the result. This case could easily break naive assumptions that departments always exist.
Multiple Students Reference the Same Missing Department
Several students may share the same invalid department_id. A buggy implementation might accidentally deduplicate results by department rather than by student. Our query operates at the student level, meaning every affected student appears independently in the output, which matches the problem requirements.
No Students Exist
If the Students table is empty, the join has no rows to process. The query naturally returns an empty result set without special-case handling. This demonstrates that the solution gracefully handles minimal input sizes.