Median of an array

A median of a population is any value such that at most half of the population is less than the proposed median and at most half is greater than the proposed median

It is a value which divides an array into 2 equal parts

1. Odd length array , median = a[mid];
2. Even length array, median = (a[mid]+ a[mid+1])/2

Given a randomly ordered array, find median-

Solution

Step 1: Sort

Step 2: find the median using formula

TC = O(nlogn) + O(1) = O(nlogn)

Given a stream of numbers, find median

Solution 1:

Sort for each number comes from stream & calculate median

TC = nlogn + (n-1)log(n-1) + (n-2)*log(n-2)+…. = ~(n²)*(logn)

Solution 2: Insertion sort

For every number, insert number into correct position & calculate median

TC for each input: O(n)

TC for stream with n numbers — O(n*n)

Solution 3: Heap

Create 2 heap such that left heap is maxHeap & right Heap is min Heap

For each input element,

if element is lesser than root of left heap then insert into left heap else insert into right heap

Adjust heap such that diff of heap size is 1 or 0

Find Median -

if size of left + right heap is odd than return root of max size heap

Else return average of (left + right heap)

TC for each input = O(insertion in heap) + O(adjust heap) + O(calculate median) = 2*O(logn) = O(logn)

TC for n input = O(n*logn)

Given 2 sorted array, find median

Solution 1:

Step 1: merge into 1 array

Step 2: Find median

TC = O(n+m) + O(1) = O(n+m)

SC = O(n+m)

Solution 2: Binary search

Step1: partition both arrays such that all elements on left side array(in both arrays) are smaller than right side elements & divide such that diff in size of left array & size of right side array is 0 or 1.

Calculate Median -

If the size is odd

Return max(left element of partition A, left Element of partition B)

Else

Return avg( max(leftElement of partition A, left Element of partition B) , man(right Ele of partition A, right Element of partition B))

TC = O(log(min(n,m)))