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:
The goal of this problem is to return the top three distinct salaries for each department along with employee and department information. Since multiple employees can share the same salary, the solution must handle ties correctly while still limiting the result to the top three salary levels.
A common and efficient strategy is to use SQL window functions. By applying DENSE_RANK() or RANK() with PARTITION BY department and ordering salaries in descending order, you can assign a rank to each salary within its department. After ranking, filter rows where the rank is less than or equal to three. This ensures that only the top three salary tiers per department are returned.
An alternative method involves a correlated subquery that counts how many distinct salaries are higher than the current employee’s salary within the same department. If fewer than three higher salaries exist, the employee belongs in the result set.
The window function approach is typically cleaner and performs well on large datasets, especially when supported by modern SQL engines.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Window Function with DENSE_RANK() | O(n log n) due to sorting within partitions | O(n) |
| Correlated Subquery with DISTINCT Salary Count | O(n^2) in worst case depending on database optimization | O(1) to O(n) |
Frederik Müller
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.
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.
1const employees = [
2 {id: 1, name: 'Joe', salary: 85000, departmentId: 1},
3 {id: 2, name: 'Henry', salary: 80000, departmentId: 2},
4 {id: 3, name: 'Sam', salary: 60000, departmentId: 2},
5 {id: 4, name: 'Max', salary: 90000, departmentId: 1},
6 {id: 5, name: 'Janet', salary: 69000, departmentId: 1},
7 {id: 6, name: 'Randy', salary: 85000, departmentId: 1},
8 {id: 7, name: 'Will', salary: 70000, departmentId: 1}
9];
10const departments = [
11 {id: 1, name: 'IT'},
12 {id: 2, name: 'Sales'}
13];
14
15const groupByDepartment = (employees) => {
16 const deptMap = new Map();
17 employees.forEach(emp => {
18 if (!deptMap.has(emp.departmentId)) {
19 deptMap.set(emp.departmentId, []);
20 }
21 deptMap.get(emp.departmentId).push(emp);
22 });
23 return deptMap;
24};
25
26const deptEmployees = groupByDepartment(employees);
27
28const result = [];
29
30for (let {id, name} of departments) {
31 const empList = deptEmployees.get(id);
32 const uniqueSalaries = [...new Set(empList.map(emp => emp.salary))];
33 uniqueSalaries.sort((a, b) => b - a);
34 const topSalaries = uniqueSalaries.slice(0, 3);
35
36 empList.forEach(emp => {
37 if (topSalaries.includes(emp.salary)) {
38 result.push({Department: name, Employee: emp.name, Salary: emp.salary});
39 }
40 });
41}
42
43console.log(result);In JavaScript, we use a Map to group employees by their department. The use of ES6 features like Set helps extract unique salaries. The solution then involves filtering employees by those who have salaries within the top three unique salaries obtained per department.
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.
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.
1import java.util.*;
2
3public class TopSalaries
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
DENSE_RANK handles duplicate salaries correctly by assigning the same rank to equal salary values. This ensures that if multiple employees share the same salary, they are treated as part of the same ranking tier. It helps return all employees whose salaries fall within the top three distinct salary levels.
Yes, variations of this problem appear in SQL interview rounds at large tech companies. Interviewers often use it to test knowledge of window functions, ranking logic, and handling duplicates in grouped datasets.
The most optimal approach typically uses SQL window functions like DENSE_RANK() with PARTITION BY department and ORDER BY salary DESC. This assigns ranks to salaries within each department, allowing you to filter the top three ranks efficiently. It is concise and performs well on modern database engines.
Window functions are the key concept for this problem. Functions like DENSE_RANK() or RANK() allow you to compute rankings within grouped partitions such as departments. This makes it easy to identify the top salary tiers without complex joins or nested queries.
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.