Median of Two Sorted Arrays

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 2:

Solution

$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

$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

Reference

• https://leetcode.com/problems/median-of-two-sorted-arrays/solutions/2471/very-concise-o-log-min-m-n-iterative-solution-with-detailed-explanation/ (opens in a new tab)