184. Department Highest Salary Solution

The problem

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.

MySQL

SELECT 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.

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.

Try this approach in the editor

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.

MySQL

WITH MaxSalaries AS ( SELECT departmentId, MAX(salary) AS max_salary FROM Employee GROUP BY departmentId ) SELECT d.name AS Department, e.name AS Employee, e.salary FROM Employee e JOIN MaxSalaries ms ON e.departmentId = ms.departmentId AND e.salary = ms.max_salary JOIN Department d ON e.departmentId = d.id

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.

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.

Try this approach in the editor

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.

MySQL

SELECT d.name AS Department, e.name AS Employee, e.salary AS Salary
FROM Employee e
JOIN Department d ON e.departmentId = d.id
WHERE e.salary = (SELECT MAX(salary) FROM Employee WHERE departmentId = e.departmentId);

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.

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.

Try this approach in the editor

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.

MySQL

SELECT Department, Employee, Salary
FROM (
  SELECT d.name AS Department, e.name AS Employee, e.salary AS Salary, 
         RANK() OVER (PARTITION BY e.departmentId ORDER BY e.salary DESC) as r
  FROM Employee e
  JOIN Department d ON e.departmentId = d.id
) ranked_employee
WHERE r = 1;

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.

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.

Try this approach in the editor

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. Space Complexity: O(N) for storing the intermediate join results and final results.
Nested Queries with Join	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.
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. Space Complexity: O(N), for storing the result set.
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. Space Complexity: O(N), for storing ranking results and generating output.

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

Frequently asked questions

Is Department Highest Salary easy or hard?

Department Highest Salary is generally rated medium difficulty. The challenge comes from combining aggregation with joins or window functions while returning the correct employee records. Developers comfortable with GROUP BY, subqueries, and ranking functions usually solve it quickly.

Department Highest Salary Python/Java solution

This problem is typically solved directly in SQL rather than Python or Java because it operates on relational tables. In application code, the logic would involve grouping employees by department and selecting the maximum salary per group, which mirrors the SQL GROUP BY or ranking approach.

How to solve Department Highest Salary in O(n)?

Pure O(n) time is uncommon because SQL engines usually perform grouping or sorting internally. However, with proper indexing on departmentId and salary, the database can approach near linear performance. In practice, the GROUP BY + JOIN or window function solution performs efficiently for large datasets.

What is the best approach for Department Highest Salary?

The most common solution uses GROUP BY to compute the maximum salary for each department and then joins that result back to the Employee table. This approach clearly separates aggregation from filtering and works efficiently in most SQL databases. Many engineers also prefer the window function approach using RANK() or DENSE_RANK() because it produces cleaner queries.

Is Department Highest Salary asked at Google/Amazon/Meta?

Department Highest Salary represents a classic SQL interview pattern involving grouping and maximum values per category. Variations of this problem appear in interviews at companies like Amazon, Meta, and Google, especially for data engineer, backend, and analytics roles where SQL proficiency is required.

What data structure is used in Department Highest Salary?

The problem relies on relational database operations rather than traditional in-memory data structures. SQL engines internally use grouping structures, sorting mechanisms, and hash aggregations to compute maximum salaries per department. Window functions also rely on partitioned sorting operations.

What is the time complexity of Department Highest Salary?

Most SQL solutions run in roughly O(n log n) time because the database engine groups or sorts rows by department and salary. The space complexity is typically O(d), where d is the number of departments, to store aggregated results. Window functions may use O(n) temporary space depending on the execution plan.

Department Highest Salary solution and explanation

The problem

Approach overview

Approach 1: SQL Group By and Join

Approach 2: Nested Queries with Join

Approach 3: SQL Subquery Approach

Approach 4: SQL Window Functions Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Department Highest Salary solution and explanation

The problem

Approach overview

Approach 1: SQL Group By and Join

Approach 2: Nested Queries with Join

Approach 3: SQL Subquery Approach

Approach 4: SQL Window Functions Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems