Find the median of all subarrays of a particular size.

Posted: 5 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
Try Problem