Median Employee Salary solution and explanation
Google
6 more videos on this problem
LeetCode Hard 569 "Median Employee Salary" Google Interview SQL Question with ExplanationEveryday Data Science · 10:25 · 5K views
刷题 - LeetCode in MySQL 569 Median Employee Salary (类似题) - Michelle小梦想家Michelle小梦想家 · 24:22 · 2K views
Leetcode 569 - Median Employee Salary - Python Solution | FAANG InterviewsEveryday Data Science · 9:46 · 681 views
SQL Interview Question (Google Asked): Find Median Salary per Company –LeetCode 569 Explained SimplyConnect To Learn · 9:02 · 100 views
#26 SQL LeetCode 569 (Hard) : Median Employee Salary | SQL Interview Questionjava stories · 12:28 · 83 views
LeetCode SQL #569. Median Employee SalaryDE in Prod · 11:51 · 24 views
🚨 Google SQL Interview Question 😱 | LeetCode 569 Explained Big Tech Update | Dev Vijay 2.0DEV VIJAY 2.0 · 5:15 · 15 views
The problem
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?
Approach overview
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.
Solution
# Write your MySQL query statement below
WITH
t AS (
SELECT
*,
ROW_NUMBER() OVER (
PARTITION BY company
ORDER BY salary ASC
) AS rk,
COUNT(id) OVER (PARTITION BY company) AS n
FROM Employee
)
SELECT
id,
company,
salary
FROM t
WHERE rk >= n / 2 AND rk <= n / 2 + 1;Complexity analysis
| 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 |
Frequently asked questions
Is Median Employee Salary easy or hard?
Median Employee Salary is classified as a Hard problem because it requires advanced SQL concepts such as window functions, partitioning, and positional filtering. Understanding how to convert median logic into ranking expressions is the main challenge.
Median Employee Salary Python/Java solution
This problem is designed for SQL rather than general-purpose languages. In Python or Java, you would group employees by company, sort each salary list, and select the middle element(s). That approach typically runs in O(n log n) time due to sorting.
How to solve Median Employee Salary in O(n)?
Pure O(n) solutions are uncommon in SQL because determining a median generally requires sorting. In relational databases, the practical method uses window functions with ORDER BY inside a partition, resulting in O(n log n) complexity. The query ranks salaries and selects the middle index positions.
What is the best approach for Median Employee Salary?
The best approach uses SQL window functions. Rank salaries within each company using ROW_NUMBER() and compute the company size with COUNT() OVER (PARTITION BY Company). The median rows are the positions between (count + 1) / 2 and (count + 2) / 2. This approach runs in O(n log n) time due to sorting within each company.
Is Median Employee Salary asked at Google/Amazon/Meta?
Median and ranking problems frequently appear in SQL interviews at large tech companies. Variants involving median calculations, salary rankings, and window functions have been reported in interviews at companies like Amazon and Google where SQL analytical queries are evaluated.
What data structure is used in Median Employee Salary?
The problem primarily relies on relational database operations rather than traditional data structures. SQL window functions create ordered partitions of rows, effectively treating each company’s salary list like a sorted array. Ranking functions then identify the middle element positions.
What is the time complexity of Median Employee Salary?
The optimized SQL solution runs in O(n log n) time because the database must sort salaries within each company partition. Window functions such as ROW_NUMBER() and COUNT() then operate over that ordered data. Space complexity is typically O(n) depending on the query execution plan.