Classes With at Least 5 Students

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

Table: Courses +-------------+---------+ | Column Name | Type | +-------------+---------+ | student | varchar | | class | varchar | +-------------+---------+ (student, class) is the primary key (combination of columns with unique values) of this table. Each row of this table indicates the name of a student and the class in which they are enrolled.

Write a solution to find all the classes that have at least 5 students.

Return the result table in any order.

The result format is in the following example.

• Examples
• Constraints
• Hash Map Counting
• Sorting and Linear Scan
• Stream / Functional

Examples

Input: Courses table: +---------+----------+ | student | class | +---------+----------+ | A | Math | | B | Math | | C | Math | | D | Math | | E | Math | | F | Math | | G | Physics | | H | Physics | | I | Physics | +---------+----------+

Output: +---------+ | class | +---------+ | Math | +---------+

Explanation:

• Math has 6 students, so we include it.
• Physics has 3 students, so we do not include it.

Constraints

- The Courses table may have up to 1000 rows.

Hash Map Counting

Intuition Use a hash map to count the number of students in each class, then filter classes with at least 5 students.

Steps

• Iterate through each course enrollment
• Increment the count for each class in a hash map
• Filter classes with count >= 5

from typing import List
from collections import defaultdict

class Solution:
    def findClasses(self, courses: List[List[str]]) -> List[str]:
        count = defaultdict(int)
        for student, course in courses:
            count[course] += 1
        return [course for course, cnt in count.items() if cnt >= 5]

Complexity

• Time: O(n) where n is the number of enrollments
• Space: O(k) where k is the number of unique classes
• Notes: Most efficient approach for this problem

Sorting and Linear Scan

Intuition Sort the enrollments by class name, then count students for each class in a single pass.

Steps

• Sort courses by class name
• Iterate through sorted list, counting consecutive entries with the same class
• Add classes with count >= 5 to result

from typing import List

class Solution:
    def findClasses(self, courses: List[List[str]]) -> List[str]:
        courses.sort(key=lambda x: x[1])
        result = []
        i = 0
        n = len(courses)
        while i < n:
            current_class = courses[i][1]
            cnt = 0
            while i < n and courses[i][1] == current_class:
                cnt += 1
                i += 1
            if cnt >= 5:
                result.append(current_class)
        return result

Complexity

• Time: O(n log n) due to sorting
• Space: O(1) extra space (or O(n) if sorting is not in-place)
• Notes: Useful when you need sorted output or when hash operations are expensive

Stream / Functional

Intuition Use functional programming constructs like streams, reduce, and filter to count and filter in a declarative style.

Steps

• Use stream/reduce to count students per class
• Filter classes with count >= 5
• Collect results

from typing import List
from collections import Counter

class Solution:
    def findClasses(self, courses: List[List[str]]) -> List[str]:
        classes = [course for _, course in courses]
        count = Counter(classes)
        return [course for course, cnt in count.items() if cnt >= 5]

Complexity

• Time: O(n) for counting and filtering
• Space: O(k) where k is the number of unique classes
• Notes: More readable and declarative, but may have slight overhead compared to imperative approach