Median of Two Sorted Arrays

Merge input arrays using merge approach used in MergeSort, if the resultant array length is an even number, then take median as result[midIndex] + result[midIndex-1] / 2 , otherwise take median as result[midIndex].

1. Let's declare two variables i=0 and j=0 to track the indexes of nums1 and nums2 respectively.
2. Compare numbers from both arrays and take the smallest number into result array and repeat this process until one of the array is fully done.
3. Copy any remaining numbers from nums1 or nums2.
4. Now, you have result array fully sorted and you can take median of the resultant array.

Complexity:

Merging two sorted arrays, takes O (m + n) run time and takes O (m +n) space as we are copying sorted numbers into a resultant array.

/**
 * Utility method to compute median of a given array
 * @param array input array
 * @return median of input array, and throws IllegalArgumentException if the input array is Null or empty
 */
private static double getMedian(int[] array) {
	if(array == null || array.length ==0) {
		throw new IllegalArgumentException("input array cannot be null or empty");
	}
	if(array.length % 2 == 0) { // resultant array is an even length array
		int midIndex = array.length/2;
		return (double)(array[midIndex] + array[midIndex-1]) /2;
	}
	// if the resultant array is an odd length array
	return array[array.length/2];
}

/**
 *
 * Merges input arrays first and then take the median
 *
 * @param nums1 sorted array1
 * @param nums2 sorted array2
 * @return median of resultant array after merging
 */
public static double median_After_Merging(int[] nums1, int[] nums2) {

  //base cases
  if(nums1 == null || nums1.length == 0) { // if nums1 array is null or empty, result array will be nums2
    return getMedian(nums2);
  } else if (nums2 == null || nums2.length ==0) { // if nums2 array is null or empty, result array will be nums1
    return getMedian(nums1);
  }

  int[] result = new int[nums1.length + nums2.length];

  int i = 0; // index to track nums1 array
  int j = 0; // index to track nums2 array

  for(int k=0; k<result.length; k++) {
    if(i<nums1.length && j<nums2.length) {
      if(nums1[i]<=nums2[j]) { // if nums1 has smaller number take that into result array
        result[k] = nums1[i];
        i++;
      } else {
        result[k] = nums2[j]; // if nums2 has smaller number take that into result array
        j++;
      }
    } else {
      // copy any remaining elements from nums1 (or) nums2
      if(i<nums1.length) {
        result[k] = nums1[i];
        i++;
      }
      if(j<nums2.length) {
        result[k] = nums2[j];
        j++;
      }
    }
  }

  return getMedian(result);
}

The main idea in this approach is, as we compare elements from nums1 and nums2, just keep copy of the elements we need to compute median and ignore rest. If the resultant array after merging is going to be of length n, then we need at most n/2 +1 comparisons whether n is even or odd.

Let's take an example, say the given input arrays are nums1 = [1,4,9] and nums2 = [3,7,8] , when you merge them, this is the resultant array [1,3, 4,7 ,8,9], so the numbers required to compute median are located at 2^nd and 3^rd indexes. So, we only need to loop until 4th index.

Steps:

1. Let's declare two variables i=0 and j=0 to track the indexes of nums1 and nums2 respectively.
2. Declare two more variables m1=-1 and m2=-1 to store large numbers seen so far as we compare input arrays.

When resultant array is even length array:

1. In a for loop from 0 to n (inclusive) compare the elements from nums1 and nums2 and store the higher number into m2 (before storing it, copy the previous value from m2 into m1).
• If the highest number is taken from nums1 array, then increment i.
• If the highest number is taken from nums2 array, then increment j.
2. When i reach end of nums1 array, then look at elements from nums2 elements only.
3. When j reach end of nums2 array, then look at elements from nums1 elements only.
4. Once we have m1 and m2 values, take median as (m1 + m2) /2 .

When resultant array is odd length array:

1. Repeat the same exact steps as above in the case where resultant array length is even, but just copy minimum element in each loop into m1.
2. Finally return m1 as this will be the middle element when array merged.

Complexity:

For loop runs n/2 times, so it takes O (n) run time where n is the size of resultant array, and takes O (1) space as we are storing middle two numbers only into two temporary variables.

public static double median_While_Merging(int[] nums1, int[] nums2) {

  int i=0; // index to keep track of nums1
  int j=0; //index to keep track of nums2

  int m1=-1; // temporary variable to hold 1st mid element
  int m2=-1;// temporary variable to hold 2n mid element

  int mergedArrayLength = nums1.length + nums2.length;

  int n = mergedArrayLength/2;

  if(mergedArrayLength %2 ==0) { // if the result array is even length

    for (int k = 0; k <= n; k++) {
      m1 = m2;
      if(i != nums1.length && j != nums2.length) {
        m2 = nums1[i]<nums2[j] ? nums1[i++] : nums2[j++];
      } else if (i<nums1.length) {
        m2 = nums1[i++];
      } else {
        m2 = nums2[j++];
      }
    }
    return (double) (m1+m2)/2;
  } else { // if the result array is odd array length
    for (int k = 0; k <= n; k++) {
      if (i != nums1.length && j != nums2.length) {
        m1 = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
      } else if (i < nums1.length) {
        m1 = nums1[i++];
      } else {
        m1 = nums2[j++];
      }
    }
    return m1;
  }

}

The main idea in this approach is to find a partion point from both arrays where they become middle 4 elements of resultant array, and if arrays are smaller then we use temporary values such as Integer.MAX_VALUE to represent right most maxinum element and similarly Integer.MIN_VALUE to represent left most minimum element.

Steps:

1. Assume nums1 array is the smallest array, in case if it isn't then reverse the input arrays.
2. Declare two variables low and high with lower and higher bounds of nums1 array.

   int low = 0;
   int high = nums1.length;
   

3. Partition both arrays at following indexes.
   nums1 array ==> at (low + high) / 2 index.
   nums2 array ==> at (nums1.length + nums2.length + 1) / 2 - nums1 partition index, here we have added +1 because in case if the resultant array is an odd length array, then we want middile element to be on life side of partition.

   int x= nums1.length;
   int y = nums2.length;
   
   int partitionX = (low + high) /2;
   int partitionY = (x + y + 1)/2 - partitionX;
   

4. When you partition the arrays, say leftX and rightX are elements on left and right side of nums1 array, and leftY and rightY are left and right elements of nums2 array.
   Note that we have to handle edge cases as well, incase if there are no elements left of left or right ends of arrays.

   //partitionX == 0 is when there is nothing left on left side of the nums1 array
   //partitionX == x is when there is nothing left on right side of the nums1 array
   int leftX = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX-1];
   int rightX = partitionX == x ? Integer.MAX_VALUE : nums1[partitionX];
   
   //partitionY == 0 is when there is nothing left on left side of the nums2 array
   //partitionY == y is when there is nothing left on right side of the nums2 array
   int leftY = partitionY ==0 ? Integer.MIN_VALUE: nums2[partitionY-1];
   int rightY = partitionY ==y ? Integer.MAX_VALUE: nums2[partitionY];
   

5. Now, check for following conditions, when these condition are met, that means we found a partition from both arrays where these 4 elements are what comes in the middle of the resultant array.
• leftX, the left element of nums1 array is less than or equal to rightY, the right element of nums2 array.
• leftY, the left element of nums2 array is less than or equal to rightX, the right element of nums1 array.
6. If we find such partition as step-5, then take median as follows.
• If resultant array is an even length array, then median is Max(leftX, leftY) + Min(rightX, rightY) /2 .
• If resultant array is an odd length array, then median is Max(leftX, leftY).
7. If we did not find partition as step-5, then check if leftX > rightY, this means we are too far on the right side of array. So, decrement high by 1. Otherwise increment low by 1 and repeat ste-3 onwards.

public static double median_Using_Binary_Search(int[] nums1, int[] nums2) {


  if(nums1.length > nums2.length) {
    return median_Using_Binary_Search(nums2, nums1);
  }
  // assume nums1 is smaller array
  int x= nums1.length;
  int y = nums2.length;

  int low = 0;
  int high = x;
  while(low <=high) {

    int partitionX = (low + high) /2;
    int partitionY = (x + y + 1)/2 - partitionX;

    //partitionX == 0 is when there is nothing left on left side of the nums1 array
    //partitionX == x is when there is nothing left on right side of the nums1 array
    int leftX = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX-1];
    int rightX = partitionX == x ? Integer.MAX_VALUE : nums1[partitionX];

    //partitionY == 0 is when there is nothing left on left side of the nums2 array
    //partitionY == y is when there is nothing left on right side of the nums2 array
    int leftY = partitionY ==0 ? Integer.MIN_VALUE: nums2[partitionY-1];
    int rightY = partitionY ==y ? Integer.MAX_VALUE: nums2[partitionY];

    if(leftX<=rightY && leftY<=rightX) {
      if((x+y) % 2 == 0) {
        return (double) (Math.max(leftX, leftY) + Math.min(rightX, rightY)) /2;
      } else {
        return Math.max(leftX, leftY);
      }
    } else if (leftX>rightY) { // we are too far on the right side of array
      high = partitionX -1;
    } else {
      low  = partitionX + 1;
    }
  }
  return -1;
}