Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Examples

Example 1:

1
2
3
4
5

Input:
nums1 = [1,3], nums2 = [2]
Output:
 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

1
2
3
4
5

Input:
nums1 = [1,2], nums2 = [3,4]
Output:
 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Median Definition

Median Definition

Simpler version of problem - Median of Two Sorted Array of Equal or Same Size.

Method 1 - Brute Force by Merging 2 Arrays and Keeping Count

We can combine two arrays until we locate the middle one or two elements, but this requires O(n) space and time.

Method 2 - Binary Search with getKth Element

This problem can be transformed into finding the kth element, where k is (length of A + length of B)/2.

If either array is empty, the kth element is simply the kth element of the non-empty array. When k is 0, the kth element is the first element of either A or B.

In typical scenarios, we adjust the pointer to discard half of A and B recursively by comparing their medians:

1
2

if (aMid < bMid) Keep [aRight + bLeft]    
else Keep [bRight + aLeft]

Time complexity - O (log(n+m))

To find the median, calculate the total array length. Let m be the length of num1 and n be the length of nums2. The total length, len, determines the approach:

  • For an odd total length (e.g., num1 is 6 and nums2 is 7), the median is the 7th element, i.e., len/2 + 1.
  • For an even total length (e.g., both m and n are 6), the median is the average of the 6th and 7th elements, i.e., len/2 and len/2 + 1.

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

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
	int m = nums1.length;
	int n = nums2.length;
	int len = m + n;
	if(len % 2 == 0){
		double left =  (double)findKthHelper(nums1, 0, nums2, 0, len/2);
		double right =  (double)findKthHelper(nums1, 0, nums2, 0, len/2 + 1);
		return (double)(left + right)/2;
	}else{
		return findKthHelper(nums1, 0, nums2, 0, len/2 + 1);
	}
}
private int findKthHelper(int[] A, int aStart, int[] B, int bStart, int k){
	// If nums1 is exhausted, return kth number in nums2
	if(aStart >= A.length){
		return B[bStart + k - 1];
	}
	// If nums2 is exhausted, return kth number in nums1
	if(bStart >= B.length){
		return A[aStart + k - 1];
	}
	// Since nums1 and nums2 is sorted, the smaller one among the start point of nums1 and nums2 is the first one
	if(k == 1){
		return Math.min(A[aStart], B[bStart]);
	}
	
	int aMid = aStart + k/2 - 1;
	int bMid = bStart + k/2 - 1;
	int aVal = aMid >= A.length ? Integer.MAX_VALUE : A[aMid];
	int bVal = bMid >= B.length ? Integer.MAX_VALUE : B[bMid];
    // Throw away half of the array from nums1 or nums2. And cut k in half
	if(aVal <= bVal){
		return findKthHelper(A, aMid + 1, B, bStart, k - k/2);
	}else{
		return findKthHelper(A, aStart, B, bMid + 1, k - k/2);
	}
}

Complexity

  • ⏰ Time complexity: O(log (min(m,n))) where m and n is length of 2 input arrays. The primary function, findMedianSortedArrays, calls findKthHelper either once or twice, each with a time complexity of O(log(min(m, n))). - The binary search in findKthHelper reduces the search space by half each time it is called, leading to O(log(min(m, n))) in each call.
  • 🧺 Space complexity: O(log (min(m,n))), as we use recursion stack.

Method 3 - Iterative with Edge Case Handling

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

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int l1 = 0;
    int l2 = 0;
    int med1 = 0;
    int med2 = 0;
    int totalLength = nums1.length + nums2.length;
    for (int i=0; i<= totalLength/2; i++) {
        med1 = med2;
        // If all elements of nums1 are already considered
        if (l1 == nums1.length) {
            med2 = nums2[l2];
            l2++;
        // If all elements of nums2 are already considered
        } else if (l2 == nums2.length) {
            med2 = nums1[l1];
            l1++;
        // If element in nums1 is smaller than element in nums2
        } else if (nums1[l1] < nums2[l2] ) {
            med2 = nums1[l1];
            l1++;
        // If element in nums2 is smaller than element in nums1
        }  else {
            med2 = nums2[l2];
            l2++;
        }
    }

    // if totalLength is even, median is the average of the two middle elements
    if (totalLength % 2 == 0) {
        return (float)(med1+med2)/2;
    }
	// if totalLength is odd, median is the middle element
    return med2;
}

Complexity

  • ⏰ Time complexity: O(m + n), as i iterates from 0 to (m + n) / 2.
  • 🧺 Space complexity: O(1)