Recently I have Doing a problem where an array of the duplicate elements is given and we have to answer Q query given. For each query, we have to tell whether the subarray contains the majority element or not? ( A subarray contain majority element if one of the element occur more than half of the length of subarray).
I know we can do this question by segment tree straight forward.
now I try to solve this question using the median of the subarray. if the occurrence of median is greater than half of it length than the subarray has majority element.
But now I am facing the problem of finding the median of subarray if it contains duplicate elements? I used merge sort Tree for finding the median of array. can anyone suggest me how to find the median of subarray efficiently?