Highest Paid in Every Department
Problem
A table employee(id, name, dept, salary) holds one row per person. Write a query that returns, for every department, the people who earn that department's highest salary, as columns dept, name and salary. When several people share the top salary of a department, return all of them. Sort by dept, then name.
Examples
Input: employee = [(1, "Ana", "eng", 120), (2, "Ben", "eng", 150), (3, "Cy", "ops", 90), (4, "Dee", "ops", 80)]
Output: [("eng", "Ben", 150), ("ops", "Cy", 90)]Input: employee = [(1, "Ana", "eng", 150), (2, "Ben", "eng", 150), (3, "Cy", "eng", 100)]
Output: [("eng", "Ana", 150), ("eng", "Ben", 150)]
Why: Ana and Ben tie for the top of eng, so both come backInput: employee = [(1, "Gus", "hr", 70)]
Output: [("hr", "Gus", 70)]
Why: edge case, the only person in a department is its top earnerHints
0 / 3
Grouping by dept gives you each department's highest salary, but it throws away who earns it. You need the maximum and the person's row at the same time.
For one row, the question is: is this salary equal to the largest salary in this row's own department? A subquery can compute that maximum using the outer row's dept.
Write WHERE e.salary = (SELECT MAX(salary) FROM employee WHERE dept = e.dept). Comparing with = keeps every tied row, which LIMIT 1 or ORDER BY tricks would not.
Solution
A correlated subquery is re-evaluated for each outer row with that row's values in scope, so (SELECT MAX(salary) FROM employee WHERE dept = e.dept) is "the top salary of this person's department". Keeping the rows whose salary equals it returns every top earner, ties included, because equality does not pick a winner the way LIMIT 1 does. An equivalent form groups once in a derived table, SELECT dept, MAX(salary) per department, and joins it back on both columns; the planner often turns the correlated form into exactly that. RANK() OVER (PARTITION BY dept ORDER BY salary DESC) = 1 is a third answer. Done naively the subquery rescans the table per row, O(n²); with an index on (dept, salary) each lookup is O(log n).
import sqlite3
QUERY = """
SELECT e.dept, e.name, e.salary
FROM employee AS e
WHERE e.salary = (
SELECT MAX(salary)
FROM employee
WHERE dept = e.dept
)
ORDER BY e.dept, e.name
"""
def run(employees):
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE employee (id INTEGER PRIMARY KEY, name TEXT, dept TEXT, salary INTEGER)")
db.executemany("INSERT INTO employee VALUES (?, ?, ?, ?)", employees)
return db.execute(QUERY).fetchall()
print(run([(1, "Ana", "eng", 120), (2, "Ben", "eng", 150), (3, "Cy", "ops", 90), (4, "Dee", "ops", 80)])) # -> [('eng', 'Ben', 150), ('ops', 'Cy', 90)]
print(run([(1, "Ana", "eng", 150), (2, "Ben", "eng", 150), (3, "Cy", "eng", 100)])) # -> [('eng', 'Ana', 150), ('eng', 'Ben', 150)]
print(run([(1, "Gus", "hr", 70)])) # -> [('hr', 'Gus', 70)]Stuck on the idea rather than the code? Subqueries covers it.