Median of the subarray.

Revision en1, by v0rtex, 2021-10-11 23:22:38

If you are given an unsorted array of size N and some queries Q which consists of l,r as the range of the subarray. The task is to find the median of this subarray. 1<=N,Q<=5*10^4. Now if we sort the subarray per query the time complexity will be Q*nlogn (here n is the length of the subarray) which will give us TLE. Can anybody share the optimal approach?

Tags range query, median, sorting, time limit exceeded


  Rev. Lang. By When Δ Comment
en1 English v0rtex 2021-10-11 23:22:38 381 Initial revision (published)