Subarray Median Queries

Moderate
0/80
0 upvote
Asked in company
Microsoft

Problem statement

You are given an array A of 'N' integers and 'Q' queries.

For each query, you are given a start index L and an end index R (1-based), which define a subarray A[L...R].

Your task is to find the median of this subarray. The median of a subarray is defined as the element that would be at the middle position if the subarray were sorted in non-decreasing order.


  • If the subarray's length is len, the median is the element at index floor((len + 1) / 2) of the sorted subarray (1-based index).


    • Detailed explanation ( Input/output format, Notes, Images )
    Input Format: 
    The first line of input contains an integer 'N'.
The second line contains 'N' space-separated integers, representing the elements of array A.
The third line contains an integer 'Q', the number of queries.
The next 'Q' lines each contain two space-separated integers, L and R.


    Output Format: 
    For each query, print the median of the subarray A[L...R] on a new line.


    Note: 
    The problem uses 1-based indexing for L and R, which should be converted to 0-based for array access in most languages.

A naive solution would be to extract the subarray, sort it, and find the middle element for each query. This is too slow (O(Q * N log N)).

An optimized approach for the given constraints would typically involve a persistent segment tree or a similar advanced data structure that can answer order statistic queries on a range in O(log N) time. A simpler approach using a Fenwick tree (BIT) or segment tree on a sorted, coordinate-compressed version of the values is also possible.
    Sample Input 1:
    5
3 1 2 5 4
2
1 5
2 4


    Sample Output 1:
    3
2


    Explanation for Sample 1:
    Query 1 (L=1, R=5): The subarray is `{3, 1, 2, 5, 4}`.
- Sorted, it becomes `{1, 2, 3, 4, 5}`.
- Length is 5. Median position is `(5+1)/2 = 3`.
- The 3rd element is 3.
Query 2 (L=2, R=4): The subarray is `{1, 2, 5}`.
- Sorted, it becomes `{1, 2, 5}`.
- Length is 3. Median position is `(3+1)/2 = 2`.
- The 2nd element is 2.


    Expected Time Complexity:
    The expected time complexity for an optimized solution is O((N+Q)*log(N)).


    Constraints:
    1 <= N, Q <= 10^5
-10^9 <= A[i] <= 10^9

Time limit: 1 sec
    Approaches (1)
    Subarray Median Queries
    Time Complexity
    Space Complexity
    Code Solution
    (100% EXP penalty)
    Subarray Median Queries
    Full screen
    Console