Median of two sorted arrays of same size

In this approach, we are going to merge input arrays first, using merge approach used in MergeSort. Now we know that that the resultant array length is an even lenth array, so take median as (result[midIndex-1] + result[midIndex]) / 2 .

Steps:

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 (n) run time and takes O (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 medianUsingMergeSortApproach1(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, whether the input array length n is odd or even, we need to find out the middle two numbers from the resultant array. In the merge() process of MergeSort algorithm, we compare elements from left array to right array and start copy them in sorting order into resultant array, but we only need middle two numbers, so we can just do n+1 comparisons and take the values comes at n-1^th comparison and n^th comparison (Because, in Java array indexes starts with 0).

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. Since the array size in n, we need n+1 comparisons.

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.
3. 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.
4. There could be two other scenarios, where i will reach n, that means all numbers in nums1 array are smaller than the numbers from nums2 array, in this case take first element from nums2 as m2.
5. Other scenario, where j will reach n, that means all numbers in nums2 array are smaller than the numbers from nums1 array, in this case take first element from nums1 as m2.
6. Once we have m1 and m2 values, take median as (m1 + m2) /2 .

Complexity:

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

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

	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=-2;// temporary variable to hold 2n mid element

	for (int k =0; k<= n; k++) { // looping to n+1 times to compare elements as our median would be
                                    // from n-1 index element from first array and 0th index from second array
                                    // when the array is fully merged and sorted  [0,1,2....n-1] [0,1,2....n-1]

		if(i == n) { // where nums1 array elements are smaller than nums2,
                            // so i is incremented to the end index of nums1 array
                            // median would be nums1[n-1] = last element from nums1
                            // and nums2[0] = first element from nums2
                    m1 = m2;
                    m2 = nums2[0];
                    break;
		}

		if(j == n) { // where nums2 array elements are smaller than nums1
			m1 = m2;
			m2 = nums1[0];
			break;
		}

		// keep copying the smallest out of nums1 and nums2 into m1 and m2
		if(nums1[i]<=nums2[j]){
			m1 = m2;
			m2 = nums1[i];
			i++;
		} else {
			m1 = m2;
			m2 = nums2[j];
			j++;
		}
	}

	return (double) (m1+m2)/2;
}

In this approach, we are going to find out indexes from both input arrays where the median will reside using a binary search, the key here is, how we choose those indexes.

The main idea here is, since the input arrays are already sorted, and when input arrays are merged, it wil have elements from both arrays at the median, and our task is to find such indexes.

Solution

• If the input arrays length is 1, say A = [a1] and B = [b1], then median is simply a1 + b1 /2.
• If the input arrays length is 2, say A = [a1, a2] and B = [b1, b2], ad when the arrays are merged resultant array will be [Min(a1, b1), Max(a1, b1) , Min(a2, b2), Max(a2, b2)]. So the median is simply Max(a1, b1) + Min(a2, b2) /2.
• If the input array length is greater than 2, then we can compare medians of two input arrays m1 and m2, and check one of the following.
• If m1 == m2, then we have found our answer, return median.
  Example: A = [1, 3 ,5] and B = [2, 3, 7], so median of array A will be m1 = 3 and median of array B will be m2 = 3. Since m1 and m2 are same we can return either m1 or m2.
• If m1 < m2, then the median should be in this range from arrays A and B, A = [......m1........endA] and B = [startB......m2.......].
  Example: A = [1, 2, 3, 6] and B = [4, 6, 8, 10], so median of array A will be m1 = 2.5 and median of array B will be m2 = 7. Since m1 < m2, median should be in these sub arrays A = [3, 6] and B = [4, 6].
• If m1 > m2, then the median should be in this range from arrays A and B, A = [startA......m1........] and B = [......m2.......endB].
  Example: A = [4, 6, 8, 10] and B = [1, 2, 3, 6], so median of array A will be m1 = 7 and median of array B will be m2 = 2.5. Since m1 > m2, median should be in these sub arrays A = [4, 6] and B = [3, 6].
• Repeat above steps on the smaller sub arrays, if you notice above two cases where m1 < m2 or m1 > m2, we are reducing the input array size by half.

Complexity:

Time complexity will be log (n) times, because in each iteration, depeding on the medians of input arrays, we are reducing search range by half. Space complexity will be O (1).

public static double median_Using_Binary_Search(int[] nums1, int[] nums2) {
    if(nums1.length == 0) { // base case if input arrays have only one element
      return (double) (nums1[0] + nums2[0])/2;
    }
    return median_Using_Binary_Search_Recursive(nums1,nums2, 0, nums1.length-1, 0, nums2.length-1);
  }
  
  public static double getMedian(int[] input, int start, int end) {
    int length = end -start +1; // since index starts from 0
    int mid = length /2;
    if((length % 2) == 0) { // even array
      return (double)(input[mid-1] + input[mid]) / 2;
    } else {
      return input[mid];
    }
  }
  
  /**
   *
   * @param nums1
   * @param nums2
   * @param startA - start index of nums1 array
   * @param endA - end index of nums1 array
   * @param startB - start index of nums2 array
   * @param endB - end index of nums2 array
   * @return
   */
  public static double median_Using_Binary_Search_Recursive(int[] nums1, int[] nums2, int startA, int endA, int startB, int endB) {
  
    if (endA - startA == 1 && endB - startB == 1) { // If the nums1 array has only two elements
                // nums2 size is also same as nums1, per problem statement
      return (double)(Math.max(nums1[startA], nums2[startB]) + Math.min(nums1[endA], nums2[endB]) ) /2;
    }
  
    double m1 = getMedian(nums1, startA, endA);
    double m2 = getMedian(nums2, startB, endB);
  
    // if both medians are same, return either of them
    if(m1 == m2) {
      return m1;
    }
  
    int length = (endA - startA +1);
    boolean isEven = length % 2==0;
    int mid = isEven ? length/2-1 : length/2;
  
    // if m1 < m2 then the median will be between m1,endA from nums1[.... m1 ....endA...]
    // and startB and m2 of nums2 [...startB....m2...]
  
    if(m1<m2) {
      return median_Using_Binary_Search_Recursive(nums1, nums2, startA+(mid), endA, startB, endB - (mid));
    } else {
      return median_Using_Binary_Search_Recursive(nums1, nums2, startA, endA-mid,  startB+mid, endB);
    }
  
  }