LeetCode 596 - Classes With at Least 5 Students

This problem is asking us to find classes in a school database that have at least five students enrolled. The input is a table named Courses with two columns: student and class. Each row represents one student being enrolled in one class.

leetcodeeasydatabase

LeetCode Problem 596

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem is asking us to find classes in a school database that have at least five students enrolled. The input is a table named Courses with two columns: student and class. Each row represents one student being enrolled in one class. The primary key of this table is the combination of (student, class), so there are no duplicate entries for the same student in the same class.

The output should be a table with a single column class, containing the names of classes that have five or more students. The order of the output does not matter. The constraints indicate that there are no null values and each student-class pair is unique, so we do not need to handle duplicates or missing data.

Important edge cases include classes with exactly five students, classes with only one student, or a situation where no class has five students. We must ensure the query counts students per class accurately and filters correctly.

Approaches

A brute-force approach would iterate over all classes, count the number of students manually for each class, and then filter out those with fewer than five students. While correct, this approach is cumbersome in SQL and inefficient for large datasets because it may require multiple passes over the table.

The key insight for the optimal solution is that SQL provides aggregation functions. By grouping the rows by class and counting the number of students in each group, we can use a HAVING clause to filter classes with at least five students. This approach is simple, efficient, and directly expresses the requirement.

Approach Time Complexity Space Complexity Notes
Brute Force O(n*m) O(1) Count students for each class manually, may require multiple scans of the table
Optimal O(n) O(k) Use GROUP BY to aggregate student counts by class, filter with HAVING, single scan of table

Algorithm Walkthrough

  1. Start with the Courses table, which contains rows of (student, class) pairs.
  2. Group all rows by the class column. This creates a set of groups where each group contains all students enrolled in that particular class.
  3. For each group, count the number of students. This gives a total student count per class.
  4. Use a HAVING clause to filter groups where the count of students is greater than or equal to five.
  5. Select only the class column from the resulting groups. This produces the final table of classes with at least five students.

Why it works: Grouping guarantees that all students of the same class are collected together. Counting ensures that we accurately measure class size, and the HAVING filter guarantees only classes meeting the minimum threshold are included. SQL handles this efficiently with a single aggregation operation.

Python Solution

# Since this is a SQL problem, Python solution here is a representation of executing SQL in Python
from typing import List
import sqlite3

def classes_with_at_least_five_students(conn: sqlite3.Connection) -> List[str]:
    query = """
    SELECT class
    FROM Courses
    GROUP BY class
    HAVING COUNT(student) >= 5;
    """
    cursor = conn.cursor()
    cursor.execute(query)
    result = [row[0] for row in cursor.fetchall()]
    return result

This Python implementation executes the SQL query directly on a database connection. We group by class, count the students, filter using HAVING, and extract the resulting class names into a Python list.

Go Solution

package main

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

func ClassesWithAtLeastFiveStudents(db *sql.DB) ([]string, error) {
    query := `
    SELECT class
    FROM Courses
    GROUP BY class
    HAVING COUNT(student) >= 5;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var classes []string
    for rows.Next() {
        var className string
        if err := rows.Scan(&className); err != nil {
            return nil, err
        }
        classes = append(classes, className)
    }
    return classes, nil
}

In Go, we use database/sql to execute the SQL query. We iterate over the result set with rows.Next(), scan each class name, and append it to a slice. Error handling ensures that any issues with query execution or row scanning are captured.

Worked Examples

For the example provided:

Courses table:
| student | class    |
|---------|---------|
| A       | Math    |
| B       | English |
| C       | Math    |
| D       | Biology |
| E       | Math    |
| F       | Computer|
| G       | Math    |
| H       | Math    |
| I       | Math    |

Step by step:

  1. Group by class:
class students
Math A, C, E, G, H, I
English B
Biology D
Computer F
  1. Count students per class:
class count
Math 6
English 1
Biology 1
Computer 1
  1. Filter with HAVING COUNT(student) >= 5:
class
Math

Complexity Analysis

Measure Complexity Explanation
Time O(n) The table is scanned once to group by class and count students.
Space O(k) Space is used to store the aggregation of k classes.

This is efficient because aggregation operations in SQL are optimized internally and require only one pass through the data.

Test Cases

# test cases for Python simulation
import sqlite3

conn = sqlite3.connect(":memory:")
cursor = conn.cursor()
cursor.execute("CREATE TABLE Courses(student TEXT, class TEXT)")

# Example test case
cursor.executemany("INSERT INTO Courses(student, class) VALUES (?, ?)", [
    ("A", "Math"),
    ("B", "English"),
    ("C", "Math"),
    ("D", "Biology"),
    ("E", "Math"),
    ("F", "Computer"),
    ("G", "Math"),
    ("H", "Math"),
    ("I", "Math")
])
assert set(classes_with_at_least_five_students(conn)) == {"Math"}  # Example case

# Case with exactly 5 students
cursor.execute("DELETE FROM Courses")
cursor.executemany("INSERT INTO Courses(student, class) VALUES (?, ?)", [
    ("A", "Math"),
    ("B", "Math"),
    ("C", "Math"),
    ("D", "Math"),
    ("E", "Math")
])
assert set(classes_with_at_least_five_students(conn)) == {"Math"}  # Exactly 5 students

# Case with no class meeting requirement
cursor.execute("DELETE FROM Courses")
cursor.executemany("INSERT INTO Courses(student, class) VALUES (?, ?)", [
    ("A", "Math"),
    ("B", "English")
])
assert classes_with_at_least_five_students(conn) == []  # No class qualifies
Test Why
Example input Validates the normal functionality with more than 5 students
Exactly 5 students Ensures boundary case of 5 students is included
No class qualifies Ensures empty result is handled correctly

Edge Cases

One edge case is a class with exactly five students, which is the minimum threshold. The HAVING clause uses >= 5 to correctly include this class.

Another edge case is when multiple classes meet the criteria. The algorithm correctly counts each class independently, so multiple classes are returned.

A third edge case is an empty Courses table or a table where no class has enough students. The algorithm handles this gracefully, returning an empty list without errors.

This solution is robust, efficient, and concise, leveraging SQL's aggregation capabilities directly to solve the problem.