# Find the median of all subarrays of a particular size.

Posted: 5 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
`````` Approach 1

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.