Students With Invalid Departments - Video Solutions

Problem Overview: The Students table stores each student's department_id, while the Departments table contains valid department records. The task is to return students whose department_id does not exist in the Departments table. In other words, find rows where the foreign key reference is invalid.

Approach 1: Subquery with NOT IN (O(n + m) time, O(m) space)

This approach filters students using a NOT IN subquery. First, retrieve all valid department IDs from the Departments table. Then scan the Students table and return rows where department_id is not present in that set. Internally, the database engine evaluates the subquery once and compares each student row against it. This solution is concise and common in SQL interviews when working with database filtering problems. Time complexity is O(n + m) where n is the number of students and m is the number of departments, with O(m) space for the subquery result set.

Approach 2: LEFT JOIN with NULL Filter (O(n + m) time, O(1) extra space)

This approach uses a LEFT JOIN between Students and Departments on department_id. A LEFT JOIN keeps every student row, even if no matching department exists. When a match is missing, the department columns become NULL. Filtering rows where the joined department ID is NULL directly identifies invalid references. This method is widely used when solving SQL join problems because it clearly expresses the relationship between the two tables. The query performs a linear scan with join matching, giving O(n + m) time complexity and O(1) additional space beyond query execution.

Both approaches rely on fundamental relational database concepts: verifying foreign key relationships and detecting missing matches between tables. Problems like this frequently appear in SQL interview rounds to test your understanding of joins and filtering conditions.

Recommended for interviews: The LEFT JOIN solution is typically preferred. It clearly shows how unmatched rows appear during a join, which demonstrates strong understanding of relational queries. The NOT IN subquery is shorter and also correct, but interviewers often expect candidates to reason about joins when solving SQL data integrity problems.