Median of Two Sorted Arrays LeetCode Problem [Python]

The Median of Two Sorted Arrays LeetCode problem presents us with a challenging task: given two sorted arrays, find the median of the both arrays.

The task: given two sorted arrays, nums1 and nums2, each of size m and n respectively, we need to find the median of the two arrays when they are merged and sorted.

The problem also requires an efficient solution with a time complexity of O(log(m + n)).

m being the size of the first array, while n is size of the second input array.

Let’s break down the problem with examples:

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: When we merge the arrays [1, 3] and [2], we get [1, 2, 3], and the median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: Merging the arrays results in [1, 2, 3, 4], and the median is calculated as (2 + 3) / 2 = 2.5.

Understanding the Constraints

Before diving into the solution, let’s grasp the constraints of the problem:

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

Efficient Solution to Median of Two Sorted Arrays LeetCode

Now, let’s implement an efficient solution for this problem using Python.

I will explain how the code works momentarily.

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

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

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

        # Check if the partition is correct
        if Aleft <= Bright and Bleft <= Aright:
            # Odd case
            if total % 2:
                return min(Aright, Bright)
            # Even case
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
        elif Aleft > Bright:
            right = i - 1
        else:
            left = i + 1

The core idea behind this solution is to find the correct partition of the two arrays in a way that ensures the elements in the left partition are less than or equal to the elements in the right partition.

This method allows us to determine the median efficiently, with a time complexity of O(log(min(m, n))).

Let me provide an explanation and an example walkthrough of how this code works:

1. Initialize variables:

• A and B are assigned to the input arrays nums1 and nums2, and total is the sum of their lengths.
• half is set to half of the total number of elements.

1. Ensure that B is the longer array:

• If the length of array B is less than the length of array A, swap the references of A and B. This step helps optimize the partitioning process.

1. Initialize pointers for binary search:

• left and right are set to the beginning and end indices of array A.

1. Start a binary search loop:

• The loop continues until a valid partition is found.

1. Inside the loop:

• Calculate i as the midpoint in array A.
• Calculate j as the corresponding index in array B based on the partition.
• Determine the left and right elements for both arrays A and B for the current partition.

1. Check if the partition is correct:

• If Aleft is less than or equal to Bright and Bleft is less than or equal to Aright, it means that the partition is valid.

1. Handle odd and even cases:

• If the total number of elements is odd, return the minimum of Aright and Bright as the median.
• If the total number of elements is even, return the average of the maximum of Aleft and Bleft and the minimum of Aright and Bright.

1. Adjust pointers for binary search:

• If Aleft is greater than Bright, it means the partition is too far to the right in A, so adjust right to i - 1.
• Otherwise, if Bleft is greater than Aright, it means the partition is too far to the left in A, so adjust left to i + 1.

1. Repeat the binary search loop until a valid partition is found, and the median is calculated and returned.

Example Walkthrough:
Let’s consider an example:

• nums1 = [1, 3] and nums2 = [2]

1. The initial setup:

• A is [1, 3], B is [2], total is 3, and half is 1.

1. The algorithm starts with left and right pointing to the beginning and end of A.
2. In the first iteration, i is calculated as 0, and j is -1. The elements Aleft, Aright, Bleft, and Bright are determined.
3. The partition is valid (Aleft <= Bright and Bleft <= Aright).
4. Since the total number of elements is odd, the median is the minimum of Aright and Bright, which is 2. So, the function returns 2 as the median.

Time and Space Complexity

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

Reasoning Behind Our Approach

We efficiently partition the two arrays by using binary search.

The core logic ensures that the left partition elements are less than or equal to the right partition elements, allowing us to determine the median efficiently.

The code is designed to handle both odd and even cases gracefully, returning the correct median value.

Similar LeetCode Questions by the Same Company

• Find Minimum In Rotated Sorted Array LeetCode
• Daily Temperatures LeetCode Problem
• 3Sum LeetCode Problem
• Container With Most Water LeetCode Problem
• Valid Parentheses LeetCode Problem

Conclusion

Solving the “Median of Two Sorted Arrays” problem efficiently is challenging, but with this approach, we achieve the desired time complexity of O(log(min(m, n))).

It’s essential to understand the problem constraints and the reasoning behind the solution.

I hope this explanation helps you grasp the concept and solve this problem with confidence.

Question Link

Feel free to comment, ask questions, make suggestions, and share this content to help others with this problem. Happy coding!