Practice/Amazon/Leetcode 571. Find Median Given Frequency of Numbers

Leetcode 571. Find Median Given Frequency of Numbers

CodingMust

Problem

You are given two arrays of equal length: values and frequencies. The values array contains distinct integers, and the frequencies array indicates how many times each corresponding value appears in an implicit dataset.

Your task is to calculate the median of this dataset without actually expanding it into a full array. The frequencies can be very large (up to 10^9), making expansion impractical.

The median is defined as:

• If the total count of numbers is odd, the median is the middle element
• If the total count is even, the median is the average of the two middle elements

Return the median as a floating-point number.

Requirements

1. Calculate the median without expanding the dataset into memory
2. Handle both odd and even total counts correctly
3. Return the result as a float
4. The solution must work efficiently even when frequencies are very large

Constraints

• 1 ≤ values.length ≤ 1000
• values.length == frequencies.length
• 1 ≤ frequencies[i] ≤ 10^9
• -10^6 ≤ values[i] ≤ 10^6
• All values are distinct
• Time complexity should be O(n log n) or better where n is the length of the arrays
• Space complexity should be O(n) or better

Examples

Example 1:

Input: values = [1, 2, 3], frequencies = [1, 2, 1] Output: 2.0 Explanation: The implicit dataset is [1, 2, 2, 3] with 4 total elements. The median is the average of the 2nd and 3rd elements: (2 + 2) / 2 = 2.0

Example 2:

Input: values = [10, 20, 30], frequencies = [5, 3, 2] Output: 10.0 Explanation: Total count is 10. The implicit dataset has 5 tens, 3 twenties, and 2 thirties. The median positions are 5th and 6th elements, both are 10.

Example 3:

Input: values = [1, 100], frequencies = [1, 1] Output: 50.5 Explanation: Dataset is [1, 100]. Median is (1 + 100) / 2 = 50.5