LeetCode 0004. Median of Two Sorted Arrays Solution in Java, C++, Python & More | Explanation + Code

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

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^{m + n + 1}⁄₂\right\rfloor-th number; if m + n is even, then the median is the average of the \left\lfloor^{m + n + 1}⁄₂\right\rfloor-th and the \left\lfloor^{m + n + 2}⁄₂\right\rfloor-th numbers. In fact, we can unify it as the average of the \left\lfloor^{m + n + 1}⁄₂\right\rfloor-th and the \left\lfloor^{m + n + 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 nums1 and the interval [j, n) of array nums2. The median is the average of f(0, 0, \left\lfloor^{m + n + 1}⁄₂\right\rfloor) and f(0, 0, \left\lfloor^{m + n + 2}⁄₂\right\rfloor).

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

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

The time complexity is O(log(m + n)), and the space complexity is O(log(m + n)). Here, m and n are the lengths of arrays nums1 and nums2 respectively.

PythonJavaC++GoTypeScriptJavaScriptC#PHPNimC

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(code-box)

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); } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

/** * @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; };(code-box)

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); } }(code-box)

class Solution { /** * @param int[] $nums1 * @param int[] $nums2 * @return float */ function findMedianSortedArrays($nums1, $nums2) { $arr = array_merge($nums1, $nums2); sort($arr); $cnt_arr = count($arr); if ($cnt_arr % 2) { return $arr[$cnt_arr / 2]; } else { return ($arr[intdiv($cnt_arr, 2) - 1] + $arr[intdiv($cnt_arr, 2)]) / 2; } } }(code-box)

import std/[algorithm, sequtils] proc medianOfTwoSortedArrays(nums1: seq[int], nums2: seq[int]): float = var fullList: seq[int] = concat(nums1, nums2) value: int = fullList.len div 2 fullList.sort() if fullList.len mod 2 == 0: result = (fullList[value - 1] + fullList[value]) / 2 else: result = fullList[value].toFloat() # Driver Code # var # arrA: seq[int] = @[1, 2] # arrB: seq[int] = @[3, 4, 5] # echo medianOfTwoSortedArrays(arrA, arrB)(code-box)

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; }(code-box)