Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

What the problem is asking

There are two tables. Employee stores each employee’s name, salary, and department ID, while Department maps each department ID to a display name. The result must contain every employee whose salary is the highest in that employee’s department.

The word every matters. If two people tie for the highest salary in the same department, both must appear. The task is therefore not to pick one employee per department; it is to find the maximum salary value per department and keep all employees who match it.

Deriving the solution

It helps to separate the problem into three small questions:

  1. What divides the employees into independent groups? The departmentId column.
  2. What value summarizes each group? MAX(salary).
  3. How are all tied winners recovered? Join that per-department maximum back to Employee on both the department ID and salary.

For example, suppose one department has salaries 70,000, 90,000, and 90,000. Grouping identifies 90,000 as that department’s maximum. Matching employees against that value returns both people earning 90,000, so ties need no special case.

The department ID should be the grouping key, not the department name. IDs define the relationship between the tables and remain unambiguous even if names are not unique. The human-readable department name is added only after the winning employee rows are known.

Optimal database approach

A grouped aggregate followed by a join is a direct translation of the reasoning:

WITH department_maximum AS (
    SELECT
        departmentId,
        MAX(salary) AS maximum_salary
    FROM Employee
    GROUP BY departmentId
)
SELECT
    department.name AS Department,
    employee.name AS Employee,
    employee.salary AS Salary
FROM Employee AS employee
INNER JOIN department_maximum AS maximum
    ON maximum.departmentId = employee.departmentId
   AND maximum.maximum_salary = employee.salary
INNER JOIN Department AS department
    ON department.id = employee.departmentId;

The common table expression produces exactly one maximum salary for each department. The first join recovers every employee at that maximum, including ties, and the second join supplies the department name. No ordering is needed because the problem accepts the rows in any order.

Another strong answer uses DENSE_RANK() over each department, ordered by salary descending, and keeps rank 1. It is especially useful when the question later expands to the top several distinct salary levels. For the base problem, the grouped maximum is usually easier to explain and may avoid the per-partition sorting required by a window function.

With E employees and D departments, the logical work is O(E + D) when grouping uses hashing, plus the cost of producing the winning rows. A database may choose a different physical plan based on indexes, statistics, and storage layout. The grouped result and joins require up to O(D) working state, apart from the output.

Python solution

LeetCode’s native submission for this problem is SQL or pandas. The Python implementation below expresses the same grouped-maximum rule for application data. It processes the employees once, keeps all current leaders for each department, and replaces a department’s leader list only when it sees a strictly higher salary.

from __future__ import annotations

from dataclasses import dataclass, field
from typing import Iterable


@dataclass(frozen=True, slots=True)
class Employee:
    employee_id: int
    name: str
    salary: int
    department_id: int


@dataclass(frozen=True, slots=True)
class Department:
    department_id: int
    name: str


@dataclass(frozen=True, slots=True)
class HighestSalaryRow:
    department: str
    employee: str
    salary: int


@dataclass(slots=True)
class _DepartmentLeaders:
    """Track one department's maximum salary and all employees tied at it."""

    salary: int
    employees: list[Employee] = field(default_factory=list)


def _index_departments(
    departments: Iterable[Department],
) -> dict[int, Department]:
    """Build a validated lookup from department ID to department record."""
    departments_by_id: dict[int, Department] = {}

    for department in departments:
        if department.department_id in departments_by_id:
            raise ValueError(
                f"Duplicate department ID: {department.department_id}"
            )
        departments_by_id[department.department_id] = department

    return departments_by_id


def find_department_highest_salaries(
    employees: Iterable[Employee],
    departments: Iterable[Department],
) -> list[HighestSalaryRow]:
    """Return every employee tied for the maximum salary in their department."""
    departments_by_id = _index_departments(departments)
    leaders_by_department: dict[int, _DepartmentLeaders] = {}

    for employee in employees:
        if employee.department_id not in departments_by_id:
            raise ValueError(
                "Employee references unknown department ID: "
                f"{employee.department_id}"
            )

        current_leaders = leaders_by_department.get(employee.department_id)

        if current_leaders is None or employee.salary > current_leaders.salary:
            # A new maximum invalidates every previous leader in this department.
            leaders_by_department[employee.department_id] = _DepartmentLeaders(
                salary=employee.salary,
                employees=[employee],
            )
        elif employee.salary == current_leaders.salary:
            # Preserve every employee tied at the maximum salary.
            current_leaders.employees.append(employee)

    result: list[HighestSalaryRow] = []

    for department_id, leaders in leaders_by_department.items():
        department_name = departments_by_id[department_id].name
        result.extend(
            HighestSalaryRow(
                department=department_name,
                employee=employee.name,
                salary=employee.salary,
            )
            for employee in leaders.employees
        )

    return result

The scan invariant is simple: after each employee is processed, the bucket for that employee’s department contains exactly the highest salary seen so far and all employees seen with that salary. A higher salary replaces the bucket, an equal salary extends it, and a lower salary changes nothing. That proves the final buckets contain exactly the required rows.

The function runs in O(E + D + W) time, where W is the number of winning employees copied into the result. Its extra space is O(D + W). It also validates duplicate department IDs and broken employee-to-department references, even though LeetCode’s schema guarantees valid keys.

Interview follow-ups

How would you return the top three distinct salary levels in each department?

Use DENSE_RANK() with PARTITION BY departmentId ORDER BY salary DESC, then keep rows whose rank is at most 3. Dense ranking gives equal salaries the same rank and advances to the next distinct salary without leaving gaps, so every employee tied at any of the top three salary levels is returned.

The database normally has to order each department’s rows, making the plan roughly O(E log E) without a supporting index. The approach is more expensive than a single grouped maximum, but it generalizes cleanly to any small number of distinct salary levels.

What if exactly one employee must be returned when the highest salary is tied?

The interviewer must define a deterministic tie-breaker, such as the smallest employee ID. Use ROW_NUMBER() partitioned by department and ordered by salary descending and employee ID ascending, then keep row number 1.

ROW_NUMBER() assigns a unique position even when salary values tie, and the secondary ordering makes the choice repeatable. This changes the original requirement by discarding tied leaders, while adding sorting work and a business rule that the base problem does not need.

Which indexes would help on a very large employee table?

A composite index beginning with departmentId and then salary descending aligns with both grouping and top-salary access. Including the employee ID or name can make the index cover more of the query, although exact support and syntax depend on the database engine. The primary keys already support the joins to department records.

The index can reduce scanning or sorting, but it makes inserts and salary updates more expensive and consumes storage. The expected answer is therefore not simply “add every column to an index”; it is to match the index to the dominant read pattern and verify the actual execution plan.

How would you include departments that currently have no employees?

Start from Department and use a left join to the computed winners. This preserves every department row, while employee and salary columns become NULL for departments without a match. Any condition on the employee side must remain in the join logic or a subquery; putting it in the final WHERE clause can accidentally turn the outer join back into an inner join.

The result becomes larger because it now includes empty departments. The grouped-maximum logic for populated departments stays the same, but the join direction must reflect the new requirement that every department be preserved.

How would you maintain the answer from a stream of salary updates?

For insert-only data, keep the current maximum and tied leaders per department, exactly as the Python solution does. Each new employee then takes expected O(1) time: replace the leaders after a higher salary, append after an equal salary, and ignore a lower salary.

Arbitrary salary decreases and deletions are harder because removing the current maximum requires finding the next one. A per-department ordered multiset, balanced tree, or indexed database table supports those changes in O(log n) time, trading more memory and update cost for efficient recovery of the next-highest salary.

Could a correlated subquery solve the original problem?

Yes. Each employee can be compared with the maximum salary from that employee’s department. The logic is concise and correct because every tied employee satisfies the equality test.

The tradeoff is execution risk: a naive plan may recompute the department maximum for many employee rows. Some optimizers decorrelate the query into an efficient grouped plan, but the explicit aggregate-and-join version makes the shared computation clear and is easier to reason about during an interview.

Takeaway

The reusable pattern is aggregate, then join back. Grouping finds the best value for each category; joining that result to the original rows recovers all records that achieved it. Keeping those two jobs separate makes the solution easy to derive and naturally handles ties.