1
\$\begingroup\$

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.

nums1 = [1, 3] nums2 = [2]

The median is 2.0

def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

        concat = sorted(nums1 + nums2)
        median = concat[len(concat) //2] if len(concat)%2 != 0 else (concat[len(concat) //2]  \
                            +concat[((len(concat))//2)-1])/2
        return median

I want to make this faster.

\$\endgroup\$
  • 1
    \$\begingroup\$ That is a \$O((m+n)\log (m+n))\$ solution, not \$O(\log (m+n))\$. \$\endgroup\$ – Martin R Aug 7 at 5:13
  • \$\begingroup\$ can you tell me how you calculate that way? \$\endgroup\$ – monk Aug 7 at 8:02
  • \$\begingroup\$ and if you know the better solution let me know \$\endgroup\$ – monk Aug 7 at 8:03
  • 1
    \$\begingroup\$ You sort an array with \$ n+m \$ elements. – I suggest to have a look at the "Related” section on the right. There you'll find Q&As about the same problem, with more efficient solutions. \$\endgroup\$ – Martin R Aug 7 at 8:04
  • \$\begingroup\$ @MartinR due to how python sorts lists, this is actually only O(m+n). Timsort (which python uses) will detect the 2 sorted sub-sequences and merge them in one merge step. \$\endgroup\$ – Oscar Smith Aug 7 at 15:29