LeetCode 184: Department Highest Salary Solution in SQL Explained

Problem Statement

In LeetCode 184, you’re given two tables:

• Employee:
• id (int, primary key)
• name (varchar)
• salary (int)
• departmentId (int, foreign key to Department.id, nullable)
• Department:
• id (int, primary key)
• name (varchar)

Your task is to write an SQL query to return the employee name, department name, and salary for the employee with the highest salary in each department, in a result table with columns Department, Employee, and Salary, ordered arbitrarily. If a department has no employees, it should not appear in the result. This differs from absence detection like LeetCode 183: Customers Who Never Order, focusing on maximum salary per group across two tables.

Constraints

• Employee has at least 1 row.
• Department has at least 1 row.
• departmentId can be null or reference Department.id.
• Multiple employees may exist per department.

Example

Let’s see a case:

Copy codeEmployee 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  |
| IT         | Max      | 90000  |
| Sales      | Henry    | 80000  |
+------------+----------+--------+
Explanation:
<ul>
<li>IT (id=1): Joe (70000), Jim (90000), Max (90000) → Jim and Max tie at 90000.</li>
<li>Sales (id=2): Henry (80000), Sam (60000) → Henry at 80000.</li>
<li>Both top earners per department included.</li>
</ul>

This shows we’re finding top salaries per department.

Understanding the Problem

How do you solve LeetCode 184: Department Highest Salary in SQL? We need to:

• Identify the highest salary for each departmentId in Employee.
• Match these employees to their departments in Department.
• Return Department.name, Employee.name, and Employee.salary for all top earners (including ties).
• Exclude departments with no employees.

For the example, IT has Jim and Max tied at 90000, Sales has Henry at 80000. We need a query to group, find maximums, and join efficiently, not a duplicate task like LeetCode 182: Duplicate Emails. We’ll use: 1. Inner Join with Subquery: Clear, efficient—our best solution. 2. Window Function with Rank: Alternative approach.

Let’s dive into the best solution.

Best Solution: Inner Join with Subquery Approach

Explanation

Inner Join with Subquery finds top earners by:

• Subquery: Group Employee by departmentId, find MAX(salary) per group.
• Join Employee with this subquery on departmentId and salary to get all top earners (including ties).
• Join with Department to get department names.
• Select Department.name, Employee.name, Employee.salary.

This ensures O(n) time with indexing on departmentId and salary, O(n) space for subquery results, and clarity by combining aggregation and joining, making it efficient and straightforward.

For the example:

• Subquery: IT→90000, Sales→80000.
• Join: Jim, Max (90000, IT), Henry (80000, Sales).
• Output: IT, Jim, 90000; IT, Max, 90000; Sales, Henry, 80000.

Step-by-Step Example

Example: Employee and Department tables as above

Goal: Return table with Department, Employee, Salary.

• Step 1: Subquery for max salaries per department.
• GROUP BY departmentId:
• departmentId=1: [70000, 90000, 90000] → 90000.
• departmentId=2: [80000, 60000] → 80000.
• Result: (1, 90000), (2, 80000).
• Step 2: Join Employee with subquery.
• e.departmentId = m.departmentId AND e.salary = m.salary:
• (2, Jim, 90000, 1) → (1, 90000) → match.
• (5, Max, 90000, 1) → (1, 90000) → match.
• (3, Henry, 80000, 2) → (2, 80000) → match.
• Step 3: Join with Department.
• d.id = e.departmentId:
• Jim → IT.
• Max → IT.
• Henry → Sales.
• Step 4: Select columns.
• Result: "IT", "Jim", 90000; "IT", "Max", 90000; "Sales", "Henry", 80000.
• Finish: Return table.

How the Code Works (Inner Join with Subquery) – Detailed Line-by-Line Explanation

Here’s the SQL query with a thorough breakdown:

Copy code-- Line 1: Select required columns
SELECT 
    d.name AS Department, 
    e.name AS Employee, 
    e.salary AS Salary
    -- Department name, employee name, salary (e.g., "IT", "Jim", 90000)

-- Line 2: Join Employee with subquery
FROM 
    Employee e
    -- Base employee table (e.g., Joe, Jim, etc.)
INNER JOIN 
    (SELECT 
         departmentId, 
         MAX(salary) AS salary
     FROM 
         Employee
     GROUP BY 
         departmentId) m
    -- Subquery for max salary per dept (e.g., (1, 90000), (2, 80000))
ON 
    e.departmentId = m.departmentId 
    AND e.salary = m.salary
    -- Match employees to max salaries (e.g., Jim, Max to 90000)

-- Line 3: Join with Department
INNER JOIN 
    Department d
    -- Department table (e.g., IT, Sales)
ON 
    e.departmentId = d.id
    -- Link to department names (e.g., 1=1 for IT)

This detailed breakdown clarifies how the inner join with subquery efficiently finds top earners per department.

Alternative: Window Function with Rank Approach

Explanation

Window Function with Rank uses RANK() to identify top earners:

• Use RANK() over salary partitioned by departmentId in descending order.
• Filter where rank = 1 (top salary, including ties).
• Join with Department to get names.
• Select Department.name, Employee.name, Employee.salary.

It’s a practical alternative, O(n log n) time with window functions (database-dependent), O(n) space for ranking, but requires modern SQL support (e.g., MySQL 8.0+), and may be less intuitive than the join approach.

For the example:

• Rank: Joe=2, Jim=1, Max=1 (IT); Henry=1, Sam=2 (Sales).
• Filter rank=1 → Jim, Max, Henry.

Step-by-Step Example (Alternative)

For the same example:

• Step 1: Add rank column.
• RANK() OVER (PARTITION BY departmentId ORDER BY salary DESC):
• IT (1): Jim=1, Max=1, Joe=3.
• Sales (2): Henry=1, Sam=2.
• Step 2: Filter rank = 1.
• Jim, Max (90000, 1), Henry (80000, 2).
• Step 3: Join with Department.
• IT: Jim, Max; Sales: Henry.
• Finish: Same output.

How the Code Works (Window Function)

Copy codeSELECT 
    d.name AS Department, 
    e.name AS Employee, 
    e.salary AS Salary
FROM (
    SELECT 
        name, 
        salary, 
        departmentId,
        RANK() OVER (PARTITION BY departmentId ORDER BY salary DESC) AS rnk
    FROM 
        Employee
) e
INNER JOIN 
    Department d
ON 
    e.departmentId = d.id
WHERE 
    e.rnk = 1

Complexity

• Inner Join with Subquery:
• Time: O(n) – join and group with indexing.
• Space: O(n) – subquery result.
• Window Function with Rank:
• Time: O(n log n) – window computation (optimized by database).
• Space: O(n) – rank storage.

Efficiency Notes

Inner Join with Subquery is the best solution with O(n) time and O(n) space, offering compatibility and clarity—Window Function with Rank uses O(n log n) time and O(n) space, requiring modern SQL support, making it elegant but less portable and slightly less efficient.

Key Insights

• Subquery: Groups max salaries.
• RANK: Assigns positions.
• Ties: Both handle multiple top earners.

Additional Example

Copy codeEmployee:
| 1 | Ann | 50000 | 1 |
| 2 | Bob | 60000 | 1 |
Department:
| 1 | HR |
Output:
| HR | Bob | 60000 |
Explanation: Bob is HR’s top earner.

Edge Cases

• No Employees in Dept: Excluded (inner join).
• Ties: All top salaries included.
• Null Dept: Excluded (join).

Both solutions handle these well.

Final Thoughts

LeetCode 184: Department Highest Salary in SQL is a rewarding grouping challenge. The Inner Join with Subquery solution excels with its efficiency and simplicity, while Window Function with Rank offers a modern alternative. Want more SQL? Try LeetCode 183: Customers Who Never Order for joins or explore Python Basics for coding skills. Ready to practice? Solve LeetCode 184 on LeetCode with the example tables, aiming for the top earners—test your skills now!