Leetcode 4. Median of Two Sorted Arrays

 4. Median of Two Sorted Arrays

Hard

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

The overall run time complexity should be O(log (m+n)).

 

Example 1:

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

Example 2:

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

 

Constraints:

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

To solve this problem efficiently with the time complexity requirement of O(log(m+n)), we need to leverage a binary search approach.

Problem Overview:

• You are given two sorted arrays, nums1 and nums2.
• The task is to find the median of the combined sorted array without actually merging the arrays, as that would take O(m + n) time, which doesn't meet the time complexity requirement.
• The median is:
  • If the combined array length is odd, the median is the middle element.
  • If the combined array length is even, the median is the average of the two middle elements.

Approach:

We can solve this problem using binary search:

• We will binary search on the smaller of the two arrays (nums1 or nums2) to partition both arrays such that:
  • The left half contains the first half of the merged array.
  • The right half contains the second half of the merged array.
• The key observation is to balance the sizes of the two partitions (left and right).
• The median will be derived from the largest element in the left partition and the smallest element in the right partition.

Steps:

1. Partitioning the arrays: Partition the smaller array into two halves, and based on this, calculate the corresponding partition in the larger array.
2. Binary Search: Perform a binary search on the smaller array (nums1), and for each partition point i, determine the corresponding partition j in nums2.
3. Check the partition validity: Ensure that:
   • nums1[i-1] <= nums2[j] (The left part of nums1 is less than or equal to the right part of nums2)
   • nums2[j-1] <= nums1[i] (The left part of nums2 is less than or equal to the right part of nums1)
4. Compute the median:
   • If the total number of elements is odd, the median is the maximum of the left side.
   • If the total number of elements is even, the median is the average of the maximum of the left side and the minimum of the right side.

Code Implementation:

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

        int m = nums1.Length;
        int n = nums2.Length;
        int left = 0, right = m;
        
        while (left <= right) {
            int i = left + (right - left) / 2; // partition index for nums1
            int j = (m + n + 1) / 2 - i; // partition index for nums2

            // Check if partition is valid
            int maxLeft1 = (i == 0) ? int.MinValue : nums1[i - 1];
            int minRight1 = (i == m) ? int.MaxValue : nums1[i];
            int maxLeft2 = (j == 0) ? int.MinValue : nums2[j - 1];
            int minRight2 = (j == n) ? int.MaxValue : nums2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // Correct partitioning found
                if ((m + n) % 2 == 0) {
                    // Even total length: average of max of left and min of right
                    return (Math.Max(maxLeft1, maxLeft2) + Math.Min(minRight1, minRight2)) / 2.0;
                } else {
                    // Odd total length: max of left part
                    return Math.Max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                // We need to move the partition in nums1 to the left
                right = i - 1;
            } else {
                // We need to move the partition in nums1 to the right
                left = i + 1;
            }
        }

        // If no valid partition is found, return 0 (this shouldn't happen with valid input)
        return 0;
    }
}

Explanation of Code:

1. Initial Check for Array Sizes: We ensure that nums1 is the smaller array for efficiency. This allows us to perform binary search on the smaller array, reducing the number of elements we need to check.
2. Binary Search: We perform a binary search on the smaller array nums1. For each partition in nums1, we calculate the corresponding partition in nums2 to ensure the combined left part has as many elements as the right part.
3. Partition Validation: We check if the partition is valid:
   • The largest element of the left part of nums1 (maxLeft1) should be less than or equal to the smallest element of the right part of nums2 (minRight2), and vice versa for nums2 and nums1.
4. Median Calculation:
   • If the combined number of elements is even, the median is the average of the maximum of the left part and the minimum of the right part.
   • If the combined number of elements is odd, the median is the maximum of the left part.

Time Complexity:

• Binary Search: We perform binary search on the smaller array, so the time complexity is O(log(min(m, n))), where m and n are the lengths of the two arrays.

• Overall Time Complexity: Since we are only doing binary search on the smaller array, the time complexity is O(log(min(m, n))), which is efficient for this problem.

Example Walkthrough:

Example 1:

Input:

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

• The merged array is [1, 2, 3].
• The median is 2.

Output:

2.00000

Example 2:

Input:

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

• The merged array is [1, 2, 3, 4].
• The median is (2 + 3) / 2 = 2.5.

Output:

2.50000

This approach satisfies the problem's constraints and efficiently finds the median in O(log(min(m, n))) time.

For the problem "Median of Two Sorted Arrays," we can explore at least three different approaches to solving it, each with varying levels of time complexity and space complexity. Here's a breakdown of three different approaches:

---

1. Binary Search Approach (Optimal)

This is the optimal approach and follows the hint to use binary search on the smaller array. It achieves the required time complexity of O(log(min(m, n))).

Explanation:

• The idea is to partition both arrays into two halves.
• The left half of the combined array contains the same number of elements as the right half.
• Perform binary search on the smaller array, and for each partition in that array, calculate the corresponding partition in the larger array.
• After the partitioning, check whether the left and right parts of the arrays satisfy the conditions for being a valid median split.

Code:

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.Length > nums2.Length) {
            var temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

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

        while (left <= right) {
            int i = left + (right - left) / 2;
            int j = (m + n + 1) / 2 - i;

            int maxLeft1 = (i == 0) ? int.MinValue : nums1[i - 1];
            int minRight1 = (i == m) ? int.MaxValue : nums1[i];
            int maxLeft2 = (j == 0) ? int.MinValue : nums2[j - 1];
            int minRight2 = (j == n) ? int.MaxValue : nums2[j];

            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 = i - 1;
            } else {
                left = i + 1;
            }
        }

        return 0;
    }
}

Time Complexity:

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

---

2. Merge and Find Median (Brute Force)

In this approach, we merge the two sorted arrays into one and then find the median of the merged array. Although this approach is easy to implement, it doesn't meet the time complexity requirement of O(log(m + n)) and has a higher time complexity.

Explanation:

• Merge the two sorted arrays into a single sorted array.
• Once the arrays are merged, calculate the median.
• If the combined array length is even, the median is the average of the two middle elements.
• If the length is odd, the median is the middle element.

Code:

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.Length + nums2.Length];
        int i = 0, j = 0, k = 0;

        while (i < nums1.Length && j < nums2.Length) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }

        while (i < nums1.Length) {
            merged[k++] = nums1[i++];
        }

        while (j < nums2.Length) {
            merged[k++] = nums2[j++];
        }

        int mid = merged.Length / 2;
        if (merged.Length % 2 == 0) {
            return (merged[mid - 1] + merged[mid]) / 2.0;
        } else {
            return merged[mid];
        }
    }
}

Time Complexity:

• Time Complexity: O(m + n) (Merging both arrays)
• Space Complexity: O(m + n) (Space for the merged array)

---

3. Two Pointers Approach (Optimal for Merge)

This approach is similar to the merge step in the previous approach but avoids explicitly creating a new merged array. Instead, it uses two pointers to traverse through both arrays and find the median directly.

Explanation:

• Use two pointers, one for each array (nums1 and nums2).
• Traverse through both arrays simultaneously and keep track of the current merged index.
• Once you’ve traversed half of the total number of elements, compute the median based on the merged data at that point.

Code:

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.Length;
        int n = nums2.Length;
        int totalLen = m + n;

        int i = 0, j = 0;
        int prev = -1, current = -1;

        for (int count = 0; count <= totalLen / 2; count++) {
            prev = current;
            if (i < m && (j >= n || nums1[i] <= nums2[j])) {
                current = nums1[i++];
            } else {
                current = nums2[j++];
            }
        }

        if (totalLen % 2 == 0) {
            return (prev + current) / 2.0;
        } else {
            return current;
        }
    }
}

Time Complexity:

• Time Complexity: O(m + n) (Linear traversal through both arrays)
• Space Complexity: O(1) (Constant space usage)

---

Comparison of Approaches:

Approach	Time Complexity	Space Complexity	Pros	Cons
Binary Search Approach	O(log(min(m, n)))	O(1)	Optimal, efficient for large arrays	More complex to understand and implement
Merge and Find Median	O(m + n)	O(m + n)	Simple to understand and implement	Not optimal for large arrays
Two Pointers Approach	O(m + n)	O(1)	Simple, avoids extra space usage	Less efficient than binary search approach

---

Conclusion:

• The Binary Search Approach is the most efficient, meeting the time complexity requirement of O(log(min(m, n))).
• The Merge and Find Median Approach is the most intuitive but has a higher time complexity of O(m + n) and space complexity of O(m + n).
• The Two Pointers Approach is a good middle ground with a time complexity of O(m + n) but is more space efficient compared to the merge approach.

You can choose the approach based on the problem constraints and efficiency needs.