Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

The Employee table stores each employee’s ID, name, department, and manager ID. The task is to return the names of employees who manage at least five other employees directly.

The word directly is the key constraint. If Alice manages Bob and Bob manages Carol, Carol is Bob’s direct report but not Alice’s. The solution therefore needs only one relationship: match each manager’s id with the managerId values of the employees who report to that manager.

Deriving the optimal solution

Think of every non-null managerId as one vote for a manager. Grouping employee rows by managerId collects those votes, and COUNT(*) tells how many direct reports each manager has. A group qualifies when its count is at least five.

Those groups contain manager IDs, but the requested output contains manager names. A self-join supplies them:

  • Treat one copy of Employee as the possible managers.
  • Treat another copy as the direct reports.
  • Join a report’s managerId to a manager’s id.
  • Group by the manager’s identity and retain groups with at least five rows.

Grouping by manager.id matters. Names are not guaranteed to be unique, so grouping only by name could accidentally combine two different managers who happen to share one.

Optimal SQL solution

SELECT
    manager.name
FROM Employee AS manager
INNER JOIN Employee AS direct_report
    ON direct_report.managerId = manager.id
GROUP BY
    manager.id,
    manager.name
HAVING COUNT(*) >= 5;

Each joined row represents exactly one direct manager-report relationship. Consequently, the size of a manager’s group is exactly that manager’s number of direct reports. The HAVING clause runs after grouping and keeps precisely the managers whose group size reaches the threshold.

If there are n employees, the logical work is O(n) with a hash-based grouping or join plan, though the database engine chooses the physical plan. The grouping state can use O(m) space for m distinct manager IDs. An index on Employee(managerId) can make locating each manager’s reports much cheaper on a large table.

Python solution

LeetCode presents this as a database problem, so SQL is the native answer. The following production-level Python implementation applies the same counting rule to application records. It validates IDs and manager references while preserving linear time.

from __future__ import annotations

from collections import Counter
from collections.abc import Iterable
from dataclasses import dataclass


@dataclass(frozen=True, slots=True)
class Employee:
    """One employee and that employee's direct manager, if any."""

    employee_id: int
    name: str
    department: str
    manager_id: int | None


def _index_employees_and_count_reports(
    employees: Iterable[Employee],
) -> tuple[dict[int, Employee], Counter[int]]:
    """Build an employee lookup and count reports for every manager ID."""
    employees_by_id: dict[int, Employee] = {}
    direct_report_counts: Counter[int] = Counter()

    for employee in employees:
        if employee.employee_id in employees_by_id:
            raise ValueError(f"Duplicate employee ID: {employee.employee_id}")

        employees_by_id[employee.employee_id] = employee

        if employee.manager_id is not None:
            if employee.manager_id == employee.employee_id:
                raise ValueError(
                    f"Employee {employee.employee_id} cannot manage themself"
                )
            direct_report_counts[employee.manager_id] += 1

    unknown_manager_ids = direct_report_counts.keys() - employees_by_id.keys()
    if unknown_manager_ids:
        formatted_ids = ", ".join(
            str(manager_id) for manager_id in sorted(unknown_manager_ids)
        )
        raise ValueError(f"Unknown manager IDs: {formatted_ids}")

    return employees_by_id, direct_report_counts


def find_manager_names(
    employees: Iterable[Employee],
    minimum_direct_reports: int = 5,
) -> list[str]:
    """Return managers with at least the requested number of direct reports."""
    if minimum_direct_reports < 1:
        raise ValueError("minimum_direct_reports must be at least 1")

    employees_by_id, direct_report_counts = (
        _index_employees_and_count_reports(employees)
    )

    # Dictionary iteration follows input order; the problem accepts any order.
    return [
        employee.name
        for employee_id, employee in employees_by_id.items()
        if direct_report_counts[employee_id] >= minimum_direct_reports
    ]

After the scan, direct_report_counts[x] equals the number of input rows whose manager_id is x. Looking up each employee’s own ID in that counter therefore answers exactly whether that employee has at least five direct reports. The function takes O(n) time and O(n) auxiliary space for the validated employee index and counts.

Interview follow-ups

How would the query change if the threshold were supplied at runtime?

Replace the literal 5 in the HAVING clause with a bound parameter. The grouping logic does not change because the count of direct reports is independent of the cutoff; only the final test changes. The application should bind the value rather than construct SQL text so that the query remains safe and can reuse a cached plan.

The asymptotic cost remains the same because every relevant report relationship still has to contribute to a group. For extremely high thresholds, database statistics may let the optimizer choose a different plan, but the logical solution remains group, count, and filter.

How would you return each qualifying manager’s report count too?

Add COUNT(*) AS direct_report_count to the selected columns. The aggregate is already being computed for HAVING, so exposing it does not require another scan or a second grouping step.

The query must still group by the manager’s unique ID as well as any selected non-aggregate columns required by the SQL dialect. The output grows by one value per qualifying manager, while time and working-space bounds stay unchanged.

What if the interviewer asks for all descendants, not only direct reports?

A single self-join is no longer enough because the number of management levels is unknown. Use a recursive common table expression that starts with each direct manager-report edge and repeatedly follows reports below the current employee. Group the resulting ancestor-descendant pairs by ancestor and count distinct descendants if the data can contain multiple paths.

This traversal costs roughly O(V + E) for a tree-shaped organization, where V is the number of employees and E is the number of reporting relationships, but the recursive intermediate result can be much larger because it materializes ancestor-descendant pairs. Production data should enforce an acyclic hierarchy or add cycle detection so malformed reporting loops cannot recurse forever.

Which index is most useful when the employee table is very large?

An index beginning with managerId directly supports finding all reports for a given manager and can help both the self-join and grouped count. Including id or name may produce a covering index in some database engines, reducing table lookups, although the exact benefit depends on the execution plan and storage engine.

The tradeoff is extra storage and slower inserts, deletes, and manager changes because the index must also be maintained. A strong production answer proposes the index and then verifies it with the database’s execution-plan tools rather than assuming it will always win.

What if two qualifying managers have the same name?

They are still different employees and should remain separate groups because their IDs differ. The base result selects only name, so two identical-looking rows may legitimately appear. Grouping by name alone would be incorrect because it could combine their report counts and even make two individually unqualified people appear qualified.

If consumers need to distinguish them, return manager.id alongside manager.name. That changes only the output shape, not the grouping rule or its complexity.

How would you also return the direct reports’ names?

First identify qualifying manager IDs with the grouped count. Then join those IDs back to the manager and report rows and aggregate the report names into an array or JSON value if the database supports it. Keeping qualification in a subquery or common table expression avoids mixing the threshold calculation with output aggregation.

The running time is still linear in the number of matched relationships under a hash-based plan, but the result itself is larger: every qualifying report name must be read and emitted. Ordering names inside each aggregate may additionally require sorting each manager’s reports.

How would you maintain this result as employees join, leave, or change managers?

Maintain a direct-report counter keyed by manager ID. Adding an employee increments one counter, removing an employee decrements one, and transferring an employee decrements the old manager’s counter and increments the new manager’s. A manager enters or leaves the result only when a counter crosses the threshold of five.

Each change takes expected O(1) time with a hash map, compared with rescanning the whole table. The tradeoff is consistency work: the counter update and employee-row change must be atomic, or the materialized result can drift from the source data. In a database, a transactional summary table or an incrementally maintained materialized view can provide that guarantee.

Takeaway

The essential pattern is self-join, group, and filter. The self-join turns manager IDs into direct relationships, grouping counts those relationships per manager, and HAVING applies the threshold after the counts exist. Recognizing that sequence makes the solution almost mechanical—and keeps direct reports distinct from the entire reporting hierarchy.