LeetCode 184 - Department Highest Salary¶

Database Language: SQL Server

Difficulty:

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:([leetcode].[dbo].[Employee].[departmentId], [Expr1006])=([leetcode].[dbo].[Employee].[departmentId], [leetcode].[dbo].[Employee].[salary]), RESIDUAL:([leetcode].[dbo].[Employee].[departmentId]=[leetcode].[dbo].[Employee].[departmentId] AND [leetcode].[dbo].[Employee].[salary]=[Expr1006]))
    |--Stream Aggregate(GROUP BY:([leetcode].[dbo].[Employee].[departmentId]) DEFINE:([Expr1006]=MAX([leetcode].[dbo].[Employee].[salary]), [leetcode].[dbo].[Department].[name]=ANY([leetcode].[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:

Runtime: 394ms
Beats: 94.38% as of July 16, 2024