Find the median of all subarrays of a particular size.

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
22 upvotes
Asked in companies
OlaAdobeFlipkart limited

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 3
1 2 3 4  
4 4 
1 2 3 4
Sample Output 1:
2.0 3.0
2.5

Sample Output 1 Explanation:

Test case 1:

All the possible subarrays of size 3 are:-
[1,2,3] → Middle element of the subarray(in sorted manner) is 2. Therefore the median is 2.
[2,3,4] → Middle element of the subarray(in sorted manner) is 3. Therefore the median is 3.

Therefore the answer is [2.0,3.0].

Test case 2:

All the possible subarrays of size 4 are:-
[1,2,3,4] → Middle elements of the subarray are 2 and 3. Therefore the median is 2.5.

Therefore the answer is [2.5].
Sample Input 2:
2
4 1
1 2 3 4
8 4
1 2 3 4 4 3 2 1
Sample Output 2:
1.0 2.0 3.0 4.0
2.5 3.5 3.5 3.5 2.5
Hint

Naively iterate over all subarrays. 

Approaches (2)
Brute Force

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.
Time Complexity

O(N * M * log(M)), where ‘N’ denotes the size of array/list and ‘M’ denotes size of the subarray.

 

For an array/list of size ‘N’, we will have ‘N-M+1’ subarrays of size ‘M’ and for each subarray, we will sort it which takes O(M * logM).

Space Complexity

O(M), where ‘M’ denotes the size of the subarray.

 

We build an auxiliary array/list to store subarrays of size ‘M’.

Code Solution
(100% EXP penalty)
Find the median of all subarrays of a particular size.
Full screen
Console