Domain 1EasyCORE

Students With Invalid Departments

The problem "Students With Invalid Departments" involves identifying students who are enrolled in departments that no longer exist. Given two tables: `students` and `departments`, we need to find the list of student names who are associated with departments that do not have a corresponding entry in the `departments` table.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 1

1350. Students With Invalid Departments

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 90.4%


Problem Breakdown

The problem “Students With Invalid Departments” involves identifying students who are enrolled in departments that no longer exist. Given two tables: students and departments, we need to find the list of student names who are associated with departments that do not have a corresponding entry in the departments table.

  • Inputs:

    • students: A table with columns student_id (primary key) and name.
    • departments: A table with columns department_id (primary key).
  • Outputs:

    • A list of student names who are enrolled in invalid departments.
  • Implicit Constraints/Edge Cases:

    • The students table may contain students with duplicate department IDs, but each student ID is unique.
    • The departments table may be empty, meaning all students are in invalid departments.
    • There might be no students at all (empty students table).

Intuition

A brute-force approach would involve iterating over each student and checking if their department exists in the departments table. This would require a nested loop, resulting in a time complexity of O(n * m), where n is the number of students and m is the number of departments.

The key insight to improve this solution is to use SQL’s set operations or joins to efficiently find students with invalid departments without needing nested loops. Specifically, we can use a LEFT JOIN to identify students whose department IDs do not match any in the departments table.

Approach

  1. Identify Invalid Departments: Use a subquery to select all department_ids from the students table that are not present in the departments table.
  2. Filter Students: Perform a LEFT JOIN between the students and departments tables on department_id. Filter the results to include only those students whose department is invalid (i.e., where the join condition fails).
  3. Select Student Names: Extract the names of these students.

Algorithm Steps:

  1. Write a subquery to find all department_ids in students that are not in departments.
  2. Use this subquery to filter students with invalid departments.
  3. Select and return the names of these students.

Complexity Analysis

  • Time Complexity: O(n + m), where n is the number of rows in the students table and m is the number of rows in the departments table. The join operation and subquery are linear with respect to the size of each table.

  • Space Complexity: O(k), where k is the number of students with invalid departments. This space is used for storing the result set.

Solution

# SQL query to find students with invalid departments
SELECT s.name 
FROM students s
LEFT JOIN departments d ON s.department_id = d.department_id
WHERE d.department_id IS NULL;

Edge Cases Handled

  • Empty departments Table: If the departments table is empty, all students will have an invalid department, and the query will return all student names.

  • Empty students Table: If there are no students, the query will naturally return an empty result set.

  • Duplicate Department IDs in students: The query handles duplicates by filtering based on the absence of a matching department ID, ensuring each student is only listed once if their department is invalid.