569 Median Employee Salary

Description

Table: Employee

• 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.

Problem Statement

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:

Output:

Explanation: The Median column is added only for understanding. For company A, the rows sorted are as follows:

For company B, the rows sorted are as follows:

For company C, the rows sorted are as follows:

Follow up: Could you solve it without using any built-in or window functions?

Solution

Here, we need those rows which contain the median salary for each company. If the number of records is odd, then the median is the middle record which is single record when ordered by the salary. However, when there are even number of records, the median is calculated using the two middle records when ordered by salary field. Hence, it will have two records for these companies.

Approach 1: Using Window Functions

In order to find the middle rows, you need to assign row number to each row per company. This can be done using the ROW_NUMBER() window function. You can partition the records by company column and use the ORDER BY clause to order the rows using salary column.

The problem can be divided in following parts.

1. Find row number for each employee of the table per company ordered by salary.

Below query returns the row number for each employee of a company.

1WITH cte AS (
2    SELECT id, company, salary,
3        ROW_NUMBER() OVER (PARTITION BY company ORDER BY salary) 'row_num'
4        FROM Employee
5) SELECT * FROM cte ORDER BY row_num;

2. Find the middle row number(s) for each company.

In order to find the middle row number, you need to find what are the total number of employees per company. Once you have the count of employees, you need rows which have count / 2 rounded down to nearest integer for odd number of employees. If you’ve even number of employees, you need to find rows which have count / 2 rounded down to nearest integer and count / 2 + 1 rounded down to nearest integer. In SQL, division does not round down the number. So, you can basically use row_num >= cnt / 2 AND row_num <= cnt / 2 + 1 condition.

1WITH cte AS (
2    SELECT id, company, salary,
3        ROW_NUMBER() OVER (PARTITION BY company ORDER BY salary) 'row_num',
4        COUNT(1) OVER (PARTITION BY company) cnt
5        FROM Employee
6) SELECT id, company, salary FROM cte 
7    WHERE row_num >= cnt / 2 AND row_num <= (cnt / 2) + 1
8    ORDER BY company, row_num;