LeetCode 184 - Department Highest Salary

Database Language: SQL Server

Difficulty: Medium

Problem Description

Input

Table: Employee

| Column Name  | Type    |
| ------------ | ------- |
| id           | int     |
| name         | varchar |
| salary       | int     |
| departmentId | int     |

`id` is the primary key (column with unique VALUES) for this table.

`departmentId` is a foreign key (reference columns) of the ID from the `Department` table.

Each row of this table indicates the ID, name, and salary of an employee. It also contains the ID of their department.

Table: Department

| Column Name | Type    |
| ----------- | ------- |
| id          | int     |
| name        | varchar |

`id` is the primary key (column with unique VALUES) for this table. It is guaranteed that department name is not NULL. Each row of this table indicates the ID of a department and its name.

Requirement

Write a solution to find employees who have the highest salary in each of the departments.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1

Input

Employee table:

| 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 table:

| id | name  |
| -- | ----- |
| 1  | IT    |
| 2  | Sales |
Output
| Department | Employee | Salary |
| ---------- | -------- | ------ |
| IT         | Jim      | 90000  |
| Sales      | Henry    | 80000  |
| IT         | Max      | 90000  |
Explanation

Max and Jim both have the highest salary in the IT department and Henry has the highest salary in the Sales department.

SQL Schema

CREATE TABLE [dbo].[Employee] (id int PRIMARY KEY, name VARCHAR(255), salary INT, departmentId INT);
CREATE TABLE [dbo].[Department] (id int PRIMARY KEY, name VARCHAR(255));

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

TRUNCATE TABLE [dbo].[Department];
INSERT INTO [dbo].[Department] (id, name) VALUES ('1', 'IT');
INSERT INTO [dbo].[Department] (id, name) VALUES ('2', 'Sales');

Solution

The first step in finding the employees who have the highest salary in each of the department is to create a query that will get the highest salary for each department. There are a couple of ways of doing this. The first is by using the `MAX()` aggregate function together with the `GROUP BY` clause of the `SELECT` statement using just the `Employee` table:

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

| departmentId | Salary |
| ------------ | ------ |
| 1            | 90000  |
| 2            | 80000  |

The second way is to still use the `MAX()` aggregate function together with the `GROUP BY` clause but instead of just using the `Employee` table, the table is joined with the `Department` table since the department name is needed in the output.

SELECT Department.name, departmentId, MAX(salary) AS Salary
FROM Employee INNER JOIN Department
  ON Employee.departmentId = Department.id
 GROUP BY Department.name, departmentId

Now that we have the highest salary for each department together with the name and ID of the department, this can now be joined back with the `Employee` table to return the requested output:

/* Final Solution Query */
SELECT Department.name AS Department, Employee.name AS Employee, Employee.Salary
FROM Employee INNER JOIN (SELECT Department.name, departmentId, MAX(salary) AS Salary
                          FROM Employee INNER JOIN Department
                            ON Employee.departmentId = Department.id
                            GROUP BY Department.name, departmentId) Department
  ON Employee.departmentId = Department.departmentId AND
     Employee.Salary = Department.Salary;

This query can also written using a common-table expression (CTE):

/* Final Solution Query */
WITH CTE_MaxSalary (Department, DepartmentID, Salary) AS
  (SELECT Department.name, departmentId, MAX(salary) AS Salary
  FROM Employee INNER JOIN Department
    ON Employee.departmentId = Department.id
  GROUP BY Department.name, departmentId)
SELECT cte.Department, Employee.name AS Employee, cte.Salary
FROM Employee INNER JOIN CTE_MaxSalary cte
  ON Employee.departmentId = cte.departmentId AND
     Employee.Salary = cte.Salary

Both of these queries generates the same query plan:

  |--Hash Match(Inner Join, HASH:([dbo].[Employee].[departmentId], [Expr1006])=
     ([dbo].[Employee].[departmentId], [dbo].[Employee].[salary]),
     RESIDUAL:([dbo].[Employee].[departmentId]=[dbo].[Employee].[departmentId] AND [dbo].[Employee].[salary]=[Expr1006]))
    |--Stream Aggregate(GROUP BY:([leetcode].[dbo].[Employee].[departmentId])
       DEFINE:([Expr1006]=MAX([dbo].[Employee].[salary]), [dbo].[Department].[name]=ANY([dbo].[Department].[name])))
    | |--Nested Loops(Inner Join, OUTER REFERENCES:([leetcode].[dbo].[Employee].[departmentId]))
    |       |--Sort(ORDER BY:([leetcode].[dbo].[Employee].[departmentId] ASC))
    |       | |--Clustered Index Scan(OBJECT:([leetcode].[dbo].[Employee].[PK_Employee]))
    |       |--Clustered Index Seek(OBJECT:([leetcode].[dbo].[Department].[PK_Department]),
               SEEK:([leetcode].[dbo].[Department].[id]=[leetcode].[dbo].[Employee].[departmentId]) ORDERED FORWARD)
    |--Clustered Index Scan(OBJECT:([leetcode].[dbo].[Employee].[PK_Employee]))

The fastest runtime for these queries is as follows:

Related Articles: