Formatted question description: https://leetcode.ca/all/571.html

571. Find Median Given Frequency of Numbers

Level

Hard

Description

The Numbers table keeps the value of number and its frequency.

+----------+-------------+
|  Number  |  Frequency  |
+----------+-------------|
|  0       |  7          |
|  1       |  1          |
|  2       |  3          |
|  3       |  1          |
+----------+-------------+

In this table, the numbers are 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3, so the median is (0 + 0) / 2 = 0.

+--------+
| median |
+--------|
| 0.0000 |
+--------+

Write a query to find the median of all numbers and name the result as median.

Solution

Suppose n1.Number is the median in table Numbers. Then the count of numbers less than or equal to n1.Number should be at least half of the total counts, and the count of numbers less than n1.Number should be at most half of the total counts.

# Write your MySQL query statement below
select avg(Number) as median from (
    select n1.Number from Numbers n1 join Numbers n2 on n1.Number >= n2.Number
        group by n1.Number
        having
        sum(n2.Frequency) >= (select sum(Frequency) from Numbers) / 2
        and
        sum(n2.Frequency) - avg(n1.Frequency) <= (select sum(Frequency) from Numbers) / 2
) med;

All Problems

All Solutions