You are given 2 array of integers as input. They are sorted. Write a function can find the median of all the numbers.

First need to clarify what is median. When given a bunch of numbers, if you sort them, the number right in the middle is called the median. For example if we have [1, 2, 3, 4, 8, 9], the median is 4. When we have even number of numbers, it is the mean of those two in the middle. For example if we have [1, 2, 3, 4, 8, 9, 10], then the median is (4+8)/2=6

Next let’s solve the problem with a simple direct and easy to understand solution:

1 2 3 4 |
public static int findMedian(int[] a, int[] b) { int[] c = merge(a, b); return median(c); } |

Really simple, right? And we are very sure it is correct as long as the merge function and median function are correct. Well you probably will be asked to implement them during an interview so here is one version:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
public static int[] merge(int[] a, int[] b) { int m = a.length; int n = b.length; int[] c = new int[m+n]; int i=0, j=0, k=0; while (i < m && j < n) { if (a[i] < b[j]) { c[k] = a[i]; i++; } else { c[k] = b[j]; j++; } k++; // Or one line like this that is harder to read // c[k++] = (a[i] < b[j]) ? a[i++] : b[j++]; } // Obviously one of the following 2 while loops will not do anything while (i < m) { c[k] = a[i]; i++; k++; } while (j < n) { c[k] = b[j]; j++; k++; } return c; } public static int median(int[] c) { if (c.length %2 != 0) { return c[c.length/2]; } else { int median1 = c[c.length/2]; int median2 = c[c.length/2 - 1]; // return (median1 + median2)/2; //This may overflow return median1 + (median1 - median2)/2; } } |

Now, what is the problem with this approach? If you say it is too slow then you probably know the speed of the solution is O(m+n) which is linear. And you are right that we can do better than that but there are problems other than time. The action of merge array uses O(m+n) space which we can also avoid. But the bigger problem is that when we try to allocated the space for array c, we may not able to because m+n may overflow, same reason that I had to do the trick when I try to find the median. So let’s avoid it and avoid allocate a new array all together in part 2