Day 24: Median of Two Sorted Arrays : Binary Search - leetcode - Python3

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 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.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

 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):

            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:

                # odd

                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

Time Complexity: O(log(min(n, m))), where n and m are the lengths of the input arrays nums1 and nums2, respectively. The algorithm performs binary search on the smaller array to find the correct partition position, and each iteration of the binary search reduces the search space by half. Therefore, the time complexity is logarithmic with respect to the smaller input size.

Space Complexity:O(1)

How it works:

1. Initialize variables A and B to refer to nums1 and nums2, respectively. These variables are used to represent the two input arrays.

2. Calculate the total length of the combined arrays nums1 and nums2 and store it in the total variable.

3. Calculate the index half which represents the middle position of the combined arrays by dividing total by 2 using floor division (//).

4. Compare the lengths of nums1 and nums2. If the length of nums2 is less than the length of nums1, swap the values of A and B. This ensures that A always refers to the array with the smaller length.

5. Initialize the left (l) and right (r) pointers for binary search. The left pointer (l) is set to 0, and the right pointer (r) is set to the length of array A minus 1.

6. Enter a loop that continues indefinitely (since there is a while True statement).

7. Calculate the midpoint index i as the floor division of the sum of l and r by 2. This represents the partition position for array A.

8. Calculate the corresponding partition position j for array B by subtracting i and 2 from half. This ensures that the total number of elements to the left of the partition in both arrays is equal to half.

9. Determine the left and right elements for both arrays (A and B) at the partition positions i and j, respectively. If i or j is less than 0, it means there are no elements to the left, so we assign negative infinity (float("-infinity")) to the respective variable. If i + 1 or j + 1 exceeds the array length, it means there are no elements to the right, so we assign positive infinity (float("infinity")) to the respective variable.

10. Compare the elements to check if the partition is correct. If the conditions Aleft <= Bright and Bleft <= Aright hold true, it means the partition is correct.

11. If the partition is correct, we check if the total number of elements is odd (total % 2 == 1). If it is, we return the minimum value between Aright and Bright as the median.

12. If the total number of elements is even (total % 2 == 0), we return the average of the maximum value between Aleft and Bleft and the minimum value between Aright and Bright as the median.

13. If the partition is not correct and Aleft is greater than Bright, it means the partition is too far to the right in array A. In this case, we update the right pointer (r) to i - 1 to search for a new partition position in the left half of array A.

14. If the partition is not correct and Bleft is greater than Aright, it means the partition is too far to the left in array A. In this case, we update the left pointer (l) to i + 1 to search for a new partition position in the right half of array A.

15. The loop continues until the correct partition position is found or until it breaks if the correct position cannot be found.