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

Posted: 5 Mar, 2021

Difficulty: Moderate

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

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.

Approach 2

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.

- We remove ‘ARR[i-m]’ from multiset:-
- Finally, we return the array/list ‘ANS’.