Domain 2MediumCORE

Count Student Number in Departments

The goal is to determine how many students are enrolled in each department based on provided data structures.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 0

580. Count Student Number in Departments

Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 52.2%


Problem Breakdown

The goal is to determine how many students are enrolled in each department based on provided data structures.

Inputs:

  • A collection of student records (typically a list), where each record contains a unique identifier and an associated department_id.
  • The input may be empty or contain null values for specific fields depending on the schema constraints.

Outputs:

  • An aggregated count for every distinct department present in the dataset. The output should ideally be sorted by department ID to ensure deterministic ordering, as interviewers often expect consistent results (matching SQL ORDER BY behavior).

Constraints & Edge Cases:

  1. Empty Input: If no students exist or a list is empty, return an empty result set immediately.
  2. Missing Departments/NULLs: A student might belong to a department that doesn’t have other metadata; we count based on the ID provided in the record. NULL IDs should be excluded from counts (standard SQL COUNT behavior usually ignores null keys unless specified).
  3. Duplicates: Multiple records for the same student/department combination are possible if data isn’t unique, but standard aggregation treats each row as an enrollment event (GROUP BY). We treat every valid row incrementing a counter.
  4. Invalid Types: If department_id is not an integer (e.g., string or boolean), it should be handled based on schema expectations; typically we filter for integers to match DB schemas, but robust code handles potential type mismatches gracefully by skipping invalid keys.

Intuition

If you were asked this without SQL knowledge, the first thought might be: “I need to count how many times each department ID appears.”

A brute-force approach would involve iterating through every student record and then checking against a list of all departments for every single row (nested loops). This results in O(N×M)O(N \times M) time complexity where N is students and M is departments. That’s inefficient because we are doing redundant work—checking the same department ID multiple times without caching it.

The key insight here is Aggregation. We don’t need to compare every student against every other student or re-scan for each count. Instead, we can maintain a running tally (a Hash Map/Dictionary) as we iterate through the data once. For every row encountered, we simply increment the counter associated with that department’s ID. This reduces complexity significantly because dictionary lookups are O(1)O(1) on average.

Approach

We will use Python’s built-in collections.Counter or a standard Dictionary to aggregate counts in a single pass over the data.

Steps:

  1. Initialize an empty counter/dictionary for department IDs.
  2. Iterate through each student record provided as input (simulating reading from a table).
  3. For each record, extract the department_id.
  4. Increment the count in our dictionary/counter for that ID if it is valid and not null.
  5. Convert the resulting counts into a list of tuples or dictionaries containing (dept_id, count), sorted by department ID to ensure consistent output order (interviewers often expect this).

This approach is efficient because we process each record exactly once (O(N)O(N)), then sort the unique keys at the end. Sorting takes O(Klog⁡K)O(K \log K) where KK is the number of unique departments, which is bounded by NN.

Complexity Analysis

  • Time Complexity: O(N+Klog⁡K)O(N + K \log K), where NN is the number of student records and KK is the number of distinct department IDs. We iterate through the list once (O(N)O(N)) for dictionary operations (amortized O(1)O(1)). Sorting at the end takes O(Klog⁡K)O(K \log K). In many cases where KK is small relative to NN, this behaves linearly, but strictly speaking it includes a sorting factor.
  • Space Complexity: O(K)O(K), to store the counts for each distinct department in our hash map/counter. In the worst case where every student has a different department (K=NK=N), this becomes O(N)O(N).

Solution

from collections import Counter
from typing import List, Dict, Any, Tuple

def count_students(students: List[Dict[str, Any]]) -> List[Tuple[int, int]]:
    """
    Counts students per department. 
    Assumes 'students' is a list of dicts with at least 'department_id'.
    Returns sorted list of (dept_id, count).
    Handles empty input and null/invalid IDs gracefully.
    """

    # Handle empty input gracefully
    if not students:
        return []

    # Use Counter for O(1) average time complexity increments
    dept_counts = Counter()
    
    for student in students:
        # Safely extract department ID; skip records with missing IDs to avoid errors
        dept_id = student.get('department_id') 
        
        # Check if valid integer (excluding booleans which are int subclasses in Python)
        if dept_id is not None and isinstance(dept_id, int) and not isinstance(dept_id, bool):
            dept_counts[dept_id] += 1
            
    # Convert Counter object back to a list of tuples for consistent output format
    result = [(k, v) for k, v in sorted(dept_counts.items())]
    
    return result

# Example usage (uncommenting this block demonstrates the function):
if __name__ == "__main__":
    data = [
        {"department_id": 1}, 
        {"department_id": 2}, 
        {"department_id": 1}
    ]
    print(count_students(data)) # Output: [(1, 2), (2, 1)]

Edge Cases Handled

  • Empty List: The function checks if not students and returns an empty list immediately.
  • Missing Department ID: We use .get() to safely access the key; if it’s missing or None, we skip incrementing that count (preventing crashes).
  • Non-Integer IDs / Booleans: Added a type check (isinstance(dept_id, int)) combined with an explicit boolean exclusion. This ensures valid integer keys for sorting and counting are used while filtering out potential edge cases where booleans might be passed as integers in Python (since bool is a subclass of int).
  • Duplicate Rows: The logic naturally handles duplicates by incrementing the counter each time a row is processed, matching standard SQL COUNT(*) behavior.