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.


Comment