LeetCode 2356 - Number of Unique Subjects Taught by Each Teacher

The problem requires calculating the number of unique subjects each teacher teaches in a university, given a table that maps teachers to subjects and departments. Each row in the Teacher table represents a specific combination of a teacher, a subject, and a department.

leetcodeeasydatabase

LeetCode Problem 2356

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem requires calculating the number of unique subjects each teacher teaches in a university, given a table that maps teachers to subjects and departments. Each row in the Teacher table represents a specific combination of a teacher, a subject, and a department. A teacher may teach the same subject in multiple departments, but for this problem, we only care about counting each subject once per teacher, regardless of the department.

The input is a SQL table Teacher with three columns: teacher_id, subject_id, and dept_id. The primary key is (subject_id, dept_id), meaning that no two rows can have the same subject in the same department, but multiple teachers may teach the same subject in different departments.

The expected output is a table with two columns: teacher_id and cnt, where cnt represents the number of unique subjects that teacher teaches. The order of the rows does not matter.

Important edge considerations include teachers who teach multiple subjects across multiple departments, teachers who teach only one subject, and the fact that duplicate subject-department entries for the same teacher must be counted only once per subject.

Approaches

Brute Force

A naive approach would be to iterate through the entire Teacher table, and for each teacher, maintain a list of all subjects they teach. After processing all rows, remove duplicates from the list of subjects for each teacher, and then count the number of unique subjects. This works because we are explicitly counting distinct subjects, but it is inefficient as it requires additional data structures to store all subjects and potentially repeated scanning for duplicates.

Optimal Approach

The optimal approach leverages SQL's COUNT(DISTINCT ...) aggregate function. Instead of manually removing duplicates or iterating row by row, we can group by teacher_id and directly count the number of unique subject_ids for each teacher. This is efficient because SQL engines are optimized for grouping and counting distinct values.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Iterate through table, store subjects in lists, remove duplicates
Optimal O(n) O(n) Use SQL GROUP BY and COUNT(DISTINCT subject_id) to compute result efficiently

Algorithm Walkthrough

  1. Group by teacher: We need to process data per teacher. SQL GROUP BY teacher_id allows aggregation for each teacher.
  2. Count unique subjects: Within each group, count the number of distinct subject_ids using COUNT(DISTINCT subject_id). This ensures that repeated subject entries in multiple departments are counted only once.
  3. Return results: Output two columns: teacher_id and the computed count as cnt. SQL will handle the ordering; since the problem allows any order, we do not need an explicit ORDER BY.

Why it works: The GROUP BY guarantees that each teacher is considered independently, and COUNT(DISTINCT subject_id) guarantees that repeated subjects across departments are only counted once. Therefore, each teacher's row correctly reflects the number of unique subjects they teach.

Python Solution

Since this is a database problem, a Python solution would normally use an ORM or execute raw SQL. Here is an example using SQLite via Python:

import sqlite3
from typing import List, Tuple

def number_of_unique_subjects_teachers(conn: sqlite3.Connection) -> List[Tuple[int, int]]:
    query = """
    SELECT teacher_id, COUNT(DISTINCT subject_id) AS cnt
    FROM Teacher
    GROUP BY teacher_id
    """
    cursor = conn.cursor()
    cursor.execute(query)
    result = cursor.fetchall()
    return result

Explanation: The Python code executes the SQL query described in the algorithm. The query groups rows by teacher_id and counts distinct subjects using SQL's COUNT(DISTINCT subject_id). The result is fetched and returned as a list of tuples, where each tuple contains a teacher ID and their unique subject count.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "log"
)

type TeacherCount struct {
    TeacherID int
    Count     int
}

func NumberOfUniqueSubjectsTeachers(db *sql.DB) ([]TeacherCount, error) {
    query := `
    SELECT teacher_id, COUNT(DISTINCT subject_id) AS cnt
    FROM Teacher
    GROUP BY teacher_id
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results []TeacherCount
    for rows.Next() {
        var t TeacherCount
        if err := rows.Scan(&t.TeacherID, &t.Count); err != nil {
            return nil, err
        }
        results = append(results, t)
    }
    return results, nil
}

Go Notes: This Go solution mirrors the Python solution but uses Go's database/sql package. We define a struct TeacherCount to store the results. The rows.Next() iteration fetches each row, and rows.Scan() extracts the teacher ID and count. Go handles nil values and empty results gracefully, returning an empty slice if no rows exist.

Worked Examples

Example Input

Teacher table:
+------------+------------+---------+
| teacher_id | subject_id | dept_id |
+------------+------------+---------+
| 1          | 2          | 3       |
| 1          | 2          | 4       |
| 1          | 3          | 3       |
| 2          | 1          | 1       |
| 2          | 2          | 1       |
| 2          | 3          | 1       |
| 2          | 4          | 1       |
+------------+------------+---------+

Execution

Step 1: Group by teacher_id.

Step 2: Count distinct subject_id in each group.

teacher_id distinct subject_id count
1 2, 3 2
2 1, 2, 3, 4 4

Step 3: Output result table.

+------------+-----+
| teacher_id | cnt |
+------------+-----+
| 1          | 2   |
| 2          | 4   |
+------------+-----+

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed once by SQL engine, grouping and counting distinct subjects
Space O(n) SQL engine may use temporary structures proportional to input size for grouping

The reasoning is that SQL optimizations for aggregation and distinct counting allow this problem to scale linearly with the number of rows in practice.

Test Cases

# example case
assert number_of_unique_subjects_teachers(conn) == [(1, 2), (2, 4)]  # standard example

# teacher teaches one subject in multiple departments
assert number_of_unique_subjects_teachers(conn) == [(3, 1)]  # subject counted once

# teacher teaches multiple subjects in one department
assert number_of_unique_subjects_teachers(conn) == [(4, 3)]  # counts all subjects

# no teachers
assert number_of_unique_subjects_teachers(conn) == []  # empty input

# multiple teachers with overlapping subjects
assert number_of_unique_subjects_teachers(conn) == [(5, 2), (6, 3)]  # multiple groups
Test Why
example case Validates typical input
single subject, multiple departments Ensures duplicate subjects are counted once
multiple subjects, one department Validates counting all unique subjects
no teachers Checks empty table handling
multiple teachers, overlapping subjects Ensures correct grouping and counting

Edge Cases

Edge Case 1: Teacher with no subjects

If a teacher exists in the system but has no subjects assigned, SQL GROUP BY will naturally exclude them. The implementation correctly returns only teachers with at least one subject.

Edge Case 2: Duplicate subject-department entries

The primary key guarantees no duplicate subject-department rows. This prevents overcounting. Counting distinct subjects still handles any duplicates robustly.

Edge Case 3: Large dataset

With thousands of teachers and subjects, the solution leverages the SQL engine's optimized aggregation. Both Python and Go implementations rely on the database for computation, ensuring scalability without loading all rows into application memory unnecessarily.