Find the top 3 highest salaries in each department.

You can solve this with a window function that ranks salaries per department and then filters the top 3. For example:

SELECT employee_id,
       department_id,
       salary,
       rank
FROM (
  SELECT e.employee_id,
         e.department_id,
         e.salary,
         ROW_NUMBER() OVER (PARTITION BY e.department_id ORDER BY e.salary DESC) AS rank
  FROM employees e
) t
WHERE t.rank <= 3;

This query assigns a row number to each employee within their department, ordered by salary descending. The outer query then keeps only rows where the rank is 1, 2, or 3. If you want to include ties (e.g., multiple employees with the same salary), replace ROW_NUMBER() with DENSE_RANK(). The time complexity is O(n log n) due to the sort performed by the window function, and the space complexity is O(n) for the intermediate result. This approach works on most SQL engines that support window functions (PostgreSQL, SQL Server, Oracle, MySQL 8+, etc.).