Leetcode 4. Median of Two Sorted Arrays

Problem

Leetcode 4 - Median of Two Sorted Arrays

Example:

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

Approach

Visualization of the Approach:

Input: nums1 = [1,3], nums2 = [2]
A = [1,3], B = [2]
total = 3
half = 1

Since len(A) > len(B), swap A, B
A = [2], B = [1,3]
left = 0, right = 0
starting while loop till we find answer

We are finding mid point for both A and B
i = (left+right) // 2 = 0
j = half-i-2 = 1-0-2 = -1

Finding median for A and B, in case these are odd number, we find right
Aleft = A[i] = 2
Aright = A[i+1] = infinity since i+1 exceeds len(A)
Bleft = B[j] = -infinity since j < 0
Bright = B[j+1] = 1

Since Aleft <= Bright and Bleft <= Aright is false
Since Aleft > Bright, right = i-1

left = 0, right = -1
i = (left+right) // 2 = -1
j = half-i-2 = 1-(-1)-2 = 0
Aleft = A[i] = -infinity since i < 0
Aright = A[i+1] = 2
Bleft = B[j] = 1
Bright = B[j+1] = 3

Since Aleft <= Bright and Bleft <= Aright and total length is odd number
return min(Aleft, Bleft)

thus return 2

Here is the Python code for the solution:

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2

        if len(B) < len(A):
            B, A = A, B
        
        left, right  = 0, len(A)-1
        while True:
            i = (left+right) // 2
            j = half-i-2

            Aleft = A[i] if i >= 0 else float('-infinity')
            Aright = A[i+1] if (i+1) < 0 else float('infinity')
            Bleft = B[j] if j >= 0 else float('-infinity')
            Bright = B[j+1] if (j+1) < 0 else float('infinity')

            if Aleft <= Bright and Bleft <= Aright:
                if total % 2 == 0:
                    return max(Aleft, Bleft)
                return (max(Aleft+Bleft) + min(Aright+Bright)) / 2
            elif Aleft > Bright:
                right = i-1
            else:
                left = i+1    

Time Complexity and Space Complexity

Time Complexity: $O(log(min(n,m)))$ where $n$ is length of nums1 and $m$ is length of nums2

Space Complexity: $O(1)$