Test H1

The video explains how to solve the "Median of Two Sorted Arrays" problem from LeetCode, which requires finding the median of two sorted arrays with a time complexity of O(log(m+n)).

The most straightforward approach is to merge the two sorted arrays into a single sorted array. The time complexity of this approach is O(m+n), which is not optimal for this problem.

1. Create a new array by merging nums1 and nums2.
2. Sort the merged array.
3. Find the median based on whether the total number of elements is odd or even.

A more efficient solution involves using binary search to partition the arrays and find the median without merging them.

Partition the smaller array (let's say A) at a midpoint i. Based on the total number of elements, a corresponding partition point j is determined in the other array (B).

The goal is to find partitions where:

• Every element in the left partition of A is less than or equal to every element in the right partition of B.
• Every element in the left partition of B is less than or equal to every element in the right partition of A.

# Initialize pointers for binary search
l, r = 0, len(A) - 1

while True:
    i = (l + r) // 2
    j = half - i - 2

Compare the elements at the boundaries of the partitions (Aleft, Aright, Bleft, Bright). If the partitions are incorrect, adjust the binary search range.

• If Aleft > Bright, it means the partition in A is too large. Adjust by moving the right pointer: r = i - 1.
• If Bleft > Aright, the partition in A is too small. Adjust by moving the left pointer: l = i + 1.

    if Aleft <= Bright and Bleft <= Aright:
        # Correct partition found
        break
    elif Aleft > Bright:
        r = i - 1
    else:
        l = i + 1

Once the correct partitions are found, calculate the median.

• If the total number of elements is odd, the median is the minimum of the first elements in the right partitions of A and B.
• If the total number of elements is even, the median is the average of the maximum element from the left partitions and the minimum element from the right partitions.

# For odd number of elements
if total % 2:
    return min(Aright, Bright)

# For even number of elements
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2

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):
            A, B = B, A

        l, r = 0, len(A) - 1

        while True:
            i = (l + r) // 2
            j = half - i - 2

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

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