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 columns) 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. It is guaranteed that department name is not NULL.
Each row of this table indicates the ID of a department and its name.
Write a solution to find employees who have the highest salary 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 | 70000 | 1 | | 2 | Jim | 90000 | 1 | | 3 | Henry | 80000 | 2 | | 4 | Sam | 60000 | 2 | | 5 | Max | 90000 | 1 | +----+-------+--------+--------------+ Department table: +----+-------+ | id | name | +----+-------+ | 1 | IT | | 2 | Sales | +----+-------+ Output: +------------+----------+--------+ | Department | Employee | Salary | +------------+----------+--------+ | IT | Jim | 90000 | | Sales | Henry | 80000 | | IT | Max | 90000 | +------------+----------+--------+ Explanation: Max and Jim both have the highest salary in the IT department and Henry has the highest salary in the Sales department.
The Department Highest Salary problem requires identifying the employee(s) who earn the maximum salary within each department. The core idea is to compare employee salaries within the same department and return those that match the department’s highest value.
A common strategy is to first compute the maximum salary per department using GROUP BY and MAX(). This result can then be combined with the employee table using a JOIN so that only employees whose salary equals the department’s maximum are selected. Another modern SQL approach uses window functions such as DENSE_RANK() or RANK() with PARTITION BY departmentId and ordering by salary descending. Employees ranked first in each partition represent the highest earners.
Both methods rely on efficient grouping or partitioning of records. Understanding joins, aggregation, and window functions is key to solving this database interview problem effectively.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| GROUP BY + MAX() with JOIN | O(N log N) | O(N) |
| Window Function (DENSE_RANK / RANK) | O(N log N) | O(N) |
Frederik Müller
This approach involves using SQL queries to retrieve the required data. We'll utilize the GROUP BY clause to segregate data by department, and the MAX function to determine the highest salary within each department. By joining the Employee table and the Department table, we can extract both the department name and the pertinent employee information.
Time Complexity: O(N) where N is the number of employees, assuming indexing on join fields.
Space Complexity: O(N) for storing the intermediate join results and final results.
1SELECT dept.name AS Department, e.name AS Employee, e.salary AS Salary FROM Employee e JOIN Department dept ON e.departmentId = dept.id WHERE (e.departmentId, e.salary) IN ( SELECT departmentId, MAX(salary) FROM Employee GROUP BY departmentId )Here, we first perform a JOIN operation between the Employee and Department tables based on departmentId. The subquery inside filters out the department-wise maximum salary using GROUP BY and MAX functions. The result is a list of employees with the highest salaries in each department, which is then retrieved using the outer query.
This method leverages nested SQL queries to first compute the maximum salary in each department and then joins these results back to the Employee table. The primary objective is to match employees with these max salaries and retrieve both their names and department names.
Time Complexity: O(N log N) due to subquery operations and sorting for determining max.
Space Complexity: O(N) for storing intermediate JOIN and final results.
1WITH MaxSalaries AS ( SELECT departmentId, MAX(salary) AS max_salary FROM Employee GROUP BYThis approach involves using an SQL subquery in conjunction with the JOIN operation. We first determine the maximum salary for each department by grouping the Employee table by departmentId. Then, we use this result to join back to the Employee table and select the employee records that match these maximum salaries.
Time Complexity: O(N * M), where N is the number of employees and M is the number of departments. The subquery is executed for each employee record, comparing salaries within the department.
Space Complexity: O(N), for storing the result set.
1SELECT d.name AS Department, e.name AS Employee, e.salary AS Salary
2This approach utilizes SQL window functions to eliminate the need for subqueries. By using the RANK() function over each department's salary list, you can directly identify which employees have the maximum salary in their respective departments.
Time Complexity: O(N log N), where N is the number of employees. The RANK function operates in a similar way to a sort operation within each partition of the dataset.
Space Complexity: O(N), for storing ranking results and generating output.
1SELECT Department, Employee, Salary
2FROM (
3 SELECT d.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
Yes, similar SQL problems involving grouping, ranking, and joins are common in FAANG and other top tech company interviews. They test a candidate's understanding of relational data and query optimization.
A common optimal approach is to calculate the maximum salary for each department using GROUP BY and MAX(), then join it with the employee table to find employees matching that salary. Another efficient approach uses window functions like DENSE_RANK() partitioned by department to identify the top salary in each group.
Key SQL concepts include joins, aggregation functions like MAX(), and GROUP BY. Window functions such as RANK() or DENSE_RANK() are also useful for ranking employees within each department without additional joins.
Since this is a SQL problem, relational database features like aggregation and window functions are most effective. These allow efficient grouping and ranking of rows within partitions defined by department IDs.
We utilize a Common Table Expression (CTE) to store maximum salaries per department (MaxSalaries) and join this temporary result back with the Employee table to filter out those employees who have these maximum salaries. Another join fetches department names from the Department table. This ensures that the results list the highest-paid employees by department.
This query works in two main steps:
The query involves the following major elements: