LeetCode 185: Department Top Three Salaries Solution in SQL Explained

Problem Statement

In LeetCode 185, 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 top three highest salaries in each department (including ties for third place), in a result table with columns Department, Employee, and Salary, ordered arbitrarily. Departments with fewer than three employees return all available employees. This extends LeetCode 184: Department Highest Salary, differing from absence detection like LeetCode 183: Customers Who Never Order.

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   | 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  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+
Explanation:
<ul>
<li>IT (id=1): Max (90000), Joe (85000), Randy (85000), Will (70000), Janet (69000) → Max, Joe, Randy (top 3, ties at 85000).</li>
<li>Sales (id=2): Henry (80000), Sam (60000) → Henry, Sam (only 2 employees).</li>
</ul>

This shows we’re finding the top three salaries per department.

Understanding the Problem

How do you solve LeetCode 185: Department Top Three Salaries in SQL? We need to:

• Identify the top three salaries (including ties for third) per departmentId in Employee.
• Match these employees to their departments in Department.
• Return Department.name, Employee.name, and Employee.salary for these top earners.
• Include departments with fewer than three employees fully.

For the example, IT’s top three are Max (90000), Joe and Randy (85000, tied), excluding Will (70000); Sales has only Henry and Sam. We need a query to rank and filter efficiently, not a simple max like LeetCode 184: Department Highest Salary. We’ll use: 1. Dense Rank Window Function: Efficient, elegant—our best solution. 2. Subquery with Count: Alternative approach.

Let’s dive into the best solution.

Best Solution: Dense Rank Window Function Approach

Explanation

Dense Rank Window Function finds top three salaries by:

• Using DENSE_RANK() over salary partitioned by departmentId, ordered descending.
• Filtering where rank ≤ 3 (top three, including ties at third).
• Joining with Department to get names.
• Selecting Department.name, Employee.name, Employee.salary.

This ensures O(n log n) time with window functions (optimized by database), O(n) space for ranking, and simplicity with modern SQL support (e.g., MySQL 8.0+), making it the most efficient and clear solution.

For the example:

• IT: Max=1, Joe=2, Randy=2, Will=3, Janet=4 → Max, Joe, Randy (≤ 3).
• Sales: Henry=1, Sam=2 → Henry, Sam (≤ 3).

Step-by-Step Example

Example: Employee and Department tables as above

Goal: Return table with Department, Employee, Salary.

• Step 1: Add dense rank in Employee.
• DENSE_RANK() OVER (PARTITION BY departmentId ORDER BY salary DESC):
• IT (1): Max=1, Joe=2, Randy=2, Will=3, Janet=4.
• Sales (2): Henry=1, Sam=2.
• Step 2: Filter rank ≤ 3.
• IT: Max (1), Joe (2), Randy (2).
• Sales: Henry (1), Sam (2).
• Step 3: Join with Department.
• IT: Max, Joe, Randy.
• Sales: Henry, Sam.
• Step 4: Select columns.
• Result: "IT", "Max", 90000; "IT", "Joe", 85000; "IT", "Randy", 85000; "Sales", "Henry", 80000; "Sales", "Sam", 60000.
• Finish: Return table.

How the Code Works (Dense Rank Window Function) – 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
    -- Dept name, employee name, salary (e.g., "IT", "Max", 90000)

-- Line 2: Subquery with dense rank
FROM (
    SELECT 
        name, 
        salary, 
        departmentId,
        DENSE_RANK() OVER (
            PARTITION BY departmentId 
            ORDER BY salary DESC
            -- Rank within each dept (e.g., Max=1, Joe=2, Randy=2)
        ) AS rnk
    FROM 
        Employee
    -- Base table (e.g., Joe, Henry, etc.)
) e
-- Alias subquery as e

-- Line 3: Join with Department
INNER JOIN 
    Department d
    -- Department table (e.g., IT, Sales)
ON 
    e.departmentId = d.id
    -- Match dept ids (e.g., 1=1 for IT)

-- Line 4: Filter top 3 ranks
WHERE 
    e.rnk <= 3
    -- Keep ranks 1, 2, 3 (e.g., Max, Joe, Randy)

This detailed breakdown clarifies how the dense rank window function efficiently finds the top three salaries.

Alternative: Subquery with Count Approach

Explanation

Subquery with Count finds top three salaries by:

• For each employee, count distinct higher salaries in the same department.
• Filter where count < 3 (top three, including ties at third).
• Join with Department.
• Select Department.name, Employee.name, Employee.salary.

It’s a practical alternative, O(n²) time without indexing (O(n log n) with indexing), O(n) space for subquery results, but more complex and less efficient than window functions, though compatible with older SQL systems.

For the example:

• IT: Max=0, Joe=1, Randy=1, Will=2, Janet=3 → Max, Joe, Randy (< 3).
• Sales: Henry=0, Sam=1 → Henry, Sam (< 3).

Step-by-Step Example (Alternative)

For the same example:

• Step 1: Subquery counts higher salaries.
• Max (90000, 1): 0 higher → 0.
• Joe (85000, 1): 1 (90000) → 1.
• Randy (85000, 1): 1 (90000) → 1.
• Will (70000, 1): 2 (90000, 85000) → 2.
• Janet (69000, 1): 3 → 3.
• Henry (80000, 2): 0 → 0.
• Sam (60000, 2): 1 (80000) → 1.
• Step 2: Filter count < 3.
• Max, Joe, Randy, Henry, Sam.
• Step 3: Join with Department.
• Same output.

How the Code Works (Subquery with Count)

Copy codeSELECT 
    d.name AS Department, 
    e1.name AS Employee, 
    e1.salary AS Salary
FROM 
    Employee e1
INNER JOIN 
    Department d
ON 
    e1.departmentId = d.id
WHERE (
    SELECT COUNT(DISTINCT e2.salary)
    FROM Employee e2
    WHERE e2.departmentId = e1.departmentId 
    AND e2.salary > e1.salary
) < 3

Complexity

• Dense Rank Window Function:
• Time: O(n log n) – window computation (optimized by database).
• Space: O(n) – rank storage.
• Subquery with Count:
• Time: O(n²) – subquery per row (O(n log n) with indexing).
• Space: O(n) – subquery result.

Efficiency Notes

Dense Rank Window Function is the best solution with O(n log n) time and O(n) space, offering efficiency and clarity with modern SQL—Subquery with Count uses O(n²) time without optimization, requiring more space and complexity, making it portable but less efficient.

Key Insights

• DENSE_RANK: Top 3 with ties.
• Count: Higher salary check.
• Join: Links departments.

Additional Example

Copy codeEmployee:
| 1 | Ann | 50000 | 1 |
| 2 | Bob | 60000 | 1 |
Department:
| 1 | HR |
Output:
| HR | Bob | 60000 |
| HR | Ann | 50000 |
Explanation: HR has only 2, both included.

Edge Cases

• Fewer than 3: All included.
• Ties at 3rd: All tied included.
• No Employees: Excluded (join).

Both solutions handle these well.

Final Thoughts

LeetCode 185: Department Top Three Salaries in SQL is a challenging ranking puzzle. The Dense Rank Window Function solution excels with its efficiency and elegance, while Subquery with Count offers a traditional approach. Want more SQL? Try LeetCode 184: Department Highest Salary for a simpler case or explore Python Basics for coding skills. Ready to practice? Solve LeetCode 185 on LeetCode with the example tables, aiming for the top three—test your skills now!