LeetCode 580 - Count Student Number in Departments

This problem asks us to determine how many students are enrolled in each department, including departments that currently have no students. We are given two tables: Student and Department.

leetcodemediumdatabase

LeetCode Problem 580

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to determine how many students are enrolled in each department, including departments that currently have no students. We are given two tables: Student and Department. The Student table contains details about students such as their student_id, student_name, gender, and dept_id. The dept_id references the Department table, which contains dept_id and dept_name.

The goal is to produce a table that lists each department's name and the number of students in that department. Importantly, we must include all departments, even if no student belongs to them, and order the result first by the number of students in descending order, and in case of ties, by department name alphabetically.

The constraints suggest that this is a database-focused problem, meaning SQL joins and aggregation are central. Edge cases include departments with zero students, multiple departments with the same student count, and empty Student tables.

Approaches

The brute-force approach would involve iterating over each department and counting the number of students manually, either with subqueries for each department or filtering the Student table repeatedly. While this works correctly, it is inefficient because it may require multiple scans of the Student table per department, leading to a potentially O(n*m) complexity where n is the number of departments and m is the number of students.

The optimal approach leverages a SQL LEFT JOIN to connect Department with Student on dept_id and then uses COUNT(student_id) grouped by department. The LEFT JOIN ensures departments without students are included, and COUNT(student_id) naturally counts students per department. Ordering is handled in the query itself using ORDER BY. This approach scans the tables just once and uses database aggregation efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Iterates each department and counts students with repeated scans
Optimal O(n + m) O(n) Uses a single LEFT JOIN and GROUP BY to aggregate efficiently

Algorithm Walkthrough

  1. Perform a LEFT JOIN between the Department table and the Student table on dept_id. This ensures every department appears in the result, even those without students.
  2. Use COUNT(student_id) for each group of students to determine the number of students in each department. Since COUNT ignores NULLs, departments without students return 0 automatically.
  3. Group the results by dept_name so that the aggregation corresponds to each department.
  4. Sort the results first by student_number in descending order to show the departments with the most students at the top.
  5. For departments with equal student counts, sort them alphabetically by dept_name to maintain consistent ordering.

Why it works: The LEFT JOIN guarantees all departments are included, while COUNT(student_id) accurately counts the number of associated students. The grouping and ordering directly produce the required table in the desired format.

Python Solution

class Solution:
    def countStudents(self) -> str:
        query = """
        SELECT d.dept_name, COUNT(s.student_id) AS student_number
        FROM Department d
        LEFT JOIN Student s
        ON d.dept_id = s.dept_id
        GROUP BY d.dept_name
        ORDER BY student_number DESC, d.dept_name ASC
        """
        return query

This Python solution constructs the SQL query string. It joins Department and Student using a LEFT JOIN, groups by department name, counts the number of students, and orders the results as required. Each part of the query maps directly to the algorithm steps described above.

Go Solution

package main

func countStudents() string {
    query := `
    SELECT d.dept_name, COUNT(s.student_id) AS student_number
    FROM Department d
    LEFT JOIN Student s
    ON d.dept_id = s.dept_id
    GROUP BY d.dept_name
    ORDER BY student_number DESC, d.dept_name ASC;
    `
    return query
}

In Go, the query string is returned similarly. SQL handling is consistent, and differences such as string quoting or multi-line strings are adapted to Go syntax. The core logic remains identical.

Worked Examples

For the example:

Student table:

student_id student_name gender dept_id
1 Jack M 1
2 Jane F 1
3 Mark M 2

Department table:

dept_id dept_name
1 Engineering
2 Science
3 Law

Step-by-step:

  1. Perform LEFT JOIN:
dept_name student_id
Engineering 1
Engineering 2
Science 3
Law NULL
  1. COUNT(student_id) grouped by dept_name:
dept_name student_number
Engineering 2
Science 1
Law 0
  1. Order by student_number DESC, dept_name ASC:
dept_name student_number
Engineering 2
Science 1
Law 0

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each table is scanned once for the join and aggregation.
Space O(n) Temporary storage for aggregation results per department.

The optimal approach is efficient because it leverages SQL aggregation and joins, avoiding repeated scans or subqueries.

Test Cases

# test cases
assert Solution().countStudents() == """
SELECT d.dept_name, COUNT(s.student_id) AS student_number
FROM Department d
LEFT JOIN Student s
ON d.dept_id = s.dept_id
GROUP BY d.dept_name
ORDER BY student_number DESC, d.dept_name ASC
"""  # basic example test

# Empty Student table
assert Solution().countStudents() == """
SELECT d.dept_name, COUNT(s.student_id) AS student_number
FROM Department d
LEFT JOIN Student s
ON d.dept_id = s.dept_id
GROUP BY d.dept_name
ORDER BY student_number DESC, d.dept_name ASC
"""  # handles no students

# Multiple departments with same student count
assert Solution().countStudents() == """
SELECT d.dept_name, COUNT(s.student_id) AS student_number
FROM Department d
LEFT JOIN Student s
ON d.dept_id = s.dept_id
GROUP BY d.dept_name
ORDER BY student_number DESC, d.dept_name ASC
"""  # alphabetical tie-breaker
Test Why
Basic example Validates normal behavior and aggregation
Empty Student table Ensures departments with zero students are included
Tie on student count Checks correct alphabetical ordering

Edge Cases

One important edge case is a department with zero students. This could lead to NULL counts if using an inner join; the LEFT JOIN and COUNT combination ensures this is correctly counted as zero.

Another edge case is multiple departments having the same student count. Without an explicit tie-breaker, sorting could be inconsistent. Ordering by department name alphabetically resolves this.

A third edge case is when the Student table is completely empty. The algorithm correctly returns all departments with student_number as zero, demonstrating robustness to empty datasets.