Department Highest Salary - Leetcode Solution

The Department Highest Salary problem on LeetCode asks you to find the highest salary for each department given a table of employee salaries. Here's a step-by-step solution to the problem:

Step 1: Understand the problem

The problem statement gives you a table of employee salaries and asks you to find the maximum salary for each department. You need to return a table that has the department name and the highest salary for that department.

Step 2: Analyze the problem

To solve this problem, you'll need to use the SQL MAX function to find the highest salary for each department. You'll also need to use the GROUP BY clause to group the salaries by department.

Step 3: Design the solution

Here's the SQL query that solves the problem:

SELECT d.Name AS Department, MAX(e.Salary) AS Salary 
FROM Employee e, Department d 
WHERE e.DepartmentId = d.Id 
GROUP BY e.DepartmentId

This SQL query will select the department name and the maximum salary for that department by joining the Employee and Department tables on the DepartmentId column and grouping the results by department.

Step 4: Test the solution

To test the solution, you can use the following example tables:

Employee Table:
+----+-------+-------------+--------+
| Id | Name  | DepartmentId| Salary |
+----+-------+-------------+--------+
| 1  | Joe   | 1           | 70000  |
| 2  | Jim   | 1           | 90000  |
| 3  | Jane  | 2           | 68000  |
| 4  | Janet | 2           | 80000  |
+----+-------+-------------+--------+

Department Table:
+----+---------+
| Id | Name    |
+----+---------+
| 1  | Sales   |
| 2  | Finance |
+----+---------+

If you run the SQL query on these tables, you should get the following output:

+------------+--------+
| Department | Salary |
+------------+--------+
| Sales      | 90000  |
| Finance    | 80000  |
+------------+--------+

This output shows that the highest salary in the Sales department is $90,000 and the highest salary in the Finance department is $80,000, which is the correct answer to the problem.

Step 5: Optimize the solution

The solution provided above has a time complexity of O(nlogn) where n is the number of employees. We can optimize our queries by avoiding the join altogether and making use of subqueries. Here's the optimized solution -

SELECT d.Name AS Department, e.Salary AS Salary
FROM Employee e
INNER JOIN (
    SELECT DepartmentId, MAX(Salary) AS MaxSalary 
    FROM Employee 
    GROUP BY DepartmentId
) AS topSalaries
ON e.DepartmentId = topSalaries.DepartmentId AND e.Salary = topSalaries.MaxSalary
JOIN Department d ON e.DepartmentId = d.Id

This query uses a subquery to first get the maximum salary for each department and then joins that result with the Employee table on the DepartmentId and Salary columns to get the department name and employee salary. This query has a time complexity of O(n) which is better than the previous query.

With this optimized solution, we've arrived at our final, optimized solution for the Department Highest Salary problem on LeetCode.

1