LeetCode Problem #4: Median of Two Sorted Arrays - Explanation and Solutions in Python and JavaScript

Introduction

The Median of Two Sorted Arrays problem is a challenging algorithmic problem frequently asked in coding interviews. It tests your understanding of binary search, arrays, and divide-and-conquer techniques. In this post, we'll break down the problem, explain the optimal approach, and provide solutions in both Python and JavaScript.

Problem Statement

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

Example:

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

Approach

The problem can be solved efficiently using a **binary search** approach. Here's the step-by-step approach:

1. Ensure nums1 is the smaller array. If not, swap nums1 and nums2.
2. Perform a binary search on the smaller array (nums1) to find the partition point.
3. Calculate the partition point in nums2 such that the left half of the combined array contains half of the elements.
4. Check if the partition is correct (i.e., all elements on the left are smaller than all elements on the right).
5. If the partition is correct, calculate the median based on the maximum of the left half and the minimum of the right half.

Solution in Python

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

    m, n = len(nums1), len(nums2)
    left, right = 0, m

    while left <= right:
        partition1 = (left + right) // 2
        partition2 = (m + n + 1) // 2 - partition1

        max_left1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        min_right1 = float('inf') if partition1 == m else nums1[partition1]

        max_left2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        min_right2 = float('inf') if partition2 == n else nums2[partition2]

        if max_left1 <= min_right2 and max_left2 <= min_right1:
            if (m + n) % 2 == 0:
                return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
            else:
                return max(max_left1, max_left2)
        elif max_left1 > min_right2:
            right = partition1 - 1
        else:
            left = partition1 + 1
    return 0.0
        

Explanation: We perform a binary search on the smaller array to find the correct partition point. We then calculate the median based on the maximum of the left half and the minimum of the right half.

Solution in JavaScript

function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }

    const m = nums1.length;
    const n = nums2.length;
    let left = 0;
    let right = m;

    while (left <= right) {
        const partition1 = Math.floor((left + right) / 2);
        const partition2 = Math.floor((m + n + 1) / 2) - partition1;

        const maxLeft1 = partition1 === 0 ? -Infinity : nums1[partition1 - 1];
        const minRight1 = partition1 === m ? Infinity : nums1[partition1];

        const maxLeft2 = partition2 === 0 ? -Infinity : nums2[partition2 - 1];
        const minRight2 = partition2 === n ? Infinity : nums2[partition2];

        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((m + n) % 2 === 0) {
                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
            } else {
                return Math.max(maxLeft1, maxLeft2);
            }
        } else if (maxLeft1 > minRight2) {
            right = partition1 - 1;
        } else {
            left = partition1 + 1;
        }
    }
    return 0.0;
}
        

Explanation: Similar to the Python solution, we perform a binary search on the smaller array to find the correct partition point. We then calculate the median based on the maximum of the left half and the minimum of the right half.

Time and Space Complexity

Time Complexity: O(log(min(m, n))) - We perform a binary search on the smaller array.
Space Complexity: O(1) - We use a constant amount of extra space.

Edge Cases

• One of the arrays is empty.
• Both arrays have the same elements.
• The combined array has an even or odd number of elements.

Conclusion

The Median of Two Sorted Arrays problem is a great way to practice binary search and array manipulation. By understanding this approach, you can solve similar problems like finding the k-th smallest element in two sorted arrays. Try solving it on your own and explore related problems on LeetCode!