Skip to content

4. Median of Two Sorted Arrays

DifficultyHard

Description

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)).

 

Example 1:

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

Example 2:

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.

 

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

Solutions

Solution 1: Divide and Conquer

Thinking

Merging the two sorted arrays and then reading the median is the direct approach, in \(O(m+n)\). \(m,n \le 10^3\) would pass, but the problem asks for \(O(\log(m+n))\), so a linear scan is out.

The bottleneck: the median only cares about the one or two middle positions after a merge. Smaller values need only be counted, not listed. Both arrays are sorted, so comparing each side’s \(\left\lfloor k/2 \right\rfloor\)-th element tells us which side’s first half cannot contain the \(k\)-th smallest, and we can drop that half at once.

So we never build a merged array; we search for the \(k\)-th remaining element. The median is the average of the \(\left\lfloor (m+n+1)/2 \right\rfloor\)-th and the \(\left\lfloor (m+n+2)/2 \right\rfloor\)-th, covering odd and even length with the same code. If one side has fewer than \(\left\lfloor k/2 \right\rfloor\) elements, treat it as \(+\infty\) and discard from the other side.

The problem requires the time complexity of the algorithm to be \(O(\log (m + n))\), so we cannot directly traverse the two arrays, but need to use the binary search method.

If \(m + n\) is odd, then the median is the \(\left\lfloor\frac{m + n + 1}{2}\right\rfloor\)-th number; if \(m + n\) is even, then the median is the average of the \(\left\lfloor\frac{m + n + 1}{2}\right\rfloor\)-th and the \(\left\lfloor\frac{m + n + 2}{2}\right\rfloor\)-th numbers. In fact, we can unify it as the average of the \(\left\lfloor\frac{m + n + 1}{2}\right\rfloor\)-th and the \(\left\lfloor\frac{m + n + 2}{2}\right\rfloor\)-th numbers.

Therefore, we can design a function \(f(i, j, k)\), which represents the \(k\)-th smallest number in the interval \([i, m)\) of array \(\textit{nums1}\) and the interval \([j, n)\) of array \(\textit{nums2}\). The median is the average of \(f(0, 0, \left\lfloor\frac{m + n + 1}{2}\right\rfloor)\) and \(f(0, 0, \left\lfloor\frac{m + n + 2}{2}\right\rfloor)\).

The implementation idea of the function \(f(i, j, k)\) is as follows:

  • If \(i \geq m\), it means that the interval \([i, m)\) of array \(\textit{nums1}\) is empty, so directly return \(\textit{nums2}[j + k - 1]\);
  • If \(j \geq n\), it means that the interval \([j, n)\) of array \(\textit{nums2}\) is empty, so directly return \(\textit{nums1}[i + k - 1]\);
  • If \(k = 1\), it means to find the first number, so just return the minimum of \(\textit{nums1}[i]\) and \(\textit{nums2}[j]\);
  • Otherwise, we find the \(\left\lfloor\frac{k}{2}\right\rfloor\)-th number in the two arrays, denoted as \(x\) and \(y\). (Note, if a certain array does not have the \(\left\lfloor\frac{k}{2}\right\rfloor\)-th number, then we regard the \(\left\lfloor\frac{k}{2}\right\rfloor\)-th number as \(+\infty\).) Compare the size of \(x\) and \(y\):
    • If \(x \leq y\), it means that the \(\left\lfloor\frac{k}{2}\right\rfloor\)-th number of array \(\textit{nums1}\) cannot be the \(k\)-th smallest number, so we can exclude the interval \([i, i + \left\lfloor\frac{k}{2}\right\rfloor)\) of array \(\textit{nums1}\), and recursively call \(f(i + \left\lfloor\frac{k}{2}\right\rfloor, j, k - \left\lfloor\frac{k}{2}\right\rfloor)\).
    • If \(x > y\), it means that the \(\left\lfloor\frac{k}{2}\right\rfloor\)-th number of array \(\textit{nums2}\) cannot be the \(k\)-th smallest number, so we can exclude the interval \([j, j + \left\lfloor\frac{k}{2}\right\rfloor)\) of array \(\textit{nums2}\), and recursively call \(f(i, j + \left\lfloor\frac{k}{2}\right\rfloor, k - \left\lfloor\frac{k}{2}\right\rfloor)\).

The time complexity is \(O(\log(m + n))\), and the space complexity is \(O(\log(m + n))\), where \(m\) and \(n\) are the lengths of arrays \(\textit{nums1}\) and \(\textit{nums2}\) respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def f(i: int, j: int, k: int) -> int:
            if i >= m:
                return nums2[j + k - 1]
            if j >= n:
                return nums1[i + k - 1]
            if k == 1:
                return min(nums1[i], nums2[j])
            p = k // 2
            x = nums1[i + p - 1] if i + p - 1 < m else inf
            y = nums2[j + p - 1] if j + p - 1 < n else inf
            return f(i + p, j, k - p) if x < y else f(i, j + p, k - p)

        m, n = len(nums1), len(nums2)
        a = f(0, 0, (m + n + 1) // 2)
        b = f(0, 0, (m + n + 2) // 2)
        return (a + b) / 2

 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
class Solution {
    private int m;
    private int n;
    private int[] nums1;
    private int[] nums2;

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        m = nums1.length;
        n = nums2.length;
        this.nums1 = nums1;
        this.nums2 = nums2;
        int a = f(0, 0, (m + n + 1) / 2);
        int b = f(0, 0, (m + n + 2) / 2);
        return (a + b) / 2.0;
    }

    private int f(int i, int j, int k) {
        if (i >= m) {
            return nums2[j + k - 1];
        }
        if (j >= n) {
            return nums1[i + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        int p = k / 2;
        int x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30;
        int y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30;
        return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        function<int(int, int, int)> f = [&](int i, int j, int k) {
            if (i >= m) {
                return nums2[j + k - 1];
            }
            if (j >= n) {
                return nums1[i + k - 1];
            }
            if (k == 1) {
                return min(nums1[i], nums2[j]);
            }
            int p = k / 2;
            int x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30;
            int y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30;
            return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p);
        };
        int a = f(0, 0, (m + n + 1) / 2);
        int b = f(0, 0, (m + n + 2) / 2);
        return (a + b) / 2.0;
    }
};

 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
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    var f func(i, j, k int) int
    f = func(i, j, k int) int {
        if i >= m {
            return nums2[j+k-1]
        }
        if j >= n {
            return nums1[i+k-1]
        }
        if k == 1 {
            return min(nums1[i], nums2[j])
        }
        p := k / 2
        x, y := 1<<30, 1<<30
        if ni := i + p - 1; ni < m {
            x = nums1[ni]
        }
        if nj := j + p - 1; nj < n {
            y = nums2[nj]
        }
        if x < y {
            return f(i+p, j, k-p)
        }
        return f(i, j+p, k-p)
    }
    a, b := f(0, 0, (m+n+1)/2), f(0, 0, (m+n+2)/2)
    return float64(a+b) / 2.0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    const m = nums1.length;
    const n = nums2.length;
    const f = (i: number, j: number, k: number): number => {
        if (i >= m) {
            return nums2[j + k - 1];
        }
        if (j >= n) {
            return nums1[i + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        const p = Math.floor(k / 2);
        const x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30;
        const y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30;
        return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p);
    };
    const a = f(0, 0, Math.floor((m + n + 1) / 2));
    const b = f(0, 0, Math.floor((m + n + 2) / 2));
    return (a + b) / 2;
}

 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
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    const f = (i, j, k) => {
        if (i >= m) {
            return nums2[j + k - 1];
        }
        if (j >= n) {
            return nums1[i + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        const p = Math.floor(k / 2);
        const x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30;
        const y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30;
        return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p);
    };
    const a = f(0, 0, Math.floor((m + n + 1) / 2));
    const b = f(0, 0, Math.floor((m + n + 2) / 2));
    return (a + b) / 2;
};

 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
public class Solution {
    private int m;
    private int n;
    private int[] nums1;
    private int[] nums2;

    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        m = nums1.Length;
        n = nums2.Length;
        this.nums1 = nums1;
        this.nums2 = nums2;
        int a = f(0, 0, (m + n + 1) / 2);
        int b = f(0, 0, (m + n + 2) / 2);
        return (a + b) / 2.0;
    }

    private int f(int i, int j, int k) {
        if (i >= m) {
            return nums2[j + k - 1];
        }
        if (j >= n) {
            return nums1[i + k - 1];
        }
        if (k == 1) {
            return Math.Min(nums1[i], nums2[j]);
        }
        int p = k / 2;
        int x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30;
        int y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30;
        return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p);
    }
}

 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
class Solution {
    /**
     * @param int[] $nums1
     * @param int[] $nums2
     * @return float
     */

    function findMedianSortedArrays($nums1, $nums2) {
        $m = count($nums1);
        $n = count($nums2);
        $a = $this->f($nums1, $nums2, $m, $n, 0, 0, intdiv($m + $n + 1, 2));
        $b = $this->f($nums1, $nums2, $m, $n, 0, 0, intdiv($m + $n + 2, 2));
        return ($a + $b) / 2;
    }

    private function f($nums1, $nums2, $m, $n, $i, $j, $k) {
        if ($i >= $m) {
            return $nums2[$j + $k - 1];
        }
        if ($j >= $n) {
            return $nums1[$i + $k - 1];
        }
        if ($k == 1) {
            return min($nums1[$i], $nums2[$j]);
        }
        $p = intdiv($k, 2);
        $x = $i + $p - 1 < $m ? $nums1[$i + $p - 1] : 1 << 30;
        $y = $j + $p - 1 < $n ? $nums2[$j + $p - 1] : 1 << 30;
        return $x < $y
            ? $this->f($nums1, $nums2, $m, $n, $i + $p, $j, $k - $p)
            : $this->f($nums1, $nums2, $m, $n, $i, $j + $p, $k - $p);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
proc medianOfTwoSortedArrays(nums1: seq[int], nums2: seq[int]): float =
  let
    m = nums1.len
    n = nums2.len

  proc f(i, j, k: int): int =
    if i >= m:
      return nums2[j + k - 1]
    if j >= n:
      return nums1[i + k - 1]
    if k == 1:
      return min(nums1[i], nums2[j])
    let p = k div 2
    let x = if i + p - 1 < m: nums1[i + p - 1] else: 1 shl 30
    let y = if j + p - 1 < n: nums2[j + p - 1] else: 1 shl 30
    if x < y:
      result = f(i + p, j, k - p)
    else:
      result = f(i, j + p, k - p)

  let
    a = f(0, 0, (m + n + 1) div 2)
    b = f(0, 0, (m + n + 2) div 2)
  result = (a + b) / 2

 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
int findKth(int* nums1, int m, int i, int* nums2, int n, int j, int k) {
    if (i >= m)
        return nums2[j + k - 1];
    if (j >= n)
        return nums1[i + k - 1];
    if (k == 1)
        return nums1[i] < nums2[j] ? nums1[i] : nums2[j];

    int p = k / 2;

    int x = (i + p - 1 < m) ? nums1[i + p - 1] : INT_MAX;
    int y = (j + p - 1 < n) ? nums2[j + p - 1] : INT_MAX;

    if (x < y)
        return findKth(nums1, m, i + p, nums2, n, j, k - p);
    else
        return findKth(nums1, m, i, nums2, n, j + p, k - p);
}

double findMedianSortedArrays(int* nums1, int m, int* nums2, int n) {
    int total = m + n;
    int a = findKth(nums1, m, 0, nums2, n, 0, (total + 1) / 2);
    int b = findKth(nums1, m, 0, nums2, n, 0, (total + 2) / 2);
    return (a + b) / 2.0;
}

Comments