Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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.

Solution

Method 1 - SQL Anti-Join (NOT EXISTS)

Intuition

We want to find students whose department_id does not exist in the Departments table. This is a classic anti-join problem, solved with NOT EXISTS or LEFT JOIN ... WHERE ... IS NULL in SQL.

Approach

  1. For each student, check if their department_id is missing from the Departments table.
  2. Return the student’s id and name.

Code

1
2
3
4
5

SELECT s.id, s.name
FROM Students s
WHERE NOT EXISTS (
  SELECT 1 FROM Departments d WHERE d.id = s.department_id
);
1

// Use SQL query above in your JDBC/ORM code. No special Java logic needed.
1
2

# Assuming students and departments are pandas DataFrames
invalid = students[~students['department_id'].isin(departments['id'])][['id', 'name']]

Complexity

  • ⏰ Time complexity: O(N + M) where N = #students, M = #departments
  • 🧺 Space complexity: O(N + M)