{x}
blog image

Number of Unique Subjects Taught by Each Teacher

Table: Teacher

+-------------+------+
| Column Name | Type |
+-------------+------+
| teacher_id  | int  |
| subject_id  | int  |
| dept_id     | int  |
+-------------+------+
(subject_id, dept_id) is the primary key (combinations of columns with unique values) of this table.
Each row in this table indicates that the teacher with teacher_id teaches the subject subject_id in the department dept_id.

 

Write a solution to calculate the number of unique subjects each teacher teaches in the university.

Return the result table in any order.

The result format is shown in the following example.

 

Example 1:

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       |
+------------+------------+---------+
Output:  
+------------+-----+
| teacher_id | cnt |
+------------+-----+
| 1          | 2   |
| 2          | 4   |
+------------+-----+
Explanation: 
Teacher 1:
  - They teach subject 2 in departments 3 and 4.
  - They teach subject 3 in department 3.
Teacher 2:
  - They teach subject 1 in department 1.
  - They teach subject 2 in department 1.
  - They teach subject 3 in department 1.
  - They teach subject 4 in department 1.

Solution Explanation

This problem requires us to find the number of unique subjects taught by each teacher. The Teacher table provides teacher IDs, subject IDs, and department IDs. We need to group the data by teacher_id and count the distinct subject_id for each teacher.

Approach

The most efficient way to solve this is using SQL's GROUP BY and COUNT(DISTINCT ...) clauses.

  1. GROUP BY teacher_id: This groups the rows in the Teacher table based on the teacher_id. All rows with the same teacher_id will be grouped together.

  2. COUNT(DISTINCT subject_id): For each group (each teacher), this counts the number of unique subject_id values. The DISTINCT keyword ensures that each subject is counted only once, even if the teacher teaches the same subject in multiple departments.

  3. AS cnt: This assigns the alias "cnt" to the resulting count column for better readability.

Code (MySQL)

SELECT teacher_id, COUNT(DISTINCT subject_id) AS cnt
FROM Teacher
GROUP BY teacher_id;

Time and Space Complexity Analysis

  • Time Complexity: O(N log N), where N is the number of rows in the Teacher table. The GROUP BY operation generally has a time complexity of O(N log N) due to the sorting involved (although specific database implementations might optimize this). The COUNT(DISTINCT ...) also adds to the processing time, but it's still within the same order of magnitude.

  • Space Complexity: O(M), where M is the number of unique teachers. The space complexity is determined by the size of the intermediate result set generated by the GROUP BY operation. This result set stores the count of distinct subjects for each teacher. In the worst case, M could be equal to N (if each teacher teaches a unique set of subjects). However, in practice, M is likely to be significantly smaller than N.

This SQL query provides a concise and efficient solution to the problem. The use of COUNT(DISTINCT subject_id) directly addresses the requirement of counting unique subjects, and the GROUP BY clause effectively aggregates the data by teacher. No extra loops or iterations are needed in the code itself because the database system handles these operations internally.