LeetCode 184 - Department Highest Salary

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem asks us to find employees with the highest salary in each department from a company database. The input consists of two relational tables: Employee and Department. The Employee table contains employee details, including id, name, salary, and departmentId. The departmentId is a foreign key linking the employee to the Department table. The Department table contains id and name, representing the unique identifier and the name of each department.

The expected output is a table containing three columns: Department, Employee, and Salary. Each row represents an employee who has the highest salary in their department. If multiple employees share the highest salary in a department, each should appear in the output.

Constraints to consider include that department names are guaranteed to be non-null and the id fields in both tables are unique. This implies we do not need to handle missing department names or duplicate IDs. Edge cases include departments with only one employee, multiple employees tied for the highest salary, and departments with no employees at all (though in this problem, the latter is unlikely as only existing employees are considered).

Approaches

The brute-force approach involves iterating through each department, scanning all employees in that department to find the maximum salary, and then collecting all employees with that maximum salary. This method works correctly but requires nested loops over departments and employees, which can be slow for large datasets.

The optimal approach leverages SQL aggregation and joining capabilities. We can first compute the maximum salary for each department using GROUP BY. Then, we join this result back with the Employee table to select only the employees whose salary matches the department maximum. Finally, we join with the Department table to get department names. This approach reduces redundant comparisons and efficiently utilizes database indexing.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(D * E)	O(E)	Iterate over each department and scan all employees to find the maximum salary
Optimal	O(E)	O(D)	Use aggregation and joins to compute max salaries per department and filter employees

Algorithm Walkthrough

Compute the maximum salary for each department. This is done by grouping the Employee table by departmentId and applying the MAX function on the salary column. The result is a mapping of departmentId to max_salary.
Join the Employee table with this maximum salary table on departmentId and salary. This filters the employees, keeping only those whose salary equals the maximum salary in their department.
Join the filtered result with the Department table on departmentId = id to obtain the department names.
Select the columns Department (department name), Employee (employee name), and Salary from the final joined result.
Return the resulting table. The ordering is not specified, so any order is acceptable.

Why it works: The invariant here is that for each department, only employees whose salary equals the computed maximum salary are kept. Because SQL joins preserve row equality, all employees tied for the maximum salary are included. The final join adds department names, satisfying the output format.

Python Solution

# Python solution using SQLAlchemy as a reference for LeetCode SQL execution
# LeetCode allows direct SQL execution, so the core logic is a SQL query
class Solution:
    def highestSalary(self) -> str:
        query = """
        SELECT d.name AS Department, e.name AS Employee, e.salary AS Salary
        FROM Employee e
        JOIN Department d ON e.departmentId = d.id
        JOIN (
            SELECT departmentId, MAX(salary) AS max_salary
            FROM Employee
            GROUP BY departmentId
        ) m ON e.departmentId = m.departmentId AND e.salary = m.max_salary
        """
        return query

Explanation: The subquery computes the maximum salary per department. Joining it with the Employee table filters out only the employees with the maximum salary. Joining with the Department table adds the department name. Column aliases Department, Employee, and Salary satisfy the required output format.

Go Solution

// Go does not execute SQL directly; LeetCode uses SQL queries. This Go solution is a reference
// for constructing the SQL query string in a Go context.
package main

func highestSalary() string {
    query := `
    SELECT d.name AS Department, e.name AS Employee, e.salary AS Salary
    FROM Employee e
    JOIN Department d ON e.departmentId = d.id
    JOIN (
        SELECT departmentId, MAX(salary) AS max_salary
        FROM Employee
        GROUP BY departmentId
    ) m ON e.departmentId = m.departmentId AND e.salary = m.max_salary
    `
    return query
}

Go-specific notes: The Go solution constructs the SQL query string. Unlike Python, we do not execute SQL directly but return the query for LeetCode's database engine. String formatting and multiline string syntax are used for readability.

Worked Examples

Example Input:

Employee:
+----+-------+--------+--------------+
| id | name  | salary | departmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Jim   | 90000  | 1            |
| 3  | Henry | 80000  | 2            |
| 4  | Sam   | 60000  | 2            |
| 5  | Max   | 90000  | 1            |
Department:
+----+-------+
| id | name  |
+----+-------+
| 1  | IT    |
| 2  | Sales |

Algorithm Execution:

Compute max salaries per department:

IT: max(70000, 90000, 90000) = 90000
Sales: max(80000, 60000) = 80000

Filter employees matching max salary:

IT: Jim (90000), Max (90000)
Sales: Henry (80000)

Join with department names:

Jim -> IT
Max -> IT
Henry -> Sales

Output:

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Jim      | 90000  |
| IT         | Max      | 90000  |
| Sales      | Henry    | 80000  |

Complexity Analysis

Measure	Complexity	Explanation
Time	O(E)	Each employee is processed once in aggregation and join operations.
Space	O(D)	Storing the maximum salary per department requires space proportional to the number of departments.

The SQL engine efficiently computes aggregations and joins using indexes, so this solution scales well with larger datasets.

Test Cases

# Example cases
assert Solution().highestSalary() == """
SELECT d.name AS Department, e.name AS Employee, e.salary AS Salary
FROM Employee e
JOIN Department d ON e.departmentId = d.id
JOIN (
    SELECT departmentId, MAX(salary) AS max_salary
    FROM Employee
    GROUP BY departmentId
) m ON e.departmentId = m.departmentId AND e.salary = m.max_salary
"""  # returns correct SQL query string

Test	Why
Employees with tie salaries in a department	Ensures all top employees are included
Department with a single employee	Ensures algorithm handles minimal department size
Multiple departments	Ensures algorithm correctly separates max salaries per department

Edge Cases

Single Employee in a Department: If a department has only one employee, that employee is automatically the highest-paid. The aggregation ensures this employee is selected without special handling.

Multiple Employees Tied for Max Salary: If multiple employees share the maximum salary in the same department, all must be included. The join on salary = max_salary guarantees all such employees appear in the result.

Departments with No Employees: While not explicitly present in the problem, departments without employees would not appear in the result. The inner join with Employee naturally excludes empty departments, avoiding NULLs or empty rows.