Skip to main content
Talentd

Students With Invalid Departments - Solution & Explanation

EasyPremiumFree on FleetCodeDatabase4 min readAsked at: Amazon
Practice this problem

Problem Statement

Table: Departments

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| name          | varchar |
+---------------+---------+
In SQL, id is the primary key of this table.
The table has information about the id of each department of a university.

 

Table: Students

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| name          | varchar |
| department_id | int     |
+---------------+---------+
In SQL, id is the primary key of this table.
The table has information about the id of each student at a university and the id of the department he/she studies at.

 

Find the id and the name of all students who are enrolled in departments that no longer exist.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Departments table:
+------+--------------------------+
| id   | name                     |
+------+--------------------------+
| 1    | Electrical Engineering   |
| 7    | Computer Engineering     |
| 13   | Bussiness Administration |
+------+--------------------------+
Students table:
+------+----------+---------------+
| 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             |
+------+----------+---------------+
Output: 
+------+----------+
| id   | name     |
+------+----------+
| 2    | John     |
| 7    | Daiana   |
| 4    | Jasmine  |
| 3    | Steve    |
+------+----------+
Explanation: 
John, Daiana, Steve, and Jasmine are enrolled in departments 14, 33, 74, and 77 respectively. department 14, 33, 74, and 77 do not exist in the Departments table.

Approach Overview

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.

Approach 1: Subquery

We can directly use a subquery to find all students who are not in the Departments table.

Code

MySQL

MySQL

Try this approach in the editor →

Approach 2: Left Join

We can also use a left join to join the Students table with the Departments table on the condition of Students.department_id = Departments.id, and then filter out the students whose Departments.id is NULL.

Code

MySQL

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Subquery—
Left Join—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Subquery with NOT INO(n + m)O(m)Simple filtering when you want to compare against a set of valid department IDs
LEFT JOIN with NULL filterO(n + m)O(1)Preferred SQL pattern for detecting unmatched rows between two related tables

Video Solution

LeetCode 1350 Interview SQL Question with Detailed Explanation | Practice SQL • Everyday Data Science • 7,249 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Students With Invalid Departments easy or hard?
Students With Invalid Departments is classified as an Easy database problem. It mainly tests basic SQL knowledge, specifically joins, subqueries, and filtering rows based on missing matches between tables.
Students With Invalid Departments Python/Java solution
This problem is solved using SQL rather than Python or Java logic. The solution typically uses a MySQL query with either a NOT IN subquery or a LEFT JOIN to identify students whose department_id does not exist in the Departments table.
How to solve Students With Invalid Departments in O(n)?
Use a LEFT JOIN between Students and Departments on department_id and filter rows where the department record is NULL. The database performs a linear scan with join matching, which effectively results in O(n + m) time complexity for the two tables.
What is the best approach for Students With Invalid Departments?
The LEFT JOIN approach is typically the best. Join the Students table with Departments on department_id and filter rows where the department side is NULL. This directly exposes students whose department reference does not exist. It runs in O(n + m) time depending on table sizes.
Is Students With Invalid Departments asked at Google/Amazon/Meta?
SQL join and data integrity problems like this commonly appear in database screening rounds at companies such as Amazon, Meta, and Google. They test your understanding of joins, filtering, and detecting missing relationships between tables.
What data structure is used in Students With Invalid Departments?
The problem uses relational database tables rather than in-memory data structures. SQL engines internally use indexing, hash joins, or nested loop joins to match rows between Students and Departments.
What is the time complexity of Students With Invalid Departments?
Both common solutions run in O(n + m) time, where n is the number of students and m is the number of departments. The database scans the Students table and checks membership using either a join or a subquery result set.

Ready to solve this problem?

Practice Students With Invalid Departments with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary