Median of Two Sorted Arrays

Median of Two Sorted Arrays

January 30, 2023

Moch Lutfi
Name
Moch Lutfi
Twitter
@kaptenupi

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


Example 1:
Input: nums1 = [1,2], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,2] 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.

Solution

O(n+m)O(n+m) Brute Force

  • This solution start with merding 2 sorted array
  • Find mid index from merged arrays len(mergedArray)/2 as midIndex
    • If length is odd, return value from mergedArray[midIndex]
    • Otherwise, return value from (mergedArray[midIndex] + mergedArray[midIndex-1]) / 2
onm.go
onmsort.go

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m, n := len(nums1), len(nums2)
nums1 = append(nums1, make([]int, len(nums2))...)
for n > 0 {
if m == 0 || nums2[n-1] > nums1[m-1] {
nums1[m+n-1] = nums2[n-1]
n--
} else {
nums1[m+n-1] = nums1[m-1]
m--
}
}
midIndex := len(nums1) / 2
if len(nums1)%2 == 1 {
return float64(nums1[midIndex])
}
return float64(nums1[midIndex-1]+nums1[midIndex]) / 2.0
}

O(log(n+m))O(log(n+m)) solution

  • Median is defined as the average of the two middle elements in a sorted array.
  • The median can be represented as (A[(N-1)/2] + A[N/2])/2 in a one-array situation.
  • The cut positions in a two-array situation can be determined by the number of positions in each array and the desired cut position in one of the arrays. nums1 into [. . . . L1 | R1 . . . ] and nums2 into [. . . . L2 | R2 . . . ] respectively. so that [. . . . L1] + [. . . . L2] has equal number of elements as [R1 . . . ] + [R2 . . . ]. The goal is to find such cutting positions that give us the median values.
  • The left and right elements at each cut position are found by using the formula L = A[(C-1)/2] R = A[C/2]
  • Using binary search, If L1 > R2, we know current cutting position is incorrect. A valid cutting position for median should be on the left half of nums1.
  • If L2 > R1, we know current cutting position is incorrect. A valid cutting position for median should be on the right half of nums1.
  • If L1 < R2 and L2 < R1, that's the result. median = (max(L1, L2) + min(R1, R2)) / 2
olognm.go

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
n1 := len(nums1)
n2 := len(nums2)
if n1 < n2 {
return findMedianSortedArrays(nums2, nums1)
}
lo, hi := 0, n2*2
for lo <= hi {
mid2 := (lo + hi) / 2
mid1 := n1 + n2 - mid2
l1 := math.MinInt64
if mid1 != 0 {
l1 = nums1[(mid1-1)/2]
}
l2 := math.MinInt64
if mid2 != 0 {
l2 = nums2[(mid2-1)/2]
}
r1 := math.MaxInt64
if mid1 != n1*2 {
r1 = nums1[mid1/2]
}
r2 := math.MaxInt64
if mid2 != n2*2 {
r2 = nums2[mid2/2]
}
if l1 > r2 {
lo = mid2 + 1
} else if l2 > r1 {
hi = mid2 - 1
} else {
return float64(max(l1, l2)+min(r1, r2)) / 2.0
}
}
return -1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}

Reference