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.

Description Hints 3 Solution Video 10:25

569. Median Employee Salary

Hard65.9% acceptance2 companiesPremium elsewhere, free here

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?