Median Of Two Sorted Arrays - Leetcode Solution

The problem "Median of Two Sorted Arrays" on LeetCode requires finding the median of two sorted arrays of equal or different length.

The median of a set of numbers is the middle number (or the average of the two middle numbers) in a sorted list of those numbers.

Approach:

The problem requires finding the median of two sorted arrays. There are several approaches to solve the problem. In this solution, we will use the binary search algorithm to find the median.

Steps:

1. Check if the length of the two arrays is equal. If it is not equal, then swap the arrays so that the first array is always the smaller one.

2. Use binary search to find the partition position of the two arrays such that the sum of the size of the left half of the partitions is equal to the sum of the size of the right half of the partitions.

3. If the total size of both arrays is even, then the median will be the average of the maximum of the left partition and the minimum of the right partition.

4. If the total size of both arrays is odd, then the median will be the maximum of the left partition.

Code:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    
    // Ensuring nums1 is always shorter or equal to nums2
    if(nums1.length > nums2.length) {
        int[] temp = nums1;
        nums1 = nums2;
        nums2 = temp;
    }
    
    int len1 = nums1.length;
    int len2 = nums2.length;
    int start = 0;
    int end = len1;
    
    while(start <= end) {
        int partitionX = (start + end)/2;
        int partitionY = (len1 + len2 + 1)/2 - partitionX;
        
        int maxLeftX = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX-1];
        int minRightX = partitionX == len1 ? Integer.MAX_VALUE : nums1[partitionX];
        
        int maxLeftY = partitionY == 0 ? Integer.MIN_VALUE : nums2[partitionY-1];
        int minRightY = partitionY == len2 ? Integer.MAX_VALUE : nums2[partitionY];
        
        if(maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if((len1 + len2) % 2 == 0) {
                return (double)(Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY))/2;
            }
            else {
                return (double)Math.max(maxLeftX, maxLeftY);   
            }
        }
        else if(maxLeftX > minRightY) {
            end = partitionX - 1;
        }
        else {
            start = partitionX + 1;
        }
    }
    
    return -1;
}

Time Complexity: O(log(min(m, n))) where m and n are the lengths of the two arrays.

1