Department Top Three Salaries

Problem

The Employee table holds all employees. Every employee has an Id, and there is also a column for the department Id.

+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
| 5  | Janet | 69000  | 1            |
| 6  | Randy | 85000  | 1            |
+----+-------+--------+--------------+

The Department table holds all departments of the company.

+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

Write a SQL query to find employees who earn the top three salaries in each of the department. For the above tables, your SQL query should return the following rows.

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Randy    | 85000  |
| IT         | Joe      | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+

Setup

CREATE TEMPORARY TABLE IF NOT EXISTS `LeetCode`.`Employee` (
  `Id` INT,
  `Name` VARCHAR(255),
  `Salary` INT,
  `DepartmentId` INT
);
CREATE TEMPORARY TABLE IF NOT EXISTS `LeetCode`.`Department` (
  `Id` INT,
  `Name` VARCHAR(255)
);
TRUNCATE TABLE `LeetCode`.`Employee`;
TRUNCATE TABLE `LeetCode`.`Department`;
INSERT INTO `LeetCode`.`Employee` 
  (`Id`, `Name`, `Salary`, `DepartmentId`) 
VALUES 
  (1, "Joe", 70000, 1), 
  (2, "Henry", 80000, 2), 
  (3, "Sam", 60000, 2), 
  (4, "Max", 90000, 1), 
  (5, "Janet", 69000, 1), 
  (6, "Randy", 85000, 1);
INSERT INTO `LeetCode`.`Department` 
  (`Id`, `Name`) 
VALUES 
  (1, "IT"), 
  (2, "Sales");
SELECT * 
FROM `LeetCode`.`Employee`;
Table 1: 6 records
Id Name Salary DepartmentId
1 Joe 70000 1
2 Henry 80000 2
3 Sam 60000 2
4 Max 90000 1
5 Janet 69000 1
6 Randy 85000 1
SELECT * 
FROM `LeetCode`.`Department`;
Table 2: 2 records
Id Name
1 IT
2 Sales

Failed Attempt #1

-- Query #1
SELECT
  `Department`.`Name` AS `Department`,
  `Employee`.`Name` AS `Employee`,
  `Employee`.`Salary`
FROM `LeetCode`.`Employee` AS `Employee`
LEFT JOIN `LeetCode`.`Department` AS `Department`
ON `Employee`.`DepartmentId` = `Department`.`Id`
WHERE (
  SELECT COUNT(*)
  FROM `LeetCode`.`Employee` AS `t1`
  WHERE `t1`.`DepartmentId` = `Employee`.`DepartmentId`
  AND `t1`.`Salary` >= `Employee`.`Salary`) <= 3
ORDER BY `Employee`.`DepartmentId`, `Employee`.`Salary` DESC;
Table 3: 5 records
Department Employee Salary
IT Max 90000
IT Randy 85000
IT Joe 70000
Sales Henry 80000
Sales Sam 60000

The solution above brings the expected result set. However, this query fails if Department is empty.

TRUNCATE TABLE `LeetCode`.`Employee`;
TRUNCATE TABLE `LeetCode`.`Department`;
INSERT INTO `LeetCode`.`Employee`
  (`Id`, `Name`, `Salary`, `DepartmentId`)
VALUES
  (1, "Joe", 10000, 1);

-- Department intentionally left empty.
-- Query #1
SELECT
  `Department`.`Name` AS `Department`,
  `Employee`.`Name` AS `Employee`,
  `Employee`.`Salary`
FROM `LeetCode`.`Employee` AS `Employee`
LEFT JOIN `LeetCode`.`Department` AS `Department`
ON `Employee`.`DepartmentId` = `Department`.`Id`
WHERE (
  SELECT COUNT(*)
  FROM `LeetCode`.`Employee` AS `t1`
  WHERE `t1`.`DepartmentId` = `Employee`.`DepartmentId`
  AND `t1`.`Salary` >= `Employee`.`Salary`) <= 3
ORDER BY `Employee`.`DepartmentId`, `Employee`.`Salary` DESC;
Table 4: 1 records
Department Employee Salary
NA Joe 10000

The original problem does not state how to handle NULL results, which is what we have here. However, the answer set shown on failure is empty. The query has to be modified to accomodate no Departments.

Failed Attempt #2

-- Query #2
SELECT
  `Department`.`Name` AS `Department`,
  `Employee`.`Name` AS `Employee`,
  `Employee`.`Salary`
FROM `LeetCode`.`Employee` AS `Employee`
LEFT JOIN `LeetCode`.`Department` AS `Department`
ON `Employee`.`DepartmentId` = `Department`.`Id`
WHERE (
  SELECT COUNT(*)
  FROM `LeetCode`.`Employee` AS `t1`
  WHERE `t1`.`DepartmentId` = `Employee`.`DepartmentId`
  AND `t1`.`Salary` >= `Employee`.`Salary`) <= 3 
-- Check for NULL
AND `Department`.`Name` IS NOT NULL
ORDER BY `Employee`.`DepartmentId`, `Employee`.`Salary` DESC;

Table: (#tab:solution-2)0 records

Department Employee Salary ———– ——— ——-

Adding the line below to the query above passes the test case.

-- Check for NULL
AND `Department`.`Name` IS NOT NULL

The last failure came with ties; no mention of how to handle ties.

TRUNCATE TABLE `LeetCode`.`Employee`;
TRUNCATE TABLE `LeetCode`.`Department`;
INSERT INTO `LeetCode`.`Employee`
  (`Id`, `Name`, `Salary`, `DepartmentId`)
VALUES
  (1, "Joe", 60000, 1),
  (2, "Ralph", 50000, 1),
  (3, "Joel", 60000, 1),
  (4, "Tracy", 75000, 1);

Notice the tie between Joel and Joe; recognize that because of this Ralph is to be included, not excluded.

INSERT INTO `LeetCode`.`Department`
  (`Id`, `Name`)
VALUES
  (1, "IT");
-- Query #2
SELECT
  `Department`.`Name` AS `Department`,
  `Employee`.`Name` AS `Employee`,
  `Employee`.`Salary`
FROM `LeetCode`.`Employee` AS `Employee`
LEFT JOIN `LeetCode`.`Department` AS `Department`
ON `Employee`.`DepartmentId` = `Department`.`Id`
WHERE (
  SELECT COUNT(*)
  FROM `LeetCode`.`Employee` AS `t1`
  WHERE `t1`.`DepartmentId` = `Employee`.`DepartmentId`
  AND `t1`.`Salary` >= `Employee`.`Salary`) <= 3 
AND `Department`.`Name` IS NOT NULL 
ORDER BY `Employee`.`DepartmentId`, `Employee`.`Salary` DESC;
Table 6: 3 records
Department Employee Salary
IT Tracy 75000
IT Joe 60000
IT Joel 60000

I have to modify the query again in order to get Ralph into the result set. I do this by modifying the COUNT call. Instead of counting all rows, I only count DISTINCT Salary.

Solution

-- Query #3
SELECT
  `Department`.`Name` AS `Department`,
  `Employee`.`Name` AS `Employee`,
  `Employee`.`Salary`
FROM `LeetCode`.`Employee` AS `Employee`
LEFT JOIN `LeetCode`.`Department` AS `Department`
ON `Employee`.`DepartmentId` = `Department`.`Id`
WHERE (
  SELECT COUNT(DISTINCT `Salary`)
  FROM `LeetCode`.`Employee` AS `t1`
  WHERE `t1`.`DepartmentId` = `Employee`.`DepartmentId`
  AND `t1`.`Salary` >= `Employee`.`Salary`) <= 3
AND `Department`.`Name` IS NOT NULL
ORDER BY `Employee`.`DepartmentId`, `Employee`.`Salary` DESC;
Table 7: 4 records
Department Employee Salary
IT Tracy 75000
IT Joe 60000
IT Joel 60000
IT Ralph 50000
  SELECT COUNT(*)
  SELECT COUNT(DISTINCT `Salary`)

This query passes all test cases and beats out about 89% of all submittals in runtime.

MariaDB Server Info

SELECT @@version_comment AS `Version`, 
  @@version_compile_machine AS `Version Compile Machine`, 
  @@innodb_version AS `InnoDB Version`, 
  @@version_compile_os AS `Version Compile OS`;
Table 8: MariaDB Server Info
Version Version Compile Machine InnoDB Version Version Compile OS
mariadb.org binary distribution x86_64 5.7.19 debian-linux-gnu
Next
Previous
comments powered by Disqus