Reference: LeetCode
Difficulty: Hard

Problem

There are two sorted arrays nums1 and nums2 of size $m$ and $n$ respectively.

Find the median of the two sorted arrays. The overall run time complexity should be $O(\log{(m+n)})$.

You may assume nums1 and nums2 cannot be both empty.

Example: 

1
2
3
4
5
6
7
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

Analysis

Sorting

Put nums1 and nums2 into a new array nums, and sort nums.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  int m = nums1.length, n = nums2.length;
  
  // nums array
  int[] nums = new int[m + n];
  int count = 0;
  for (int i = 0; i < m; ++i, ++count) {
    nums[count] = nums1[i];
  }
  for (int i = 0; i < n; ++i, ++count) {
    nums[count] = nums2[i];
  }
  
  // sort
  Arrays.sort(nums);   // O((m + n)log(m + n))
  
  int mid = (m + n) / 2; // right-leaning
  if ((m + n) % 2 == 0) { // even
    return (nums[mid - 1] + nums[mid]) / 2.0;
  } else { // odd
    return nums[mid];
  }
}

Time: $O((m + n)\log{(m + n)})$
Space: $O(m + n)$

Two Pointers

Use two pointers to locate the index of the median. Process the pointers carefully with some special cases.

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
48
49
// (4 + 2 - 1) / 2 = 2  left-leaning
// 0 1 2 3 4 5 // move 2 (even)
// (3 + 2) / 2 = 2
// 0 1 2 3 4   // move 2 (odd)

// Two Pointers
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  int m = nums1.length, n = nums2.length;
  int numStep = (m + n - 1) / 2; // left-leaning (see the example above)
  int p1 = 0, p2 = 0;
  
  // Move to the first median
  for (int i = 0; i < numStep; ++i) { // number of steps to move before it reaches a median
    if (p1 < m && p2 < n) {
      if (nums1[p1] < nums2[p2]) p1 += 1;
      else p2 += 1;
    } else {
      if (p1 < m) p1 += 1;
      else p2 += 1;
    }
  }
  
  // Calculate the median
  // If nums1[p1] < nums2[p2], we have nums1[p1] as the median / left part of median.
  // If nums1[p1] >= nums2[p2], we have nums2[p2] as the median / ...
  // If p1 >= m (out of bound), we have nums2[p2] as the median / ...
  // If p2 >= n (out of bound), we have nums1[p1] as the median / ...
  double median = 0;
  if (p1 < m && p2 < n) { // in bound
    if (nums1[p1] < nums2[p2]) median = nums1[p1++];
    else median = nums2[p2++];
  } else { // out of bound
    if (p1 < m) median = nums1[p1++];
    else median = nums2[p2++];
  }
  
  // Process even case (right part of the median)
  if ((m + n) % 2 == 0) {
    if (p1 < m && p2 < n) {
      median += (nums1[p1] < nums2[p2]) ? nums1[p1] : nums2[p2];
    } else {
      if (p1 < m) median += nums1[p1];
      else median += nums2[p2];
    }
    median /= 2.0;
  }
  
  return median;
}

Time: $O(m + n)$
Space: $O(1)$

Reference: Finding the Median of 2 Sorted Arrays in Logarithmic Time (Question 6)

The idea is to avoid merging two arrays, since merging takes $O(m + n)$ time. We can use binary search to optimize the two-pointer approach.