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 TABLE `Employee` (
  `Id` INT,
  `Name` VARCHAR(255),
  `Salary` INT,
  `DepartmentId` INT
);

CREATE TABLE `Department` (
  `Id` INT,
  `Name` VARCHAR(255)
);

INSERT INTO `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 `Department` 
  (`Id`, `Name`) 
VALUES 
  (1, "IT"), 
  (2, "Sales");

SELECT * 
FROM `Employee`;

SELECT * 
FROM `Department`;

Failed Attempt #1

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

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

DELETE FROM `Employee`;

DELETE FROM `Department`;

INSERT INTO `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 
  `Employee` AS `Employee`
LEFT JOIN 
  `Department` AS `Department`
ON 
  `Employee`.`DepartmentId` = `Department`.`Id`
WHERE (
  SELECT 
    COUNT(*)
  FROM 
    `Employee` AS `t1`
  WHERE 
    `t1`.`DepartmentId` = `Employee`.`DepartmentId`
  AND 
    `t1`.`Salary` >= `Employee`.`Salary`
  ) <= 3
ORDER BY 
  `Employee`.`DepartmentId`, 
  `Employee`.`Salary` 
DESC;

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 Department.

Failed Attempt #2

-- Query #2
SELECT
  `Department`.`Name` AS `Department`,
  `Employee`.`Name` AS `Employee`,
  `Employee`.`Salary`
FROM 
  `Employee` AS `Employee`
LEFT JOIN 
  `Department` AS `Department`
ON 
  `Employee`.`DepartmentId` = `Department`.`Id`
WHERE (
  SELECT 
    COUNT(*)
  FROM 
    `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;

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.

DELETE FROM `Employee`;

DELETE FROM `Department`;

INSERT INTO `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 `Department`
  (`Id`, `Name`)
VALUES
  (1, "IT");

-- Query #2
SELECT
  `Department`.`Name` AS `Department`,
  `Employee`.`Name` AS `Employee`,
  `Employee`.`Salary`
FROM 
  `Employee` AS `Employee`
LEFT JOIN 
  `Department` AS `Department`
ON 
  `Employee`.`DepartmentId` = `Department`.`Id`
WHERE (
  SELECT 
    COUNT(*)
  FROM 
    `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;

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 
  `Employee` AS `Employee`
LEFT JOIN 
  `Department` AS `Department`
ON 
  `Employee`.`DepartmentId` = `Department`.`Id`
WHERE (
  SELECT 
    COUNT(DISTINCT `Salary`)
  FROM 
    `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;

  SELECT 
    COUNT(*)

  SELECT 
    COUNT(DISTINCT `Salary`)

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