CareerCup

def find_median_lazy( a, b ){
  s = sset() // sorted set 
  s += a 
  s += b 
  l = list(s) // done, to get indexer up 
  len = size(l)
  if ( len == 0 ) return null
  // and now the rest 
  mid = len/2 
  if ( len % 2 == 0 ){
    // even case, then 
    return (l[mid-1] + l[mid])/2.0
  }
  return l[mid] 
}
println( find_median_lazy( [1,2] , [3,4] ) )
println( find_median_lazy( [1,2,5] , [3,4] ) )

def _merge_(a,b){
  l = list()
  i_a = 0 
  l_a = size(a)
  i_b = 0 
  l_b = size(b)
  while ( i_a < l_a && i_b < l_b ){
    if ( a[i_a] < b[i_b] ){
      l += a[i_a]
      i_a += 1 
    } else {
      l += b[i_b]
      i_b += 1
    }
  }
  while ( i_a < l_a ){
    l += a[i_a]
    i_a += 1
  }
  while ( i_b < l_b ){
    l += b[i_b]
    i_b += 1
  }
  l // return 
}
def find_median_with_unnecessary_work(a,b){
  l = _merge_(a,b)
  len = size(l)
  if ( len == 0 ) return null
  // and now the rest 
  mid = len/2 
  if ( len % 2 == 0 ){
    // even case, then 
    return (l[mid-1] + l[mid])/2.0
  }
  return l[mid]
}

println( find_median_with_unnecessary_work( [1,2] , [3,4] ) )
println( find_median_with_unnecessary_work( [1,2,5] , [3,4] ) )

Can you give couple of the example data what is required ?

Here is a better solution that still uses O((M+N)/2) complexity but with minimal space:

#include "CommonHeader.h"

double findMedian(const std::vector<int>& arr1, const std::vector<int>& arr2)
{
    // Sanity
    size_t arr1Index = 0;
    size_t arr2Index = 0;
    size_t maxMergedSize = arr1.size() + arr2.size();
    bool isOdd = ((maxMergedSize % 2) != 0);

    // We need to merge both arrays and return the median
    // Incase the merged array size is odd we need to merge halfway and return the last element in the merged array
    // otherwise, we return the avg of the two last elements of the merged array
    size_t minMergedSize = isOdd ? (maxMergedSize / 2) : ((maxMergedSize / 2) + 1);
    size_t elementsToKeep = isOdd ? 1 : 2;

    size_t counter = 0;
    // We use queue to keep the values of the last 2 elements (or 1, depends on the total number of numbers of both arrays)
    std::queue<int> q;
    while(true) {
        int a = arr1[arr1Index];
        int b = arr2[arr2Index];
        if(a < b) {
            q.push(a);
            if(q.size() > elementsToKeep) q.pop();
            arr1Index++;
        } else {
            q.push(b);
            if(q.size() > elementsToKeep) q.pop();
            arr2Index++;
        }
        ++counter;
        if(counter == minMergedSize) break;
    }

    if(isOdd) {
        // return the last number in the array
        return (double) q.front();
    } else {
        // we cast to double to allow decimal points
        double a = q.front(); q.pop();
        double b = q.front(); q.pop();
        return (a + b) / 2.0;
    }
}

a = [0,1,2,3,4] , b = [ -10, -2 ]
That is, no duplicate.

But in the question you are asking to find median element ?

"Given two sorted integer arrays, find the median element. Note that for an even sized collection, median element is to be defined as the average of the central two elements."

Merge both arrays and return the median.
However, we don't need to fully merge the arrays only O((M+N)/2) where M and N are the array sizes.

#include "Common.h"

double findMedian(const std::vector<int>& arr1, const std::vector<int>& arr2)
{
    size_t arr1Index = 0;
    size_t arr2Index = 0;
    size_t maxMergedSize = arr1.size() + arr2.size();
    bool isOdd = ((maxMergedSize % 2) != 0);
    
    // We need to merge both arrays and return the median
    // Incase the merged array size is odd we need to merge halfway and return the last element in the merged array
    // otherwise, we return the avg of the two last elements of the merged array
    size_t minMergedSize = isOdd ? (maxMergedSize / 2) : ((maxMergedSize / 2) + 1);
    
    std::vector<int> mergedArray;
    while(true) {
        int a = arr1[arr1Index];
        int b = arr2[arr2Index];
        if(a < b) {
            mergedArray.push_back(a);
            arr1Index++;
        } else {
            mergedArray.push_back(b);
            arr2Index++;
        }
        if(mergedArray.size() == minMergedSize) break;
    }

    if(isOdd) {
        // return the last number in the array
        return (double)mergedArray[mergedArray.size() - 1];
    } else {
        // we cast to double to allow decimal points
        return (double)(mergedArray[mergedArray.size() - 1] + mergedArray[mergedArray.size() - 2]) / 2.0;
    }
}

PenChief and NoOne, why do you actually need to perform the merge?
You can just run through the merge process without actually storing the results. Thus, it becomes an O(1) algo.

The following is just to give an idea. I definitely did not cover the corner cases.

int A = arr1.length;
	int B = arr2.length;
	int m = (int)(A+B)/2; // The index of the first median element in the merged array
	int n = (A+B) % 2 == 0 ? 2 : 1; // No. of median elements
	
	int i, j;
	while(i < A && j < B && (i+j) < m) {
		int a = arr1[i];
		int b = arr2[j];
		if (a < b)
			i++;
		else
			j++;
	}

	while(i < B && (i+j) < m)
		i++;

	while(j < B && (i+j) < m)
		j++;

	if (i == A) {
		return n == 1 ? arr2[j] : (arr2[j]+arr2[j+1])/2;
	} else if (j == B)
		return n == 1 ? arr1[i] : (arr1[i]+arr1[i+1])/2;
	} else {
		int x = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];
		int y = arr1[j] < arr2[j] ? arr1[i] : arr2[j];
	}

@RajK you are partially correct, the complexity is the same (O((N+M)/2) you only save space. In your code you still need to run over the array so its *not* O(1), since you need to run half way its O((M+N)/2) where M and N are the array length

public static void main(String[] args) {
		int[] arr1 = { 1, 2, 5 };
		int[] arr2 = { 3,4 };
		int n = getMedian(arr1, arr2);
		System.out.println(n);
	}

	public static int getMedian(int[] arr1, int[] arr2) {
		int n = arr1.length;
		int m = arr2.length;
		int q = n + m;

		if (q % 2 == 0)
			return (getKthPositionValue(arr1, arr2, q / 2) + getKthPositionValue(arr1, arr2, q / 2+1)) / 2;
		else
			return getKthPositionValue(arr1, arr2, q / 2+1);
	}

	public static int getKthPositionValue(int[] arr1, int[] arr2, int k) {
		int n = arr1.length;
		int m = arr2.length;

		int i = 0;
		int j = 0;
		while (i < n && j < m) {
			if (i < arr1.length && j < arr2.length && arr1[i] < arr2[j]) {
				i++;
				k--;
				if (k == 0)
					return arr1[i - 1];
			}
			if (i < arr1.length && j < arr2.length && arr2[j] < arr1[i]) {
				j++;
				k--;
				if (k == 0)
					return arr2[j - 1];
			}
		}
		if (i < arr1.length - 1 && (k + i -1) < n) {
			return arr1[k + i -1];
		}
		if (j < arr2.length - 1 && (k + j -1) < m) {
			return arr2[k + j -1];
		}
		return -1;
	}

There is a solution without merge, thus O(1) space complexity and and time complexity of something like O(lg(m)*lg(n)) or O(lg(m+n)) [depending on how smart you implement it] which is basically a simultaneous binary search over the two arrays. It goes like this:
- since the array are sorted, you can jump into the middle of the first array, pick that element and binary search it in the second array, then you know the order of that element (e.g. k-th order). since you are looking for n/2 or n/2-1 and n/2 you can correct, so you repeat it but only consider the first arrays upper or lower part etc.
- The corner cases are ugly, if you want to optimize constant factors etc.
if you are interested there is the exact same question on leetcode including some explanations in quite some details. How ever, you'll need to write it on a piece of paper to fully understand corner cases and cleanly code it.

final static int ARR1 = 0;
    final static int ARR2 = 1;
    
    static int median(int[] arr1, int[] arr2) {
        int[][] arrs = new int[][]{arr1,arr2};
        int[] ptrs = new int[] {-1,-1};   
        int length = arr1.length + arr2.length;
        int middle = 1 + (length/2);
        int prev = 0;
        int median = 0;
        for (int i = 0; i < middle; i++) {
            int which;
            if (ptrs[ARR1] >= arrs[ARR1].length - 1) {
                // reached end of ARR1 so must move ARR2
                which = ARR2;
            } else if (ptrs[ARR2] >= arrs[ARR2].length - 1) {
                // reached end of ARR2 so must move ARR1
                which = ARR1;
            } else if (arrs[ARR1][ptrs[ARR1]+1] >= arrs[ARR2][ptrs[ARR2]+1]) {
                // next ARR1 is bigger than next ARR2, so move ARR2
                which = ARR2;
            } else {
                which = ARR1;
            }
            prev = median;
            ptrs[which]++;
            median = arrs[which][ptrs[which]];
        }
        if (length % 2 == 0) {
            // its even, so return the average (cast to int, but could be returned as a double)
            return (median + prev) / 2;
        }
        return median;
    }

std::vector<int> v1{ 1, 5, 7, 8, 9 };
    std::vector<int> v2{ 2, 3, 6, 7, 8, 10 };

    std::vector<int> v3(v1.size() + v2.size());

    std::copy(v1.begin(), v1.end(), v3.begin());
    std::copy(v2.begin(), v2.end(), v3.begin() + v1.size());

    std::inplace_merge(v3.begin(), v3.begin() + v1.size(), v3.end());

    int middle = v3.size() / 2;
    if (v3.size() % 2 == 0 && v3.size() > 1)
    {
        return (float)(v3[middle] + v3[middle+1]) * .5f;
    }

    return (float)v3[middle];

median xs
| trueCenter = xs!!center
| otherwise = (xs!!center + xs!!center+1)/2
where
center = floor $ realToFrac (length xs) / 2
trueCenter = (realToFrac (length xs) / 2) == realToFrac center

merge [] ys = ys
merge (x:xs) ys = x : (merge xs ys)

main = do
print "Median of the list"
print $ merge [1,2,3,4,5,7] [6,8,9, 10, 11, 12]
print $ median $ merge [1,2,3,4,5,7] [6,8,9, 10, 11, 12]

do we really need to merge 2 arrays, why not loop (M+N)/2 +1 times and just get 2 middle numbers and add a small check for even or odd

public class MedianArrays {
    public static void main(String[] args) {
        int[] arr1 = {4,5,6,7,15,20,34,66,71};
        int[] arr2 = {0,37,99,133,155,178,200};

        int k1, k2 = -1, value1 = 0, value2 = 0;
        if ( (arr1.length + arr2.length)%2 == 0 ) {
            k1 = (arr1.length + arr2.length)/2 ;
            k2 = k1+1;
        } else {
            k1 = (arr1.length + arr2.length)/2 + 1;
        }

        int i = 0, j = 0;
        for ( int k = 0; k < (k1<k2?k2:k1); k++ ) {
            value1 = value2;
            if ( arr1[i] <= arr2[j] ) {
                value2 = arr1[i++];
            } else {
                value2 = arr2[j++];
            }
            System.out.print(value2 + ",");
        }
        System.out.println();
        if ( k2 == -1 ) {
            System.out.println(value2);
        } else {
            System.out.println((value1 + value2)/2.0);
        }
    }

}

array1 = [1,6,7,8,9,12,15,16]
array2 = [2,5,12,13]


def find_median(array1, array2):
    size = len(array1) + len(array2)
    index = int(size/2)
    even = (size%2 == 0)
    i =0
    j=0
    count = 0
    median = []
    current = 0
    prev= 0
    while count < index + 1:
        prev = current
        if(i < len(array1) and (len(array2) == j) or array1[i] < array2[j]):
            current = array1[i]
            i= i+1

        elif j < len(array2):
            current = array2[j]
            j = j+1

        count = count + 1
    if even:
        return (prev + current)/2
    else:
        return current


print(find_median(array1, array2))

array1 = [1,6,7,8,9,12,15,16]
array2 = [2,5,12,13]


def find_median(array1, array2):
    size = len(array1) + len(array2)
    index = int(size/2)
    even = (size%2 == 0)
    i =0
    j=0
    count = 0
    median = []
    current = 0
    prev= 0
    while count < index + 1:
        prev = current
        if(i < len(array1) and (len(array2) == j) or array1[i] < array2[j]):
            current = array1[i]
            i= i+1

        elif j < len(array2):
            current = array2[j]
            j = j+1

        count = count + 1
    if even:
        return (prev + current)/2
    else:
        return current


print(find_median(array1, array2))

and

array1 = [1,6,7,8,9,12,15,16]
array2 = [2,5,12,13]


def find_median(array1, array2):
size = len(array1) + len(array2)
index = int(size/2)
even = (size%2 == 0)
i =0
j=0
count = 0
median = []
current = 0
prev= 0
while count < index + 1:
prev = current
if(i < len(array1) and (len(array2) == j) or array1[i] < array2[j]):
current = array1[i]
i= i+1

elif j < len(array2):
current = array2[j]
j = j+1

count = count + 1
if even:
return (prev + current)/2
else:
return current


print(find_median(array1, array2))

and