Department Top Three Salaries

hard database ranking window function

Problem

Write a SQL query to find employees who are among the top three earners in each department (dense rank ≤ 3).

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

InputIT: Joe=85k, Henry=85k, Sam=60k, Max=90k; Sales: Janet=69k, Randy=85k

OutputIT: Max, Joe, Henry, Sam; Sales: Randy, Janet

Employee (name|dept|salary; …)

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

Explanation

We want the top three distinct salary levels in each department, along with everyone earning them. The tool for "rank within groups" is the window function DENSE_RANK.

The phrase PARTITION BY departmentId restarts the ranking separately for each department, and ORDER BY salary DESC ranks the highest salary as 1. We use DENSE_RANK (not RANK) so that ties share a rank and the next salary gets the very next number, with no gaps — that is what makes "top three salary levels" work even when several people earn the same amount.

The subquery attaches this rank r to every employee. The outer query then simply keeps rows where r <= 3 and joins to Department for the readable name.

Example: IT salaries 90k, 85k, 85k, 60k get dense ranks 1, 2, 2, 3 — all are ≤ 3, so all four IT employees qualify (two tie at rank 2). Sales with 85k and 69k gives ranks 1 and 2, so both stay.

The ranking is done with a sort inside each partition, so the cost is roughly n log n.

Time: O(n log n) Space: O(n)