Skip to main content
Talentd

Median Employee Salary - Solution & Explanation

HardPremiumFree on FleetCodeDatabase5 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self Join Median DetectionO(n²)O(1)Conceptual understanding of median definition in SQL queries
Window Functions with Row RankingO(n log n)O(n)Best practical SQL solution using ranking and partitioning

Video Solution

LeetCode Hard 569 "Median Employee Salary" Google Interview SQL Question with Explanation • Everyday Data Science • 5,936 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Median Employee Salary with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Median Given Frequency of Numbers