Number of Unique Subjects Taught by Each Teacher

Difficulty: Easy | Acceptance: 89.20% | Paid: No Topics: Database

Table: Teacher

(teacher_id, subject_id) is the primary key (combination of columns with unique values) of this table. Each row in the 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.

Return the result table in any order.

The result format is in the following example.

• Examples
• Constraints
• Approach 1: Hash Map Grouping
• Approach 2: Sorting and Iteration

Examples

Example 1:

Input: Teacher table:

Output:

Explanation: Teacher 1 teaches subjects 2 and 3 (subject 2 is taught in two different departments, but we count it only once). Teacher 2 teaches subjects 1, 2, and 3.

Constraints

The Teacher table may contain duplicate rows for the same teacher and subject in different departments.

Approach 1: Hash Map Grouping

Intuition We can iterate through the list of teacher records and use a hash map (or dictionary) to keep track of the unique subject IDs for each teacher ID. The key will be the teacher_id, and the value will be a set of subject_ids. Finally, we count the size of each set.

Steps

• Initialize an empty hash map where keys are integers (teacher_id) and values are sets of integers (subject_id).
• Iterate through each record in the input data.
• For each record, extract the teacher_id and subject_id.
• Add the subject_id to the set corresponding to the teacher_id in the map.
• After processing all records, iterate through the map and create a result list containing [teacher_id, count_of_unique_subjects].

from typing import List

class Solution:
    def countUniqueSubjects(self, teachers: List[List[int]]) -> List[List[int]]:
        subject_map = {}
        
        for teacher_id, subject_id, _ in teachers:
            if teacher_id not in subject_map:
                subject_map[teacher_id] = set()
            subject_map[teacher_id].add(subject_id)
            
        result = []
        for teacher_id, subjects in subject_map.items():
            result.append([teacher_id, len(subjects)])
            
        return result

Complexity

• Time: O(N) where N is the number of rows in the Teacher table. We iterate through the list once, and set operations are O(1) on average.
• Space: O(N) to store the unique subjects for each teacher in the hash map.
• Notes: This is the most efficient approach for time complexity, trading off space for speed.

Approach 2: Sorting and Iteration

Intuition If we sort the records first by teacher_id and then by subject_id, all records for a specific teacher will be grouped together, and their subjects will be in sorted order. We can then iterate through the sorted list and count how many times the subject_id changes for each teacher.

Steps

• Sort the input list of records. The primary sort key is teacher_id, and the secondary sort key is subject_id.
• Initialize an empty result list.
• Iterate through the sorted records.
• Keep track of the current teacher_id and the last seen subject_id.
• If the teacher_id changes from the previous record, push the previous teacher’s count to the result and reset the count.
• If the subject_id changes from the previous record (and teacher_id is the same), increment the count.
• Handle the edge case for the last teacher in the list after the loop finishes.

from typing import List

class Solution:
    def countUniqueSubjects(self, teachers: List[List[int]]) -> List[List[int]]:
        if not teachers:
            return []
            
        # Sort by teacher_id, then subject_id
        teachers.sort(key=lambda x: (x[0], x[1]))
        
        result = []
        curr_teacher = teachers[0][0]
        curr_subject = None
        count = 0
        
        for t_id, s_id, _ in teachers:
            if t_id != curr_teacher:
                result.append([curr_teacher, count])
                curr_teacher = t_id
                count = 1
                curr_subject = s_id
            elif s_id != curr_subject:
                count += 1
                curr_subject = s_id
                # If it is the very first record of the group, count starts at 1
                if count == 0: count = 1
        
        # Append the last teacher
        result.append([curr_teacher, count])
        
        return result

Complexity

• Time: O(N log N) due to the sorting step, where N is the number of rows. The iteration itself is O(N).
• Space: O(1) or O(N) depending on the sorting algorithm’s space complexity (e.g., quicksort is O(log N) stack space, mergesort is O(N)). We exclude the space required for the output.
• Notes: This approach is useful if memory is extremely constrained and we cannot afford the overhead of a hash map, though it is generally slower than the hash map approach due to sorting.