# LeetCode 580: Count Student Number in Departments

## Problem Restatement

We are given two tables: `Student` and `Department`.

Each student belongs to one department. We need to report every department name and the number of students majoring in that department.

Departments with no students must still appear in the result with count `0`.

The result should be ordered by `student_number` in descending order. If two departments have the same number of students, order them by `dept_name` alphabetically.

## Tables

### Student

| Column | Type | Meaning |
|---|---|---|
| `student_id` | int | Student ID |
| `student_name` | varchar | Student name |
| `gender` | varchar | Student gender |
| `dept_id` | int | Department ID |

`student_id` is the primary key.

### Department

| Column | Type | Meaning |
|---|---|---|
| `dept_id` | int | Department ID |
| `dept_name` | varchar | Department name |

`dept_id` is the primary key.

## Example

Input:

`Student`

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

`Department`

| dept_id | dept_name |
|---:|---|
| 1 | Engineering |
| 2 | Science |
| 3 | Law |

Output:

| dept_name | student_number |
|---|---:|
| Engineering | 2 |
| Science | 1 |
| Law | 0 |

`Engineering` has two students.

`Science` has one student.

`Law` has no students, but it still appears because every department must be reported.

## First Thought: Group Student Only

A first attempt might be:

```sql
SELECT
    dept_id,
    COUNT(*) AS student_number
FROM Student
GROUP BY dept_id;
```

This counts students by department ID.

But it has two problems.

First, it returns `dept_id`, not `dept_name`.

Second, it misses departments with no students. If a department has no matching row in `Student`, it cannot appear when we select only from `Student`.

So we must start from `Department`, not from `Student`.

## Key Insight

The output needs all departments.

That means `Department` should be the left table.

Then we attach matching students with a `LEFT JOIN`.

A `LEFT JOIN` keeps every department row. If there are no matching students, the student columns become `NULL`.

Then we count `student_id`.

This matters:

```sql
COUNT(s.student_id)
```

counts only non-null student IDs.

For a department with no students, `s.student_id` is `NULL`, so the count becomes `0`.

Do not use:

```sql
COUNT(*)
```

after a `LEFT JOIN`, because that would count the department row itself and return `1` for departments with no students.

## Algorithm

1. Start from `Department`.
2. `LEFT JOIN` with `Student` using `dept_id`.
3. Group by department.
4. Count `Student.student_id`.
5. Return `dept_name` and the count as `student_number`.
6. Sort by `student_number DESC`, then `dept_name ASC`.

## Correctness

The query starts from `Department`, so every department is considered.

The `LEFT JOIN` attaches all students whose `dept_id` matches the department's `dept_id`. If a department has no students, the joined student columns are `NULL`, but the department row remains in the result.

After grouping by department, each group contains exactly the joined rows for one department. Counting `s.student_id` counts exactly the students in that department because `student_id` is non-null for real student rows and null for the synthetic unmatched row created by the `LEFT JOIN`.

Therefore, each department receives the correct student count, including `0` for departments without students.

The `ORDER BY` clause sorts first by the count from largest to smallest, then by department name alphabetically when counts tie. This matches the required output order.

## Complexity

Let:

```text
D = number of departments
S = number of students
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(D + S + D log D)` | Join and group the rows, then sort departments |
| Space | `O(D)` | Store one aggregate result per department |

The exact execution plan depends on the SQL engine and available indexes.

## Implementation

```sql
SELECT
    d.dept_name,
    COUNT(s.student_id) AS student_number
FROM Department AS d
LEFT JOIN Student AS s
    ON d.dept_id = s.dept_id
GROUP BY d.dept_id, d.dept_name
ORDER BY student_number DESC, d.dept_name ASC;
```

## Code Explanation

This starts from the table that must be fully preserved:

```sql
FROM Department AS d
```

This attaches students when they exist:

```sql
LEFT JOIN Student AS s
    ON d.dept_id = s.dept_id
```

The `LEFT JOIN` is the reason departments with zero students still appear.

This groups all joined rows for the same department:

```sql
GROUP BY d.dept_id, d.dept_name
```

We group by both `dept_id` and `dept_name` to make the query explicit and portable.

This counts only real student rows:

```sql
COUNT(s.student_id) AS student_number
```

If there are no students, `s.student_id` is `NULL`, so the count is `0`.

Finally, this applies the required ordering:

```sql
ORDER BY student_number DESC, d.dept_name ASC;
```

## Testing

Sample data:

```sql
CREATE TABLE Student (
    student_id INT PRIMARY KEY,
    student_name VARCHAR(255),
    gender VARCHAR(10),
    dept_id INT
);

CREATE TABLE Department (
    dept_id INT PRIMARY KEY,
    dept_name VARCHAR(255)
);

INSERT INTO Student (student_id, student_name, gender, dept_id) VALUES
(1, 'Jack', 'M', 1),
(2, 'Jane', 'F', 1),
(3, 'Mark', 'M', 2);

INSERT INTO Department (dept_id, dept_name) VALUES
(1, 'Engineering'),
(2, 'Science'),
(3, 'Law');
```

Query:

```sql
SELECT
    d.dept_name,
    COUNT(s.student_id) AS student_number
FROM Department AS d
LEFT JOIN Student AS s
    ON d.dept_id = s.dept_id
GROUP BY d.dept_id, d.dept_name
ORDER BY student_number DESC, d.dept_name ASC;
```

Expected result:

| dept_name | student_number |
|---|---:|
| Engineering | 2 |
| Science | 1 |
| Law | 0 |

Additional test cases:

| Case | Expected behavior |
|---|---|
| Department has no students | Included with `0` |
| Two departments have same count | Ordered by `dept_name` alphabetically |
| All departments have no students | All returned with `0` |
| One department has many students | It appears first |
| Student table is empty | Every department appears with `0` |