Skip to main content

4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

Python​

Merge and Sort​

  • Time: O((M+N)log(M+N)) # For the sorting
  • Space: O(M+N)
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        merged = sorted(nums1 + nums2)

        mid = len(merged) >> 1
        if len(merged) % 2 == 1:
            return merged[mid]
        else:
            return (merged[mid] + merged[mid-1]) / 2

Use the sorted advantage​

  • Time: O(M+N)
  • Space: O(M+N)
from collections import deque

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        merged = deque()

        # Merge and keep it sorted
        while nums1 or nums2:
            if not nums1:
                merged.appendleft(nums2.pop())
            elif not nums2:
                merged.appendleft(nums1.pop())
            else:
                if nums1[-1] > nums2[-1]:
                    merged.appendleft(nums1.pop())
                else:
                    merged.appendleft(nums2.pop())

        mid = len(merged) >> 1
        if len(merged) % 2 == 1:
            return merged[mid]
        else:
            return (merged[mid] + merged[mid-1]) / 2