Department Highest Salary - Solution & Explanation
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 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.
Approach Overview
Problem Overview: Given Employee and Department tables, return the employees who earn the highest salary within each department. The result should include the department name, employee name, and salary.
Approach 1: SQL Group By and Join (Time: O(n log n), Space: O(d))
This approach first computes the maximum salary for each department using GROUP BY. A sub-result like SELECT departmentId, MAX(salary) identifies the top salary per department. Then you JOIN this result back to the Employee table to retrieve employees whose salary matches the department maximum. Finally, join with the Department table to get department names. This approach is straightforward and commonly used in SQL interview questions involving grouped aggregates.
Approach 2: Nested Queries with Join (Time: O(n log n), Space: O(d))
A nested query calculates the highest salary per department inside a derived table. That derived table is then joined with the Employee table to filter matching records. The structure typically looks like a join between Employee and a subquery that returns departmentId with MAX(salary). Compared to the first method, this version simply embeds the aggregation logic directly inside the join statement. It's useful when writing compact SQL queries and appears frequently in database interview problems.
Approach 3: SQL Subquery Approach (Time: O(n log n), Space: O(1))
This solution filters rows using a correlated subquery. For each employee row, a subquery calculates the maximum salary within that employee's department. The query keeps rows where salary = (SELECT MAX(salary) ...). The advantage is readability: the condition directly expresses the business rule. However, correlated subqueries may execute repeatedly depending on the optimizer, which can make them less efficient on very large datasets.
Approach 4: SQL Window Functions Approach (Time: O(n log n), Space: O(n))
Window functions provide a clean and modern solution. Use RANK() or DENSE_RANK() with PARTITION BY departmentId ORDER BY salary DESC. This ranks employees within each department by salary. After ranking, filter rows where the rank equals 1 to get the top earners. Window functions avoid additional joins or subqueries and make the intent very clear. Many production SQL systems prefer this pattern, especially when working with analytical queries using window functions.
Recommended for interviews: The GROUP BY + JOIN solution is the most commonly expected answer because it demonstrates strong understanding of aggregation and relational joins. Window functions are equally valid and often considered the cleanest modern SQL approach. Showing both indicates strong SQL proficiency.
Approach 1: SQL Group By and Join
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.
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.
Code
SQL
Complexity
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.
Approach 2: Nested Queries with Join
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.
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.
Code
SQL
Complexity
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.
Approach 3: SQL Subquery Approach
This 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.
This query works in two main steps:
- We perform a JOIN between the Employee and Department tables on the department ID to access department names alongside employee details.
- For each employee, we use a subquery to check if their salary equals the maximum salary in their department, filtering down to only those employees who have the department's highest salary.
Code
SQL
Complexity
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.
Approach 4: SQL Window Functions Approach
This 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.
The query involves the following major elements:
- We use a window function RANK() while partitioning by departmentId and ordering salaries in descending order, thus assigning rank 1 to the highest salaries within each department.
- We then filter these results to only include records where the rank is 1, corresponding to the highest paid employee(s) per department.
Code
SQL
Complexity
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.
Approach 5: Equi-Join + Subquery
We can use an equi-join to join the Employee table and the Department table based on Employee.departmentId = Department.id, and then use a subquery to find the highest salary for each department. Finally, we can use a WHERE clause to filter out the employees with the highest salary in each department.
Code
MySQL
Approach 6: Equi-Join + Window Function
We can use an equi-join to join the Employee table and the Department table based on Employee.departmentId = Department.id, and then use the window function rank(), which assigns a rank to each employee in each department based on their salary. Finally, we can select the rows with a rank of 1 for each department.
Code
MySQL
Complexity Comparison
| Approach | Complexity |
|---|---|
| SQL Group By and Join | Time Complexity: O(N) where N is the number of employees, assuming indexing on join fields. |
| Nested Queries with Join | Time Complexity: O(N log N) due to subquery operations and sorting for determining max. |
| SQL Subquery Approach | 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. |
| SQL Window Functions Approach | 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. |
| Equi-Join + Subquery | — |
| Equi-Join + Window Function | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Group By and Join | O(n log n) | O(d) | Most common SQL interview solution when aggregating max values per group |
| Nested Queries with Join | O(n log n) | O(d) | Compact query structure when combining aggregation results directly in joins |
| Subquery Approach | O(n log n) | O(1) | Readable solution using correlated subqueries for filtering rows |
| Window Functions | O(n log n) | O(n) | Best modern SQL approach when window functions like RANK or DENSE_RANK are supported |
Video Solution
Very Famous SQL Interview Question | Department Highest Salary • Sumit Mittal • 27,541 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Department Highest Salary easy or hard?
Department Highest Salary Python/Java solution
How to solve Department Highest Salary in O(n)?
What is the best approach for Department Highest Salary?
Is Department Highest Salary asked at Google/Amazon/Meta?
What data structure is used in Department Highest Salary?
What is the time complexity of Department Highest Salary?
Ready to solve this problem?
Practice Department Highest Salary with our built-in code editor and test cases.
Practice on FleetCode