Median of Two Sorted Arrays – LeetCode Hard Solutions

Are you tired of being average? Well, data analysis has got you covered! Meet the median, the ultimate middle child of statistics. It’s like the cool cousin who shows up to family reunions and says, “Hey, I’m not the highest, nor the lowest, but I’m here, and I’m representative!” LeetCode’s 4th Hard problem, “Median of Two Sorted Arrays,” is like the median’s coming-out party – and you’re invited!

Problem Statement

Finding the Median of Two Sorted Arrays

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

Constraints:

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

What’s the Catch?

• The arrays are sorted, but merging them would be inefficient.
• The median might not be an integer.
• It would be best if you found a solution that’s faster than O((m+n) log(m+n)).

Find the median of two sorted arrays without merging them, optimizing for time and space complexity.

Approaches and Solutions

Brute Force Approach (Merging and Sorting)

The brute force approach involves merging the two sorted arrays into one and then finding the median.

def findMedianSortedArrays(nums1, nums2):
    # Merge and sort the arrays
    merged = sorted(nums1 + nums2)

    # Find the median
    length = len(merged)
    if length % 2 == 0:
        return (merged[length // 2 - 1] + merged[length // 2]) / 2
    else:
        return merged[length // 2]

Explanation:

• Merge nums1 and nums2 into a single array merged.
• Sort merged in ascending order.
• Calculate the median based on the length of the merged.

Why This Approach is Not Ideal:

• Time Complexity: O((m+n) log(m+n)) due to sorting, where m and n are the lengths of nums1 and nums2.
• Space Complexity: O(m+n) for storing the merged array.
• Inefficiency: Merging and sorting large arrays can be slow.

Limitations:

• This approach is impractical for large inputs.
• It doesn’t utilize the fact that the input arrays are already sorted.

Optimized Approach (Binary Search)

The optimized approach leverages binary search to find the median without merging the arrays.

Key Insights:

• The median is the middle element in the combined sorted array.
• We can find the median by partitioning the combined array into two halves.

Code Implementation (Python):

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    x, y = len(nums1), len(nums2)
    start = 0
    end = x

    while start <= end:
        partitionX = (start + end) // 2
        partitionY = (x + y + 1) // 2 - partitionX

        maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
        minRightX = float('inf') if partitionX == x else nums1[partitionX]

        maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
        minRightY = float('inf') if partitionY == y else nums2[partitionY]

        if maxLeftX <= minRightY and maxLeftY <= minRightX:
            if (x + y) % 2 == 0:
                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0
            else:
                return max(maxLeftX, maxLeftY)

        elif maxLeftX > minRightY:
            end = partitionX - 1

        else:
            start = partitionX + 1

    # Return statement for edge cases or errors
    return None  # or raise ValueError("Invalid input")

Explanation:

• Ensure nums1 is the smaller array.
• Initialize start = 0 and end = nums1.length.
• Calculate the partition point partitionX = (start + end) / 2.
• Calculate the corresponding partition point partitionY = (nums1.length + nums2.length + 1) / 2 - partitionX.
• Compare elements at partitionX and partitionY.
• Adjust start and end based on the comparison.
• Repeat steps 3-6 until start <= end.

Time & Space Complexity:

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

The optimized approach using binary search efficiently finds the median without merging the arrays.