Leetcode Problem 4 Median of Two Sorted Arrays.txt

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0
Example 2:

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

The median is (2 + 3)/2 = 2.5

//Idea to solve this problem:
//Do a binary search on the first list and partition both the list so that there are equal elements on both the side of partition.
//Time complexity : O(log(m+n))


public class Solution 
{
    
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) 
    {   
        //Flip the nums so that the first list is smaller. We need to do this because we can do binary search on smaller list.
        if(nums1.Count() > nums2.Count())
        {
            return FindMedianSortedArrays(nums2,nums1);
        }
        
        int lenX = nums1.Count();
        int lenY = nums2.Count();
        
        int low = 0;
        int high = nums1.Count();
        
        
        //Binary search begins.
        while(low <= high)
        {
            int partitionX = (low+high)/2;
            int partitionY = (lenX + lenY + 1)/2 - partitionX;
            
            //We have to think about the edge case when there are no numbers left on either side of partition.
            //If there are no numbers on the left side of parition assign Math.MinValue
            //If there are no numbers on the right side of the partition assign Math.MaxValue
            int maxLeftX = partitionX == 0? int.MinValue : nums1[partitionX-1];
            int minRightX = partitionX == lenX? int.MaxValue: nums1[partitionX];
            
            int maxLeftY = partitionY == 0 ? int.MinValue : nums2[partitionY-1];
            int minRightY = partitionY == lenY? int.MaxValue : nums2[partitionY];
            
            //Console.WriteLine("PartitionX = "+ partitionX + " PartitionY = "+ partitionY);
            //Console.WriteLine("maxLeftX = "+ maxLeftX + " minRightX = "+ minRightX);
            //Console.WriteLine("maxLeftY = "+ maxLeftY + " minRightY = "+ minRightY);
            
            //If this condition is true then we have found four numbers within which the median lies.
            if(maxLeftX <= minRightY && maxLeftY <= minRightX)
            {
                if((lenX+lenY)% 2 == 0)
                    return ((Math.Max(maxLeftX,maxLeftY) + Math.Min(minRightX,minRightY))/2.0f);
                else
                    return Math.Max(maxLeftX,maxLeftY);
            }
            else if(maxLeftX > minRightY)
            {
                //Console.WriteLine("left x is greater than right y. Hence moving in left direction");
                high = partitionX-1;
            }
            else
            {
                //Console.WriteLine("left x is smaller than right y. Hence moving in right direction");
                low = partitionX+1;
            }
        }
        
        //This will happen when the given numbers are not in sorted order.
        return -1;
    }
}