Table: Employee
+--------------+---------+ | Column Name | Type | +--------------+---------+ | id | int | | company | varchar | | salary | int | +--------------+---------+ id is the primary key (column with unique values) for this table. Each row of this table indicates the company and the salary of one employee.
Write a solution to find the rows that contain the median salary of each company. While calculating the median, when you sort the salaries of the company, break the ties by id.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Employee table: +----+---------+--------+ | id | company | salary | +----+---------+--------+ | 1 | A | 2341 | | 2 | A | 341 | | 3 | A | 15 | | 4 | A | 15314 | | 5 | A | 451 | | 6 | A | 513 | | 7 | B | 15 | | 8 | B | 13 | | 9 | B | 1154 | | 10 | B | 1345 | | 11 | B | 1221 | | 12 | B | 234 | | 13 | C | 2345 | | 14 | C | 2645 | | 15 | C | 2645 | | 16 | C | 2652 | | 17 | C | 65 | +----+---------+--------+ Output: +----+---------+--------+ | id | company | salary | +----+---------+--------+ | 5 | A | 451 | | 6 | A | 513 | | 12 | B | 234 | | 9 | B | 1154 | | 14 | C | 2645 | +----+---------+--------+ Explanation: For company A, the rows sorted are as follows: +----+---------+--------+ | id | company | salary | +----+---------+--------+ | 3 | A | 15 | | 2 | A | 341 | | 5 | A | 451 | <-- median | 6 | A | 513 | <-- median | 1 | A | 2341 | | 4 | A | 15314 | +----+---------+--------+ For company B, the rows sorted are as follows: +----+---------+--------+ | id | company | salary | +----+---------+--------+ | 8 | B | 13 | | 7 | B | 15 | | 12 | B | 234 | <-- median | 11 | B | 1221 | <-- median | 9 | B | 1154 | | 10 | B | 1345 | +----+---------+--------+ For company C, the rows sorted are as follows: +----+---------+--------+ | id | company | salary | +----+---------+--------+ | 17 | C | 65 | | 13 | C | 2345 | | 14 | C | 2645 | <-- median | 15 | C | 2645 | | 16 | C | 2652 | +----+---------+--------+
Follow up: Could you solve it without using any built-in or window functions?
Problem Overview: The table contains employee Id, Company, and Salary. For each company, return the employee record(s) whose salary represents the median. If the company has an odd number of employees, return the single middle salary. If even, return the two middle salaries.
Approach 1: Self Join Median Detection (O(n²) time, O(1) space)
A brute force SQL strategy compares each employee's salary with every other employee in the same company using self joins. For a salary to qualify as the median, the number of salaries smaller and larger than it must not exceed half of the company size. This can be implemented with grouped comparisons and COUNT() conditions. While it demonstrates the median definition clearly, it performs poorly because each row may compare against many others. This approach is rarely used in production but helps build intuition for median logic in database queries.
Approach 2: Window Functions with Row Ranking (O(n log n) time, O(n) space)
The practical SQL solution ranks salaries within each company using window functions. First, sort salaries per company and assign ROW_NUMBER(). At the same time compute the total employee count with COUNT(*) OVER (PARTITION BY Company). The median rows are the positions between (count + 1) / 2 and (count + 2) / 2. For odd counts both expressions resolve to the same row; for even counts they capture the two middle rows. This works because ordered ranking directly exposes the middle index in the sorted salary list. The database engine handles the sorting and partitioning efficiently, making it the standard solution using SQL and window functions.
Recommended for interviews: The window function approach is what interviewers typically expect for SQL-heavy problems. It shows you understand ranking functions, partitioning, and how to compute positional statistics like medians directly inside SQL. Mentioning the brute force comparison method shows conceptual understanding, but the window function solution demonstrates practical SQL skills and scales far better on large tables.
MySQL
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self Join Median Detection | O(n²) | O(1) | Conceptual understanding of median definition in SQL queries |
| Window Functions with Row Ranking | O(n log n) | O(n) | Best practical SQL solution using ranking and partitioning |
LeetCode Hard 569 "Median Employee Salary" Google Interview SQL Question with Explanation • Everyday Data Science • 5,533 views views
Watch 6 more video solutions →Practice Median Employee Salary with our built-in code editor and test cases.
Practice on FleetCode