Department Highest Salary - Solution & Explanation

Problem Overview: The query must return the employee(s) who earn the highest salary in each department. The output includes the department name, employee name, and their salary. Multiple employees may appear for a department if they share the same maximum salary.

Approach 1: SQL Group By and Join (Time: O(n log n), Space: O(n))

This approach computes the maximum salary per department using GROUP BY. A subquery first scans the Employee table and calculates MAX(salary) for each departmentId. The result is then joined back with the original Employee table to retrieve the employee rows that match those maximum salaries. Finally, another join connects the result with the Department table to get department names. This pattern is common in SQL queries where aggregated results must be mapped back to detailed records.

Approach 2: Nested Queries with Join (Time: O(n log n), Space: O(n))

The nested query approach embeds the maximum salary calculation directly inside the filtering condition. For each employee, a correlated subquery checks whether their salary equals the maximum salary for that department. The database engine evaluates the inner query grouped by department and filters matching rows. While logically straightforward, correlated subqueries may be slightly less efficient depending on query planning. This method is still widely used in database interview questions because the logic closely mirrors the problem statement.

Approach 3: SQL Subquery Approach (Time: O(n log n), Space: O(n))

Another clean pattern uses a derived table containing departmentId and MAX(salary). The outer query joins this derived table with Employee and Department. The key insight is separating aggregation and filtering into two logical steps: first compute department-level metrics, then match employees who satisfy that metric. Query optimizers usually handle this efficiently using indexes and hash joins.

Approach 4: SQL Window Functions Approach (Time: O(n log n), Space: O(n))

Window functions compute rankings inside partitions. Using RANK() or DENSE_RANK() with PARTITION BY departmentId ORDER BY salary DESC assigns rank 1 to the highest-paid employees within each department. Filtering rows where rank equals 1 directly produces the answer. This approach avoids explicit aggregation joins and keeps the logic compact. Window functions are a powerful feature in modern SQL window functions workflows.

Recommended for interviews: The GROUP BY + JOIN approach is the safest answer because it demonstrates understanding of aggregation and relational joins. Window functions are often considered the cleanest modern solution and show stronger SQL fluency. Knowing both patterns signals strong database query skills.