Problem

There are two sorted arrays nums1 and nums2 of size n. Find the median of the two sorted arrays.

You may assume nums1 and nums2 cannot be both empty.

OR There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))

Median Definition

Median Definition

Note → Since the size of the two input arrays for which we are looking for the median is even(2n), we need to take the average of the middle two numbers and return it.

Examples

Example 1:

1
2

nums1 = [1, 3]
nums2 = [2, 4]

1

The median is 2.5 as (2 + 3) / 2 = 2.5

Example 2:

1
2

nums1 = [1, 2, 9]
nums2 = [3, 4, 7]

1

The median is (3 + 4)/2 = 3.5

Solution

Method 1 - Brute Force

We can combine two arrays into a sorted array in O(n) time and then calculate the average of the middle two values. However, this approach is not efficient enough.

Method 2 - Counting While Comparing (kind of Brute force)

  1. Initialise two pointers, i and j, to 0, pointing to the start of nums1 and nums2, respectively.
  2. Compare the values at nums1[i] and nums2[j]; if nums1[i] is smaller, increment i; otherwise, increment j.
  3. Continue step 2 until the sum of i and j equals n.
  4. Finally, return the median of the elements at the i-th and j-th indexes.

Code

 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

int getMedian(int arr1[], int arr2[]) {
	int n = arr1.length;
	int i = 0; // Current index of array arr1[]
	int j = 0; // Current index of array arr2[]
	int count;
	int m1 = -1, m2 = -1;

	//Since there are 2n elements, median will be average
	// of elements at index n-1 and n in the array obtained after
	// merging ar1 and ar2
	for (count = 0; count<= n; count++) {
		//Below is to handle case where all elements of arr1[] are
		//  smaller than smallest(or first) element of arr2[]
		if (i == n) {
			m1 = m2;
			m2 = arr2[0];
			break;
		}

		//Below is to handle case where all elements of arr2[] are
		//  smaller than smallest(or first) element of arr1[]
		else if (j == n) {
			m1 = m2;
			m2 = arr1[0];
			break;
		}

		if (arr1[i]<arr2[j]) {
			m1 = m2; //Store the prev median
			m2 = arr1[i];
			i++;
		} else {
			m1 = m2; //Store the prev median
			m2 = arr2[j];
			j++;
		}
	}

	return (m1 + m2) / 2;
}

Complexity

  • ⏰ Time complexity: O(n) where n is the size of the input arrays
  • 🧺 Space complexity: O(1)

Method 3 - Comparing Medians - Divide and Conquer

This method involves comparing the medians of both arrays using the Divide & Conquer approach. Let us denote the medians by m1 and m2.

  • If m1 > m2, then the median will be in the union of nums1[0 to m1] and nums2[m2 to n]. This means we search for the median within nums1 from the beginning to median1 and within nums2 from median2 to the end. (Why?)

To sum up:

1
2
3
4
5

if (m1 > m2) {
	Take the left half of arr1 and the right half of arr2.
} else {
	Take the right half of arr1 and the left half of arr2.
}

We know median1 is at least as large as the first half of nums1, and similarly for median2 and nums2. We also know median1 is at most as large as the second half of nums1.

Consider the case where median1 > median2:

1
2
3

nums1:      [.....median1.....]
nums2:      [.....median2.....]
nums1+nums2: [.....median2...median1........]

Example

1
2

 nums1 = {1, 12, 15, 26, 38}
 nums2 = {2, 13, 17, 30, 45}

1

m1 = 15 and m2 = 17 for num1[0 to 4] and num2[0 to 4]

1
2

m1 < m2. So, the median is within {15, 26, 38} and {2, 13, 17}
Now, m1 = 26 and m2 = 13

1

m1 > m2. So, the median is within {15, 26} and {13, 17}

1
2

When both subarrays size is 2:
Median = (max(15, 13) + min(26, 17)) / 2 = 16

Algorithm

  1. Calculate the medians m1 and m2 of num1[] and num2[].

  2. Repeat until the size of num1 and num2 is two.

    • If m1 == m2, return m1.
    • If m1 > m2, the median is in num1[0..m1] and num2[m2 to n].
    • If m2 > m1, the median is in num1[m1 to n] and num2[0 to m2].

  3. Return Median = (max(array1[0], array2[0]) + min(array1[1], array2[1])) / 2.

Code

 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
44
45
46
47

public class MedianOfTwoSortedArrays {

	public double findMedianEqualSize(int[] nums1, int[] nums2) {
		int n = nums1.length;
		return helper(nums1, nums2, 0, 0, n);
	}

	private double helper(int[] nums1, int[] nums2, int start1, int start2, int n) {
		// Base cases when the size of both arrays is 2
		if (n == 1) {
			return (nums1[start1] + nums2[start2]) / 2.0;
		}

		if (n == 2) {
			return (Math.max(nums1[start1], nums2[start2]) + Math.min(nums1[start1 + 1], nums2[start2 + 1])) / 2.0;
		}

		int m1 = getMedian(nums1, start1, n);
		int m2 = getMedian(nums2, start2, n);

		if (m1 == m2) {
			return m1;
		}

		if (m1 < m2) {
			if (n % 2 == 0) {
				return helper(nums1, nums2, start1 + n / 2 - 1, start2, n - n / 2 + 1);
			} else {
				return helper(nums1, nums2, start1 + n / 2, start2, n - n / 2);
			}
		} else {
			if (n % 2 == 0) {
				return helper(nums1, nums2, start1, start2 + n / 2 - 1, n - n / 2 + 1);
			} else {
				return helper(nums1, nums2, start1, start2 + n / 2, n - n / 2);
			}
		}
	}

	private int getMedian(int[] nums, int start, int n) {
		if (n % 2 == 0) {
			return (nums[start + n / 2] + nums[start + n / 2 - 1]) / 2;
		} else {
			return nums[start + n / 2];
		}
	}
}

Complexity

  • ⏰ Time complexity: O(log n), where n is length of array, as we compare the medians of the two arrays and then recursively reduce the problem size.
  • 🧺 Space complexity: O(log n), assuming recursion stack