Unlocking LeetCode’s Hardest SQL Problem with Window Functions

LeetCode’s Hardest SQL Question?

Frequent LeetCode users will recognize Problem 185: Department Top Three Salaries , the only hard‑difficulty database problem on the platform, with over 900,000 submissions and a 58.3% acceptance rate.

Preparing the Tables and Sample Data

CREATE TABLE IF NOT EXISTS Employee (
  id INT,
  name VARCHAR(255),
  salary INT,
  departmentId INT
);
CREATE TABLE IF NOT EXISTS Department (
  id INT,
  name VARCHAR(255)
);
TRUNCATE TABLE Employee;
INSERT INTO Employee (id, name, salary, departmentId) VALUES
  (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);
TRUNCATE TABLE Department;
INSERT INTO Department (id, name) VALUES (1, 'IT'), (2, 'Sales');

The Employee table stores each employee’s ID, name, salary, and department ID, while the Department table stores department IDs and names.

Problem Statement

For each department, retrieve all employees whose salaries rank among the top three distinct salaries in that department. The result can be returned in any order.

Example Input and Output

Input: the Employee and Department tables shown above.

Output:

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

Official Answer Comparison

Solution 1: Subquery

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

This approach uses a correlated subquery to count how many distinct higher salaries exist for each employee within the same department; if fewer than three, the employee is kept.

Solution 2: Window Function

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

The DENSE_RANK() window function ranks salaries per department and directly filters the top three.

Performance Testing

We generated a larger test set using a stored procedure that creates 10 departments, each with 1,000 employees (10,000 rows total).

DELIMITER $$
CREATE PROCEDURE generate_test_data()
BEGIN
  DECLARE i INT DEFAULT 1;
  DECLARE j INT DEFAULT 1;
  DECLARE emp_id INT DEFAULT 1;
  WHILE i <= 10 DO
    INSERT INTO Department (id, name) VALUES (i, CONCAT('Dept_', i));
    SET j = 1;
    WHILE j <= 1000 DO
      INSERT INTO Employee (id, name, salary, departmentId)
      VALUES (emp_id, CONCAT('Employee_', emp_id), FLOOR(3000 + RAND() * 7000), i);
      SET emp_id = emp_id + 1;
      SET j = j + 1;
    END WHILE;
    SET i = i + 1;
  END WHILE;
END$$
DELIMITER ;
CALL generate_test_data();

Running the two queries on this dataset showed a dramatic difference: the window‑function version completed in sub‑millisecond time, while the subquery version took over five seconds.

Why Use Window Functions?

Avoid repeated scans and calculations: Traditional subqueries often require multiple passes over the data, causing performance bottlenecks; window functions compute results in a single scan.

Reduce intermediate results and temporary tables: Subqueries may generate large temporary tables, increasing memory and disk usage; window functions operate directly on the result set.

Eliminate unnecessary materialization: When the same PARTITION BY and ORDER BY are used, window functions share computation, avoiding duplicate work.

Conclusion and Recommendation

When using MySQL 8.0+ or any database that supports window functions, prefer the window‑function solution for this problem; it is both simpler and dramatically faster.