Skip to main content
Talentd

Department Top Three Salaries - Solution & Explanation

HardDatabase9 min readAsked at: Amazon, Microsoft, Meta +8
Practice this problem

Problem Statement

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 column) 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.
Each row of this table indicates the ID of a department and its name.

 

A company's executives are interested in seeing who earns the most money in each of the company's departments. A high earner in a department 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.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Employee table:
+----+-------+--------+--------------+
| id | name  | salary | departmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 85000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
| 5  | Janet | 69000  | 1            |
| 6  | Randy | 85000  | 1            |
| 7  | Will  | 70000  | 1            |
+----+-------+--------+--------------+
Department table:
+----+-------+
| id | name  |
+----+-------+
| 1  | IT    |
| 2  | Sales |
+----+-------+
Output: 
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Joe      | 85000  |
| IT         | Randy    | 85000  |
| IT         | Will     | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+
Explanation: 
In the IT department:
- Max earns the highest unique salary
- Both Randy and Joe earn the second-highest unique salary
- Will earns the third-highest unique salary

In the Sales department:
- Henry earns the highest salary
- Sam earns the second-highest salary
- There is no third-highest salary as there are only two employees

 

Constraints:

  • There are no employees with the exact same name, salary and department.

Approach Overview

Problem Overview: You are given employee salary records and department information. The task is to return employees whose salary ranks in the top three distinct salaries within their department. Multiple employees can share the same salary, so ranking must behave like DENSE_RANK rather than a simple top-three list.

Approach 1: SQL-like Grouping and Filtering (O(n log n) time, O(n) space)

This method mirrors how you would solve the problem in SQL using GROUP BY and ranking. First, group employees by department using a dictionary or map. Inside each group, collect the distinct salary values and sort them in descending order. The third highest distinct salary becomes the threshold for that department. Finally, iterate through the employees again and select those whose salary is greater than or equal to this threshold.

The key insight is separating salary ranking from employee filtering. You compute the top three distinct salaries first, then match employees against that set. Sorting each department’s salaries dominates the runtime, resulting in O(n log n) time overall with O(n) extra space for grouped data. This approach closely reflects database logic and is easy to implement in Python or JavaScript using maps and arrays. It heavily relies on concepts similar to hash maps and database grouping.

Approach 2: Using Data Structures and Sorting (O(n log n) time, O(n) space)

Another practical solution groups employees by department and sorts employees within each department by salary in descending order. While scanning the sorted list, track the number of distinct salary levels encountered. Each time the salary value changes, increase the rank counter. Continue collecting employees until the rank exceeds three.

This approach avoids building a separate salary set because the sorting order naturally exposes salary ranks. A simple loop maintains the current rank and ensures employees tied with the same salary share the same position. Sorting each department’s employee list drives the complexity to O(n log n) time with O(n) space for grouping. It’s straightforward to implement in Java using collections and comparators and relies on standard sorting techniques.

Recommended for interviews: The grouping plus ranking approach is what most interviewers expect. It shows you understand how to partition data by department and handle duplicate salaries correctly using dense ranking. A brute-force scan of every employee against all others demonstrates the idea but scales poorly. The grouped sorting or SQL-style ranking solution clearly communicates both algorithmic thinking and familiarity with real-world database queries.

Approach 1: SQL-like Grouping and Filtering

This approach involves grouping employees by their department and filtering their salaries to get the top three unique salaries for each department. By using structures such as dictionaries in our programming languages, we can mimic SQL-like GROUP BY and LIMIT operations. This involves two major steps: Grouping employees by department and then filtering by top salaries.

This solution utilizes Python dictionaries to group employees by department and process their salaries. We maintain a list of top unique salaries per department using a sorted list of unique salaries and filter employees to obtain only those with salaries in this list.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n log n), dominated by the sorting step where n is the number of employees. Space Complexity: O(n), to store grouped employees and unique salaries.

Try this approach in the editor →

Approach 2: Using Data Structures and Sorting

This approach involves using a more sophisticated data structure to keep track of top salaries and employees proactively while grouping the employees by department. In certain languages, this can be achieved efficiently using priority queues or heaps. However, this example shows a simpler method utilizing sorted structures.

This Java solution groups employees by departments and sorts the list by salary to filter the top three unique salaries. The use of lists and sets helps us manage unique top salaries and efficiently output all qualifying employees.

Code

Java

Java

Complexity

Time Complexity: O(n log n), caused by the sort operation on each department's employee list. Space Complexity: O(n), due to storage needs for set and list of employees per department.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonMySQL

Python

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
SQL-like Grouping and Filtering

Time Complexity: O(n log n), dominated by the sorting step where n is the number of employees. Space Complexity: O(n), to store grouped employees and unique salaries.

Using Data Structures and Sorting

Time Complexity: O(n log n), caused by the sort operation on each department's employee list. Space Complexity: O(n), due to storage needs for set and list of employees per department.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
SQL-like Grouping and FilteringO(n log n)O(n)Best when modeling the problem like a SQL query with department grouping and salary ranking
Data Structures with Sorting per DepartmentO(n log n)O(n)Useful when implementing in languages like Java using collections and sorted lists

Video Solution

LeetCode 185: Department Top Three Salaries [SQL] • Frederik Müller • 17,873 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Department Top Three Salaries easy or hard?
Department Top Three Salaries is classified as a hard database problem because it requires handling grouped ranking with duplicate salary values. The difficulty comes from implementing dense ranking logic correctly rather than from complex algorithms.
Department Top Three Salaries Python/Java solution
Python and JavaScript solutions usually build a dictionary mapping departments to salary lists, then compute the top three distinct salaries before filtering employees. Java implementations often group employees using maps and sort each department's employee list by salary to track the top three ranks.
How to solve Department Top Three Salaries in O(n)?
A near O(n) approach is possible if each department tracks only the top three distinct salaries while scanning employees. Using a hash map from department to a small ordered structure of size three avoids full sorting. In practice, many implementations still rely on sorting because it keeps the logic simpler and easier to maintain.
What is the best approach for Department Top Three Salaries?
The most practical approach groups employees by department and determines the top three distinct salary levels within each group. After computing these salary ranks, filter employees whose salary falls within those levels. This mirrors SQL window functions such as DENSE_RANK and runs in O(n log n) time due to sorting.
Is Department Top Three Salaries asked at Google/Amazon/Meta?
Department Top Three Salaries is commonly used in database interview preparation and appears in SQL-focused interviews at companies such as Amazon, Google, and Meta. It tests understanding of ranking functions, grouping, and handling duplicate salary values within partitions.
What data structure is used in Department Top Three Salaries?
Typical solutions use hash maps to group employees by department and arrays or lists to store salary values. Sorting or ranking logic is then applied within each group. In SQL environments, window functions like DENSE_RANK conceptually replace these structures.
What is the time complexity of Department Top Three Salaries?
Most implementations run in O(n log n) time because salaries within each department are sorted to determine ranking. The space complexity is O(n) for storing grouped employee data and salary lists. If a database engine handles ranking internally, the logical complexity is still dominated by sorting.

Ready to solve this problem?

Practice Department Top Three Salaries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary