LeetCode SQL Problem & Solution: Department Top Three Salaries

Looking for a detailed explanation of the hardest exercise in the LeetCode SQL 50? We have compiled a detailed explanation of this SQL problem, with the thought process behind the solution and instructions on how to build the query step-by-step.

LeetCode is a popular online platform that offers a variety of SQL problems designed to help you learn, practice, and prepare for interviews. They also offer programming problems in other languages. Problems are grouped into topics like algorithms, data structures, databases, system design, and individual programming languages.

LeetCode also includes a 50-problem SQL study plan to get you all the necessary skills to ace a data science interview. But if you are looking for more than just 50 problems to learn and practice on, consider the 120+ exercises in our SQL Basics course. We also have a collection of 100+ SQL Interview questions specifically designed for you to practice before a job interview.

In this article, we will take a close look at the hardest problem of LeetCode’s SQL set: Department Top Three Salaries. We will discuss the thought process behind the solution and how to build the query step-by-step. Ready?

The Department Top Three Salaries Problem

Department Top Three Salaries is the only Hard problem within LeetCode’s SQL 50 study plan. There are several places where you could get stuck, so let’s tackle this problem one step at a time.

The Task

A company’s executives are interested in seeing who earns the most money in each of the company’s departments. A high earner is an employee who has a salary in the top three unique salaries for that department.

Write a solution to find the employees who are high earners in each of the departments.

Take a look at the schema of the database for this task:

The Solution

Step 1: Finding the Company’s High Earners

Let’s start by finding high earners without bothering with the departments. The problem description specifies that a high earner is anyone with a salary that is one of the top 3 unique salaries. This means that if there are several people with the same salary, they will all be top earners. Take a look at the following result table:

Notice that while we are only selecting the top four salaries, there can be more than four high earners. For example, Will and Max share the same salary amount and both end up on the high earners list with the same salary rank of 3.

We cannot use basic ORDER BY and LIMIT to fetch the high earners, because we cannot know how many top earners there are before running the query! But we can filter the result by the salary rank. Let’s discuss how we can obtain that ranking, since it is not included in the database.

There are three ranking functions in SQL: RANK(), DENSE_RANK(), and ROW_NUMBER(). All of them will return a ranking of values within the specified window frame and ordering direction. The difference between them is how they handle duplicate values. You can read a detailed explanation on how to use ranking functions in our Overview of Ranking Functions in SQL.

Take a look at the same scenario as before, but now with all ranking functions included:

As you can see, RANK() and DENSE_RANK() return the same rank if the salaries are the same; this is the behaviour that we need to make sure that multiple people can be included as high earners if they share the same salary. Max would be excluded from the top 3 list when using ROW_NUMBER() even though he has a top 3 salary.

The difference between RANK() and DENSE_RANK() is how they handle holes in ranking left by duplicate values. RANK() skips a sequential rank number for every duplicate rank, resulting in non-duplicate values having the same rank. DENSE_RANK() does not skip ranks in case of duplicates. That’s what we want for this problem, as it eliminates omitting a top 3 salary when there are two or more top 2 salaries.

Here’s a query that will assign all employees a rank based on their salary using DENSE_RANK():

SELECT
  e.name,
  e.salary,
  DENSE_RANK() OVER(ORDER BY e.salary DESC)
FROM employee e;

Great! We are now getting the same result as in the first example: All employees are assigned ranks corresponding to their salary rank. The next step is to create a separate ranking for each department.

Step 2: Finding Department High Earners

We can add a PARTITION BY inside the OVER() clause to specify the window frame for each row based on a given value.

In this problem, we are looking to create a top 3 ranking of salaries in each department, so we should partition the window frame by the department ID. For a deeper dive into this expression, read our article on How to use PARTITION BY with OVER().

Here’s the query that will assign the ranks separately for each department:

SELECT
  d.name AS department, 
  e.name AS employee,
  e.salary,
  DENSE_RANK() OVER(PARTITION BY d.id ORDER BY e.salary DESC) AS rank
FROM employee e
JOIN department d 
  ON d.id = e.departmentId;

We have to join the department and employee tables because the task asks us to display the department names. However, the PARTITION BY clause should use the department.id column (the department table’s primary key) to make sure that no two departments map to the same partition (which could happen if two departments have the same name).

Step 3: Building the Final Query

Great! We have a local ranking for salaries for each department. Now what?

We cannot filter by the rank column because windows functions are not allowed in the WHERE clause.

We will have to wrap the ranking query in a CTE and get the final result from there. We’ll filter by the rank column to only include the top 3 salaries of each department. Remember not to include the rank itself in the final result, as we only need the salaries.

Take a look at the full solution to the problem:

WITH ranks AS (
SELECT
  d.name AS department, 
  e.name AS employee,
  e.salary,
  DENSE_RANK() OVER(PARTITION BY d.id ORDER BY e.salary DESC) AS salary_rank
FROM employee e
JOIN department d 
  ON d.id = e.departmentId
)
SELECT
  department,
  employee,
  salary,
FROM ranks 
WHERE  salary_rank <= 3;

Just like that, we have a complete list of high earners for each department!

Solved: LeetCode’s Hardest SQL Problem!

Nicely done! We have done a deep dive into the hardest problem of the LeetCode SQL 50 study plan.

Are you looking for more practice beyond the SQL 50 plan? Try our SQL Practice track and choose from over 1,000 interactive SQL exercises!