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:
Problem Overview: You are given employee and department data and need to return employees whose salary ranks in the top three distinct salaries within their department. Each result should include the department name, employee name, and salary. The main challenge is grouping employees by department and selecting the highest three unique salaries for each group.
Approach 1: SQL-like Grouping and Filtering (O(n log n) time, O(n) space)
This approach mimics how the query would be written in SQL using ranking functions like DENSE_RANK(). First, group employees by departmentId. Inside each group, sort employees by salary in descending order. Then iterate through the sorted list while tracking distinct salaries. Assign a rank whenever a new salary appears and stop collecting results once the rank exceeds three. This guarantees that employees tied at the same salary share the same rank. The algorithm relies on grouping and sorting, which results in O(n log n) time due to sorting within departments and O(n) space for storing grouped data.
This method is intuitive if you already think in relational queries. It closely models real database execution plans where grouping and ranking operations determine top results per partition. Concepts overlap with database queries and sorting strategies used in analytical workloads.
Approach 2: Using Data Structures and Sorting (O(n log n) time, O(n) space)
This implementation focuses more on algorithmic data structures. Start by building a map from departmentId to a list of employees. For each department list, sort employees by salary in descending order. Traverse the sorted list and track distinct salary values using a variable or a small set. Once you have encountered three unique salaries, stop processing further entries unless they match the third salary value (to preserve ties). Add qualifying employees to the final result structure.
The main operations are inserting employees into a hash map and sorting department-level lists. Hash map grouping runs in O(n), while sorting dominates with O(n log n). Space complexity stays O(n) because every employee is stored in the grouped structure. This solution emphasizes practical data organization using hash maps and deterministic ordering with sorting.
Recommended for interviews: The grouping plus sorting approach is what most interviewers expect. It demonstrates you understand partitioning data, handling ties correctly, and managing ranking logic without built-in SQL functions. Mentioning how SQL solves the same problem with DENSE_RANK() shows strong system awareness, while implementing the grouped sorting solution proves algorithmic skill.
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.
JavaScript
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.
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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| SQL-like Grouping and Filtering | O(n log n) | O(n) | When modeling SQL behavior such as DENSE_RANK or top-k per group queries |
| Data Structures + Sorting | O(n log n) | O(n) | General programming solution when implementing grouping and ranking logic without SQL |
LeetCode 185: Department Top Three Salaries [SQL] • Frederik Müller • 15,937 views views
Watch 9 more video solutions →Practice Department Top Three Salaries with our built-in code editor and test cases.
Practice on FleetCode