Last Updated: 5 Mar, 2021

Find the median of all subarrays of a particular size.

Moderate

Asked in companies

Solve now

Problem statement

You have been given an array/list ‘ARR’ of integers consisting of ‘N’ integers. You are also given a size ‘M’. You need to display the median of all the subarrays of size ‘M’ and it is starting from the very left of the array.

Median is the middle value in an ordered integer array/list. If the size of the array/list is even there is no middle element. So the median is the mean of two middle values in an even size array/list.

Your task is to return the median of all the subarrays whose size is ‘M’.

Example:

Let’s say you have an array/list [1,4,3,5] and ‘M’ is 3.Then the first subarray of size 3 is [1,4,3] whose median is 3.Then the second subarray of size 3 is [4,3,5] whose median is 4. Therefore the median of all the subarrays of size 3 is [3.0,4.0].

Input Format:

The first line contains a single integer ‘T' representing the number of test cases.

The first line of each test case contains two single space-separated integers ‘N’ and ‘M’ representing the size of the array/list ‘ARR’ and size of subarray for which you need to calculate median respectively.

The second line and the last line of input contain ‘N’ single space-separated integers representing the array/list elements.

Output Format:

For each test case, return the median of all the subarrays whose size is ‘M’.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 1000
1 <= M <= N
1 <= ‘ARR[i]’ <= 10^6

Time Limit: 1sec

Solve now

Approaches

01 Approach

We can solve each subarray individually.

For a particular subarray of size ‘M’:-

Sort this subarray as we need to order the integers to find the subarray.
Median is calculated as follows:-
- If ‘M’ is odd, the median is the m/2th element of the sorted subarray (0-based indexing is assumed).
Else the median is the mean of ‘(M/2-1)th’ and ‘M/2th’ element of the sorted subarray (0-based indexing is assumed).
Push the median into the ‘ANS’ vector/list.

Solve now

02 Approach

We use multiset(self-balance binary tree) because it keeps elements in sorted order and can have multiple occurrences of a number. Declare a multiset 'WINDOWS'.

Following is the algorithm for this approach:

Insert first 'M' elements in multiset 'WINDOWS'.
'MEDIAN' for the first subarray is calculated by defining the iterator 'MID' as 'M/2'th element of multiset (assuming the first element as ‘0th’ element of multiset). We calculate median as the mean of value at this iterator and 'M/2-1 + M%2'th position. In case 'M' is odd both iterators point to the same element. In case 'M' is even first iterator points to 'M/2'th element and the second iterator points to ‘M/2-1’th element.
We iterate from 'M' to 'N'-1 for the rest of the subarrays.
In each iteration:-
- We remove ‘ARR[i-m]’ from multiset:-
  - If it is less than mid we decrease iterator 'MID' by ‘1’.
- We insert ‘ARR[i]’ in multiset:-
  - If it is less than equal to mid we increase iterator 'MID' by ‘1’.
- Calculate 'MEDIAN' in a similar way as described for the first subarray.
Finally, we return the array/list ‘ANS’.

Solve now