Median of Two Sorted Arrays | Leetcode 4

Finding the median of two sorted arrays is a classic problem in computer science and competitive programming. It is particularly interesting due to its constraints, which encourage an efficient solution rather than a simple brute-force approach. In this article, we’ll cover different methods to solve this problem, including their pros and cons, and provide Java code for each solution.

Problem Statement

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

Approach 1: Merge and Find the Median

This approach is based on merging the two sorted arrays into one and then finding the median. It is straightforward but not optimal in terms of time complexity.

Steps:

1. Merge nums1 and nums2 into a single sorted array.
2. Find the median of the merged array.
3. If the merged array length is odd, the median is the middle element.
4. If the merged array length is even, the median is the average of the two middle elements.

Java Code:

import java.util.Arrays;

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        System.arraycopy(nums1, 0, merged, 0, nums1.length);
        System.arraycopy(nums2, 0, merged, nums1.length, nums2.length);
        Arrays.sort(merged);
        
        int n = merged.length;
        if (n % 2 == 0) {
            return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
        } else {
            return merged[n / 2];
        }
    }
}

Time Complexity:

• Time:O((m+n) log (m+n)) due to the sorting step.
• Space:O(m+n) for storing the merged array

Analysis:

While this approach is simple, it does not meet the optimal time complexity requirement of O(log (m+n)). It is suitable for smaller input sizes but inefficient for large arrays.

Approach 2: Two-Pointer Merge (Without Sorting)

To optimize the merging step, we can use the two-pointer technique to merge the arrays directly while keeping track of the median.

Steps:

1. Use two pointers to traverse nums1 and nums2.
2. Merge them until we reach the middle point of the combined array.
3. If the total length is odd, the median is the middle element.
4. If the total length is even, the median is the average of the two middle elements.

Java Code:

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int totalLength = m + n;
        int medianPos1 = (totalLength - 1) / 2;
        int medianPos2 = totalLength / 2;
        
        int i = 0, j = 0, current = 0, prev = 0;
        for (int k = 0; k <= medianPos2; k++) {
            prev = current;
            if (i < m && (j >= n || nums1[i] <= nums2[j])) {
                current = nums1[i++];
            } else {
                current = nums2[j++];
            }
        }
        
        if (totalLength % 2 == 0) {
            return (prev + current) / 2.0;
        } else {
            return current;
        }
    }
}

Time Complexity:

• Time: O(m + n) for merging.
• Space: O(1) if we don’t count the input arrays.

Analysis:

This method is more efficient than the sorting approach but still not optimal for large arrays, as it requires traversing both arrays entirely.

Approach 3: Binary Search (Optimal)

This approach uses binary search and achieves the desired O(log (m+n)) time complexity by partitioning the two arrays. The idea is to find a partition that divides both arrays such that the left side has all smaller elements and the right side has all larger elements.

Steps:

1. Ensure nums1 is the smaller array to minimize iterations.
2. Set two pointers left and right for binary search on nums1.
3. Calculate the partition positions for nums1 and nums2.
4. Check if the partitions are valid:
   • maxLeft1 <= minRight2 and maxLeft2 <= minRight1.
5. If valid, compute the median.
6. If not valid, adjust the binary search range and repeat.

Java Code:

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        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) ? Integer.MIN_VALUE : nums1[partition1 - 1];
            int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
            
            int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
            int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : 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 IllegalArgumentException("Input arrays are not sorted");
    }
}

Time Complexity:

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

Analysis:

This is the optimal solution for finding the median of two sorted arrays. It efficiently uses binary search to minimize comparisons and achieves the required time complexity, making it suitable for large datasets.

Conclusion

Finding the median of two sorted arrays can be approached in various ways depending on the input size and complexity constraints. For smaller arrays, simple merging works fine, while the binary search approach is the optimal choice for larger inputs due to its logarithmic time complexity. By understanding these approaches, you can choose the right solution based on the problem’s requirements.

Happy coding!