Median of Two Sorted Arrays

Solutions

Binary Search

Time: O(log(min(m,n)))Space: O(1)

We use binary search to find the partition point for both arrays. The idea is to partition both arrays such that elements on the left side of the partition are less than the elements on the right side. We calculate the max element on the left side and the min element on the right side. If the max element on the left side is less than or equal to the min element on the right side, we have found the correct partition. If the total number of elements is even, the median is the average of the max element on the left side and the min element on the right side. If the total number of elements is odd, the median is the max element on the left side.


def findMedianSortedArrays(nums1, nums2):
    m, n = len(nums1), len(nums2); if m > n:
        nums1, nums2, m, n = nums2, nums1, n, m; low, high = 0, m; while low <= high:
            partitionX = (low + high) // 2; partitionY = (m + n + 1) // 2 - partitionX; maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]; minRightX = float('inf') if partitionX == m else nums1[partitionX]; maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]; minRightY = float('inf') if partitionY == n else nums2[partitionY]; if maxLeftX <= minRightY and maxLeftY <= minRightX:
                if (m + n) % 2 == 0:
                    return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2; else:
                        return max(maxLeftX, maxLeftY); elif maxLeftX > minRightY:
                            high = partitionX - 1; else:
                                low = partitionX + 1

Constraints:

Examples:

Solutions

Binary Search

Follow-up: