CareerCup

Just for simplicity assume X =2 , that mean we have 2 vectors.


Case 1: when 2 vectors sorted, we can simply use medians of median algorithm to find medain of combined vector.

Time complexity : O(logn)
Space complexity : O(1)

note: here n = n1+n2 ( n1 1st vector size , and n2 second vector size )
-----------------------------------
Case 2: when 2 vectors not sorted, then we better to use two Heaps (min & max).

1. if n is even, max and min heap sizes n/2 .
2. if n is odd, max heap size n/2 +1 , and min heap size n/2 .

3. add small elements of vector into max heap , simlarly add max elements into min heap.
4. After inserting n elemets into min & max heaps. if n is odd, max element in max heap is the medain.
5. if n is even, get max elm for max heap, and get min elm from min heap, avg of both elms is the median.

==================================================

if X is big number , I mean X > 2 . then use following algoriths

case 1: when all X vectors sorted.

step1: take MIN heap of size X , add first elemets of X vectors , now heap has x elemtns.
Step2: now delete min elemnt from heap, and add next element of vector which contains previously dleted min element.

step 3: repeat step 2 , till we get n/2 th min element. n/2 th element is median

TC = O(n);
SC = O(X) ;// heap size
-----------------------------
Case 2: x vectors are unsorted

We can use selection algorithm. this algorithm bit difficult to explain. you better to refer Coreman book . below I mentioned basic steps.
step1 : this algothm divides n elements into n/5 groups,
step2: find median of each group .
step3: find median of mediands.
step4: do some elemts reduction based on current median value.
step5: becuase of reduction , we can find median in O(n) TC.

This question makes no sense. Read about median on Wikipedia. It say its defined only on 1D data/scalar. I don't know what it means to find median of a vector