LeetCode 184: Department Highest Salary

Problem Restatement

We are given two tables: Employee and Department.

Employee stores employee information.

Column	Type
id	int
name	varchar
salary	int
departmentId	int

Department stores department information.

Column	Type
id	int
name	varchar

Each employee belongs to one department through Employee.departmentId.

We need to find employees who have the highest salary in each department. If multiple employees share the highest salary in the same department, we return all of them. The official problem asks for employees who have the highest salary in each department.

Input and Output

Item	Meaning
Input	Tables `Employee` and `Department`
Output	Columns `Department`, `Employee`, and `Salary`
Rule	Return employees whose salary equals the highest salary in their department
Ties	Return all tied employees
Order	Any order is accepted

Expected output columns:

Department, Employee, Salary

Examples

Input:

Employee
+----+-------+--------+--------------+
| id | name  | salary | departmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Jim   | 90000  | 1            |
| 3  | Henry | 80000  | 2            |
| 4  | Sam   | 60000  | 2            |
| 5  | Max   | 90000  | 1            |
+----+-------+--------+--------------+

Department
+----+-------+
| id | name  |
+----+-------+
| 1  | IT    |
| 2  | Sales |
+----+-------+

For department IT, the salaries are:

Joe -> 70000
Jim -> 90000
Max -> 90000

The highest salary in IT is 90000, so both Jim and Max should be returned.

For department Sales, the salaries are:

Henry -> 80000
Sam   -> 60000

The highest salary in Sales is 80000, so Henry should be returned.

Output:

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Jim      | 90000  |
| Sales      | Henry    | 80000  |
| IT         | Max      | 90000  |
+------------+----------+--------+

First Thought: Find the Maximum Salary Per Department

The core task is to find, for each department, the maximum salary.

That query is:

SELECT
    departmentId,
    MAX(salary) AS salary
FROM Employee
GROUP BY departmentId;

This gives one row per department:

departmentId -> highest salary

Then we need to return employees whose (departmentId, salary) pair matches one of those maximum pairs.

Key Insight

This problem has two separate parts:

Part	Purpose
Find max salary per department	Determines the top salary level in each department
Join employee and department names	Produces the required output columns

The important detail is ties.

We should not choose only one employee per department. We should return every employee whose salary equals the department maximum.

So the condition is:

employee.salary = max_salary_for_that_department

not “first employee after sorting.”

Algorithm

Group Employee by departmentId.
Compute MAX(salary) for each department.
Join Employee with Department to get department names.
Keep only employees whose (departmentId, salary) appears in the maximum-salary result.
Return department name, employee name, and salary.

Correctness

The subquery:

SELECT
    departmentId,
    MAX(salary)
FROM Employee
GROUP BY departmentId

returns exactly one maximum salary for each department.

For any employee e, the pair:

(e.departmentId, e.salary)

is in the subquery result only when e.salary equals the maximum salary of e.departmentId.

Therefore, the outer query keeps exactly the employees who have the highest salary in their own department.

The join with Department only adds the department name. It does not change which employees qualify.

If several employees in the same department share the maximum salary, they all have the same qualifying (departmentId, salary) pair, so all of them are returned.

Complexity

Metric	Value	Why
Time	`O(n + d)` expected	The database groups employees and joins departments
Space	`O(d)`	The grouped result stores one maximum salary per department

Here, n is the number of employees, and d is the number of departments with employees.

Implementation

SELECT
    d.name AS Department,
    e.name AS Employee,
    e.salary AS Salary
FROM Employee e
JOIN Department d
    ON e.departmentId = d.id
WHERE (e.departmentId, e.salary) IN (
    SELECT
        departmentId,
        MAX(salary)
    FROM Employee
    GROUP BY departmentId
);

Code Explanation

This joins employees to their departments:

FROM Employee e
JOIN Department d
    ON e.departmentId = d.id

Now each employee row has both employee information and department information.

The subquery:

SELECT
    departmentId,
    MAX(salary)
FROM Employee
GROUP BY departmentId

computes the highest salary in each department.

This filter keeps only employees whose department and salary match that result:

WHERE (e.departmentId, e.salary) IN (...)

Finally, we return the requested columns:

SELECT
    d.name AS Department,
    e.name AS Employee,
    e.salary AS Salary

Alternative Implementation With Window Function

We can also use RANK().

WITH ranked AS (
    SELECT
        d.name AS Department,
        e.name AS Employee,
        e.salary AS Salary,
        RANK() OVER (
            PARTITION BY e.departmentId
            ORDER BY e.salary DESC
        ) AS rnk
    FROM Employee e
    JOIN Department d
        ON e.departmentId = d.id
)
SELECT
    Department,
    Employee,
    Salary
FROM ranked
WHERE rnk = 1;

RANK() is useful because tied salaries receive the same rank.

So if two employees share the highest salary in a department, both receive rank 1.

Testing

Test case 1:

CREATE TABLE Employee (
    id INT PRIMARY KEY,
    name VARCHAR(255),
    salary INT,
    departmentId INT
);

CREATE TABLE Department (
    id INT PRIMARY KEY,
    name VARCHAR(255)
);

INSERT INTO Employee (id, name, salary, departmentId) VALUES
(1, 'Joe', 70000, 1),
(2, 'Jim', 90000, 1),
(3, 'Henry', 80000, 2),
(4, 'Sam', 60000, 2),
(5, 'Max', 90000, 1);

INSERT INTO Department (id, name) VALUES
(1, 'IT'),
(2, 'Sales');

Expected:

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Jim      | 90000  |
| Sales      | Henry    | 80000  |
| IT         | Max      | 90000  |
+------------+----------+--------+

Test case 2:

DELETE FROM Employee;
DELETE FROM Department;

INSERT INTO Department (id, name) VALUES
(1, 'Engineering');

INSERT INTO Employee (id, name, salary, departmentId) VALUES
(1, 'Alice', 100000, 1);

Expected:

+-------------+----------+--------+
| Department  | Employee | Salary |
+-------------+----------+--------+
| Engineering | Alice    | 100000 |
+-------------+----------+--------+

Test case 3:

DELETE FROM Employee;
DELETE FROM Department;

INSERT INTO Department (id, name) VALUES
(1, 'Engineering');

INSERT INTO Employee (id, name, salary, departmentId) VALUES
(1, 'Alice', 100000, 1),
(2, 'Bob', 100000, 1),
(3, 'Cara', 90000, 1);

Expected:

+-------------+----------+--------+
| Department  | Employee | Salary |
+-------------+----------+--------+
| Engineering | Alice    | 100000 |
| Engineering | Bob      | 100000 |
+-------------+----------+--------+

Test case 4:

DELETE FROM Employee;
DELETE FROM Department;

INSERT INTO Department (id, name) VALUES
(1, 'IT'),
(2, 'Sales');

INSERT INTO Employee (id, name, salary, departmentId) VALUES
(1, 'Alice', 50000, 1),
(2, 'Bob', 70000, 1),
(3, 'Cara', 60000, 2),
(4, 'Dan', 65000, 2);

Expected:

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Bob      | 70000  |
| Sales      | Dan      | 65000  |
+------------+----------+--------+