4. Median of Two Sorted Arrays - Leetcode

Median of Two Sorted Arrays in C#

Finding the median of two sorted arrays is a classic problem in computer science and coding interviews. The problem asks you to find the median of two sorted arrays of size m and n respectively, with a time complexity requirement of O(log(m + n)).

Problem Statement:

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

Example:

  • Example 1:

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

  • Example 2:

    Input: nums1 = [1, 2], nums2 = [3, 4]
    Output: 2.50000
    Explanation: Merged array = [1, 2, 3, 4] and the median is (2 + 3) / 2 = 2.5.


Solution 1: Brute Force Approach

In the brute force approach, we merge both sorted arrays into a single sorted array and then find the median. This approach is simple and easy to implement but is not efficient in terms of time complexity.

C# Code:

public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
    var merged = nums1.Concat(nums2).OrderBy(x => x).ToArray();  // Merge and sort
    int length = merged.Length;
    
    if (length % 2 == 0)  // If even, take the average of the two middle elements
    {
        return (merged[length / 2 - 1] + merged[length / 2]) / 2.0;
    }
    else  // If odd, return the middle element
    {
        return merged[length / 2];
    }
}

Explanation:

  1. Merging the Arrays:
    We use the Concat() method to combine the two arrays (nums1 and nums2) into one array. Then, we apply the OrderBy() method to sort the merged array in ascending order. This step ensures that the two arrays are combined and sorted, preparing them for median calculation.

  2. Finding the Median:
    The length of the merged array is stored in the length variable. We then check if the length is even or odd:

    • If even, the median is the average of the two middle elements. This is done by accessing the two middle elements (merged[length / 2 - 1] and merged[length / 2]) and calculating their average.
    • If odd, the median is simply the middle element of the array, which is located at merged[length / 2].
  3. Return the Result:
    Finally, we return the computed median value.

Time Complexity:

  • Merging both arrays takes O(m + n) time.
  • Sorting the merged array takes O((m + n) log(m + n)) time.
  • Finding the median takes O(1) time.

Thus, the overall time complexity of the brute force approach is O((m + n) log(m + n)).


Solution 2: Optimal Approach Using Binary Search (O(log(min(m, n))))

The optimal solution leverages binary search on the smaller array. By partitioning both arrays into two halves and ensuring that elements on the left are less than or equal to those on the right, we can find the median in O(log(min(m, n))) time.

C# Code:

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

    int m = nums1.Length;
    int n = nums2.Length;
    int left = 0, right = m;

    while (left <= right)
    {
        int partition1 = (left + right) / 2;
        int partition2 = (m + n + 1) / 2 - 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)
        {
            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)
        {
            right = partition1 - 1;
        }
        else
        {
            left = partition1 + 1;
        }
    }

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

Explanation:

  1. Array Reordering: To make sure that we perform binary search on the smaller array (for better efficiency), we check if nums1 is larger than nums2. If it is, we swap them. This step ensures that nums1 is the smaller array, minimizing the number of iterations for binary search.

  2. Binary Search Setup: We initialize left as 0 and right as the length of nums1. The goal is to find the correct partition of the two arrays such that the left side has the same number of elements (or one more element if the total length is odd) as the right side.

  3. Partitioning: We calculate the partition points for both arrays (partition1 for nums1 and partition2 for nums2). These partitions split the arrays into left and right parts. We then check if the maximum element of the left part (maxLeft1 and maxLeft2) is less than or equal to the minimum element of the right part (minRight1 and minRight2). If this condition holds, we've found the correct partition.

  4. Median Calculation: If the combined length of both arrays is even, the median is the average of the two middle elements, which are the maximum values from the left parts and the minimum values from the right parts. If the combined length is odd, the median is the maximum value from the left parts, as the left part will have one more element than the right part.

  5. Adjusting the Partition: If the partition is not correct, we adjust the binary search range by moving left or right depending on whether maxLeft1 is greater than minRight2 or maxLeft2 is greater than minRight1.

Time Complexity:

  • The binary search in the smaller array takes O(log(min(m, n))) time.
  • The comparison operations and calculations within the binary search loop take O(1) time.

Thus, the overall time complexity of the optimal approach is O(log(min(m, n))).


Conclusion

  • The Brute Force Solution is straightforward but inefficient with a time complexity of O((m + n) log(m + n)).
  • The Optimal Solution uses binary search and partitions the arrays efficiently, achieving a time complexity of O(log(min(m, n))). This is the preferred method for large arrays.

By understanding both solutions, you can choose the approach that best fits the problem constraints and performance requirements.


Featured Posts

3. Longest Substring Without Repeating Characters - Leetcode

Longest Substring Without Repeating Characters Difficulty: Medium Problem Statement: Given a string s , find the length of the longest ...

Popular Posts