LeetCode 185 - Department Top Three Salaries

This is a SQL database problem where we need to identify the employees who belong to the top three unique salaries within each department.

leetcodeharddatabase

LeetCode Problem 185

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

This is a SQL database problem where we need to identify the employees who belong to the top three unique salaries within each department.

The input consists of two tables:

The Employee table stores information about each employee, including:

  • id, a unique identifier for the employee
  • name, the employee's name
  • salary, the employee's salary
  • departmentId, which links the employee to a department

The Department table stores department information:

  • id, a unique department identifier
  • name, the department name

The goal is to return a result table with three columns:

Column Meaning
Department Department name
Employee Employee name
Salary Employee salary

The key requirement is understanding what top three salaries means. It refers to the top three unique salary values, not the top three employees.

For example, suppose a department has salaries:

[90000, 85000, 85000, 70000, 69000]

The top three unique salaries are:

90000, 85000, 70000

This means every employee earning one of those salaries should be included. Both employees with salary 85000 qualify.

The problem guarantees that there are no employees with the exact same combination of name, salary, and department, which simplifies handling duplicates.

Several edge cases are important:

  • A department may contain fewer than three distinct salaries. In that case, we include all employees whose salaries are among the available unique salaries.
  • Multiple employees can share the same salary. Since ranking is based on unique salary values, all tied employees should be included.
  • Departments may have only one employee, meaning only one salary exists and that employee must still be returned.
  • A naive solution may incorrectly count employees instead of distinct salary values, producing wrong results when ties occur.

Approaches

Brute Force Approach

A brute-force strategy would examine each employee and determine whether their salary belongs to the department's top three unique salaries.

For every employee, we could:

  1. Find all salaries in the same department.
  2. Extract distinct salary values.
  3. Sort them in descending order.
  4. Take the top three salaries.
  5. Check whether the current employee's salary is inside that set.

This approach works because it directly computes the answer definition for every employee. However, it repeatedly recomputes department salary rankings for many employees in the same department.

If a department contains many employees, repeatedly sorting salaries becomes inefficient. We end up doing redundant work for every row.

Optimal Approach

The key observation is that we should compute rankings once per department salary, not once per employee.

SQL window functions are ideal here. Specifically, DENSE_RANK() solves the problem naturally.

We partition employees by department and rank salaries in descending order.

The important detail is using DENSE_RANK() instead of RANK():

  • DENSE_RANK() gives consecutive rankings to unique salary values.
  • Employees with the same salary receive the same rank.
  • No gaps are introduced.

Example:

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

We then filter employees whose rank is less than or equal to 3.

This directly models the requirement of top three unique salaries.

Approach Time Complexity Space Complexity Notes
Brute Force O(N² log N) O(N) Recomputes sorted salary rankings for many employees
Optimal O(N log N) O(N) Uses SQL window functions to rank salaries efficiently

Algorithm Walkthrough

Optimal Algorithm Using DENSE_RANK()

  1. Join the Employee and Department tables so that each employee record contains the department name. This is necessary because the output requires the department name rather than only the department ID.
  2. Partition employees by department using PARTITION BY departmentId. This ensures salary rankings are computed independently for each department.
  3. Sort salaries in descending order inside each department. Higher salaries should receive better rankings, so we order by salary DESC.
  4. Use DENSE_RANK() to assign rankings to salary values. Employees with identical salaries receive the same rank because the ranking is based on unique salary values.
  5. Filter employees whose rank is <= 3. These employees belong to the top three unique salaries in their department.
  6. Return the department name, employee name, and salary.

Why it works

The correctness comes from the behavior of DENSE_RANK().

Within each department, DENSE_RANK() assigns the same rank to equal salary values and increments ranks only when a new distinct salary appears. Therefore, ranks 1, 2, and 3 correspond exactly to the top three unique salaries. Filtering to these ranks guarantees that every qualifying employee is included and no employee outside the top three unique salary values is returned.

Python Solution

LeetCode Database problems use SQL rather than Python methods. Below is the exact SQL solution that is LeetCode-submittable.

# This problem requires SQL, not Python.
#
# MySQL Solution:

SELECT
    d.name AS Department,
    ranked.name AS Employee,
    ranked.salary AS Salary
FROM (
    SELECT
        name,
        salary,
        departmentId,
        DENSE_RANK() OVER (
            PARTITION BY departmentId
            ORDER BY salary DESC
        ) AS salary_rank
    FROM Employee
) AS ranked
JOIN Department d
    ON ranked.departmentId = d.id
WHERE ranked.salary_rank <= 3;

The solution begins by creating a derived table named ranked. Inside this subquery, we compute a dense rank for every employee salary within their department.

The PARTITION BY departmentId clause ensures that salary rankings restart independently for each department. Without partitioning, salaries from different departments would incorrectly compete against each other.

The ORDER BY salary DESC clause ranks higher salaries first.

The most important piece is DENSE_RANK(). Employees with the same salary receive the same rank, which satisfies the requirement for top three unique salaries.

After ranking, we join with the Department table to retrieve department names. Finally, we filter rows where salary_rank <= 3, ensuring only high earners are returned.

Go Solution

Since this is a database problem, LeetCode expects a SQL query rather than a Go implementation. Below is the exact Go-compatible SQL string if needed in an application context.

query := `
SELECT
    d.name AS Department,
    ranked.name AS Employee,
    ranked.salary AS Salary
FROM (
    SELECT
        name,
        salary,
        departmentId,
        DENSE_RANK() OVER (
            PARTITION BY departmentId
            ORDER BY salary DESC
        ) AS salary_rank
    FROM Employee
) AS ranked
JOIN Department d
    ON ranked.departmentId = d.id
WHERE ranked.salary_rank <= 3;
`

The core logic is identical to the SQL solution. The only difference is that the query is stored as a Go multiline string. Since the problem itself executes SQL directly on LeetCode, no Go-specific concerns such as integer overflow, slices, or nil handling apply.

Worked Examples

Example 1

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

Step 1: Rank salaries per department

Department: IT

Sort salaries descending:

Employee Salary
Max 90000
Joe 85000
Randy 85000
Will 70000
Janet 69000

Apply DENSE_RANK():

Employee Salary Rank
Max 90000 1
Joe 85000 2
Randy 85000 2
Will 70000 3
Janet 69000 4

Keep ranks <= 3:

Employee Salary
Max 90000
Joe 85000
Randy 85000
Will 70000

Department: Sales

Sort salaries descending:

Employee Salary
Henry 80000
Sam 60000

Apply DENSE_RANK():

Employee Salary Rank
Henry 80000 1
Sam 60000 2

Keep ranks <= 3:

Employee Salary
Henry 80000
Sam 60000

Final Result

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

Complexity Analysis

Measure Complexity Explanation
Time O(N log N) Window function sorting dominates runtime
Space O(N) Ranking operation stores intermediate rows

The dominant cost comes from sorting salaries within each department for ranking. Across all employees, this behaves similarly to sorting operations, giving approximately O(N log N) time complexity. The query engine also needs temporary storage for ranking and partitioning, resulting in O(N) auxiliary space.

Test Cases

Since this is a SQL problem, below are representative logical test scenarios expressed in Python-style assertions.

# Example case from the prompt
assert get_high_earners([
    ("Joe", 85000, 1),
    ("Henry", 80000, 2),
    ("Sam", 60000, 2),
    ("Max", 90000, 1),
    ("Janet", 69000, 1),
    ("Randy", 85000, 1),
    ("Will", 70000, 1),
]) == {
    ("IT", "Max", 90000),
    ("IT", "Joe", 85000),
    ("IT", "Randy", 85000),
    ("IT", "Will", 70000),
    ("Sales", "Henry", 80000),
    ("Sales", "Sam", 60000),
}  # provided example

# Department with fewer than three salaries
assert get_high_earners([
    ("Alice", 100000, 1),
    ("Bob", 80000, 1),
]) == {
    ("Dept", "Alice", 100000),
    ("Dept", "Bob", 80000),
}  # only two salaries exist

# Multiple employees tied on same salary
assert get_high_earners([
    ("A", 100, 1),
    ("B", 90, 1),
    ("C", 90, 1),
    ("D", 80, 1),
    ("E", 70, 1),
]) == {
    ("Dept", "A", 100),
    ("Dept", "B", 90),
    ("Dept", "C", 90),
    ("Dept", "D", 80),
}  # ties included

# Single employee department
assert get_high_earners([
    ("Solo", 50000, 1),
]) == {
    ("Dept", "Solo", 50000),
}  # one employee only

# More than three unique salaries
assert get_high_earners([
    ("A", 100, 1),
    ("B", 90, 1),
    ("C", 80, 1),
    ("D", 70, 1),
    ("E", 60, 1),
]) == {
    ("Dept", "A", 100),
    ("Dept", "B", 90),
    ("Dept", "C", 80),
}  # fourth salary excluded
Test Why
Provided example Validates standard behavior
Fewer than three salaries Ensures departments with limited salaries work
Duplicate salaries Verifies ties are included correctly
Single employee Confirms minimal input works
More than three salaries Ensures filtering logic is correct

Edge Cases

Multiple employees sharing the same salary

A common bug is treating ranking as employee-based rather than salary-based. For example, if two employees both earn 85000, a naive top-three employee solution might exclude one of them. Using DENSE_RANK() ensures identical salaries receive the same rank, so all tied employees are included.

Departments with fewer than three unique salaries

Some departments may only have one or two distinct salaries. A fragile implementation might expect exactly three ranks and accidentally exclude valid employees. The query naturally handles this because DENSE_RANK() only creates existing salary levels, and filtering <= 3 includes everything available.

More than three employees but fewer than three salary levels

Consider salaries [100, 100, 90, 90, 80]. Although there are many employees, there are only three unique salaries. A naive implementation that limits to three employees would fail. This solution ranks salary values, not employee counts, so every qualifying employee is returned correctly.