Problem Statement

We need to find all employees whose salary belongs to the top 3 unique salaries within their department.

A high earner is an employee whose salary is among the top three distinct salaries in their department.

Given two tables:

Employee

id	name	salary	departmentId

Department

id	name

Example

Employee 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

Expected Output

Department	Employee	Salary
IT	Max	90000
IT	Joe	85000
IT	Randy	85000
IT	Will	70000
Sales	Henry	80000
Sales	Sam	60000

Understanding the Key Requirement

The problem does not ask for the top 3 employees.

It asks for employees earning one of the top 3 unique salaries.

For example:

IT Department Salaries

Salary
90000
85000
85000
70000
69000

Unique salaries:

Top 3 unique salaries:

90000
85000
70000

Therefore:

Max (90000) → Include
Joe (85000) → Include
Randy (85000) → Include
Will (70000) → Include
Janet (69000) → Exclude

Why DENSE_RANK() Is the Best Choice

SQL provides three common ranking functions:

ROW_NUMBER()

ROW_NUMBER()

Result:

Salary	Row Number
90000	1
85000	2
85000	3
70000	4

Will (70000) gets excluded.

❌ Incorrect

RANK()

RANK()

Result:

Salary	Rank
90000	1
85000	2
85000	2
70000	4

Will gets rank 4.

❌ Incorrect

DENSE_RANK()

DENSE_RANK()

Result:

Salary	Rank
90000	1
85000	2
85000	2
70000	3
69000	4

This perfectly matches the requirement.

✅ Correct

Optimal SQL Solution

WITH RankedEmployees AS
(
    SELECT
        d.name AS Department,
        e.name AS Employee,
        e.salary AS Salary,
        DENSE_RANK() OVER
        (
            PARTITION BY e.departmentId
            ORDER BY e.salary DESC
        ) AS salary_rank
    FROM Employee e
    JOIN Department d
        ON e.departmentId = d.id
)

SELECT
    Department,
    Employee,
    Salary
FROM RankedEmployees
WHERE salary_rank <= 3;

Step-by-Step Explanation

Step 1: Join Employee and Department

FROM Employee e
JOIN Department d
ON e.departmentId = d.id

This gives us department names along with employee information.

Step 2: Rank Salaries Within Each Department

DENSE_RANK() OVER
(
    PARTITION BY e.departmentId
    ORDER BY e.salary DESC
)

PARTITION BY creates separate ranking for each department.
ORDER BY salary DESC ranks higher salaries first.
DENSE_RANK ensures duplicate salaries share the same rank.

Step 3: Filter Top Three Unique Salaries

WHERE salary_rank <= 3

This keeps only employees whose salary belongs to the top three unique salary groups.

Complexity Analysis

Time Complexity

O(N log N)

The window function sorts salaries within each department.

Space Complexity

O(N)

Required for storing ranking information.

Alternative Solution (Without Window Functions)

For databases that do not support window functions:

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

This works but is less efficient because it performs a correlated subquery for each employee.

Time Complexity:

O(N²)

Interview Tips

When solving ranking problems, always ask:

Are duplicates important?
Do we need unique rankings?
Should tied values share the same rank?

Use:

ROW_NUMBER() → Unique ranking
RANK() → Shared rank with gaps
DENSE_RANK() → Shared rank without gaps

For this problem, DENSE_RANK() is the correct choice because the requirement is based on top three unique salaries.

Final Takeaway

This problem is a classic example of using SQL Window Functions effectively.

The key insight is understanding that the ranking should be based on distinct salary values, not individual employees.

Using DENSE_RANK():

Produces the correct result
Handles duplicate salaries naturally
Is efficient and scalable
Is the most commonly expected interview solution

If you're preparing for SQL interviews, make sure you're comfortable with ROW_NUMBER(), RANK(), and DENSE_RANK(), as they appear frequently in medium and hard database problems.

DotNet By Ajay

May 31, 2026

LeetCode 185: Department Top Three Salaries | SQL DENSE_RANK Solution Explained with Example

No comments:

Post a Comment