LeetCode 4: Median of Two Sorted Arrays

LeetCode problem 4: Median of Two Sorted Arrays requires finding the median of two sorted arrays in O(log(m+n)) time complexity. This article will walk through the problem, analyze the approach, and provide a complete C# solution.

---

Problem Explanation

Given two sorted arrays, nums1 and nums2, find the median of the combined array. The solution must be efficient with a logarithmic time complexity.

---

What Is the Median?

The median is the middle value in a sorted list of numbers:

1. For an odd-length list, the median is the middle element.
2. For an even-length list, the median is the average of the two middle elements.

---

Example Walkthrough

Example 1:

Input:
nums1 = [1, 3]
nums2 = [2]

Output:
2.00000
Explanation:
Merged array: [1, 2, 3]. Median: 2.

---

Example 2:

Input:
nums1 = [1, 2]
nums2 = [3, 4]

Output:
2.50000
Explanation:
Merged array: [1, 2, 3, 4]. Median: (2 + 3) / 2 = 2.5.

---

Approach

To achieve O(log(m+n)) complexity, we can use binary search on the smaller array to partition the combined arrays. Here's the step-by-step approach:

1. Partition the Arrays

• Divide nums1 and nums2 into two halves such that all elements in the left half are less than or equal to those in the right half.

2. Use Binary Search

• Perform binary search on the smaller array (nums1 or nums2) to find the correct partition point.

3. Handle Odd and Even Cases

• If the combined length is odd, the median is the maximum of the left halves.
• If it's even, the median is the average of the maximum of the left halves and the minimum of the right halves.

---

C# Solution

Here’s the implementation:

using System;

public class Solution
{
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        // Ensure nums1 is the smaller array
        if (nums1.Length > nums2.Length)
        {
            return FindMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.Length;
        int n = nums2.Length;
        int totalLeft = (m + n + 1) / 2;

        int left = 0, right = m;

        while (left <= right)
        {
            int partition1 = (left + right) / 2;
            int partition2 = totalLeft - partition1;

            int maxLeft1 = (partition1 == 0) ? int.MinValue : nums1[partition1 - 1];
            int minRight1 = (partition1 == m) ? int.MaxValue : nums1[partition1];

            int maxLeft2 = (partition2 == 0) ? int.MinValue : nums2[partition2 - 1];
            int minRight2 = (partition2 == n) ? int.MaxValue : nums2[partition2];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
            {
                // Found the correct partition
                if ((m + n) % 2 == 0)
                {
                    return (Math.Max(maxLeft1, maxLeft2) + Math.Min(minRight1, minRight2)) / 2.0;
                }
                else
                {
                    return Math.Max(maxLeft1, maxLeft2);
                }
            }
            else if (maxLeft1 > minRight2)
            {
                // Move left
                right = partition1 - 1;
            }
            else
            {
                // Move right
                left = partition1 + 1;
            }
        }

        throw new ArgumentException("Input arrays are not valid.");
    }
}

---

How the Code Works

1. Ensure nums1 is the smaller array:

   • This minimizes the binary search range.

2. Binary Search to Find Partition:

   • Partition the smaller array and calculate the corresponding partition in the larger array.
   • Adjust the partition using binary search based on the comparisons of the left and right halves.

3. Calculate Median:

   • Use the maximum of the left halves and the minimum of the right halves to calculate the median.

---

Example Execution

Input:

int[] nums1 = { 1, 3 };
int[] nums2 = { 2 };

Execution:

1. Ensure nums1 is smaller.
2. Perform binary search to partition:
   • Partition 1: Left = [1], Right = [3]
   • Partition 2: Left = [2], Right = []
3. Median: max(1, 2) = 2.

Output:

2.00000

---

Complexity Analysis

• Time Complexity:
  O(log(min(m, n))) due to binary search.
• Space Complexity:
  O(1) as no extra space is used.

---

Comparison Table: Binary Search vs Brute Force

Approach	Time Complexity	Space Complexity	Notes
Binary Search	O(log(min(m,n)))	O(1)	Optimal for large arrays.
Merge and Find	O(m + n)	O(m + n)	Simpler but slower for large inputs.