Median of two sorted arrays


  • 0
    M

    Click here to see the full article post


  • 0
    G

    2 steps process.

    1. Merge 2 arrays to frame sorted array while merging ( a step of merge sort ) - O(m+n)
    2. find median ( 0(1) )
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        	int[] c = merge(nums1, nums2);
            print(c);
        	if (c.length % 2 == 0) {
        		System.out.println( c.length );
        		return (double) (c[ c.length/2 -1 ] + c[ (c.length / 2) ]) / 2;
        	} else {           
        		return (double) c[ c.length/2 ];
        	}
                    
        }
        
        
        
        public static int[] merge(int[] a, int[] b) {
        	int c[] = new int[a.length + b.length];
        	
        	int i = 0;
        	int j = 0;
        	int k = 0;
        	while ( i < a.length && j < b.length ) {
        		if( a[i] == b[j] ) {
        			c[k] = a[i]; k++; i++;
        			c[k] = b[j]; k++; j++;
        		}
        		else if( a[i] < b[j]) {
        			c[k] = a[i]; k++; i++;
        		}
        		else if( a[i] > b[j]) {
        			c[k] = b[j]; k++; j++;
        		}
        	}
        	
        	while(i<a.length) {
        		c[k] = a[i]; k++; i++;
        	}
        	
        	while (j<b.length) {
        		c[k] = b[j]; k++; j++;
        	}
        	    	
        	return c;
        }
    }
    

  • -1
    G

    Slower but self-explanatory:

    class Solution {
        static class DualSortedListIterator {
            int[] nums1, nums2;
            int idx1 = 0, idx2 = 0;
            
            DualSortedListIterator(int[] nums1, int[] nums2) {
                this.nums1 = nums1;
                this.nums2 = nums2;
            }
            
            int length() {
                return nums1.length + nums2.length;
            }
            
            boolean hasNext() {
                return idx1 < nums1.length || idx2 < nums2.length;    
            }
            
            Integer next() {
                Integer ans = null;
                if (hasNext()) {
                    boolean takeFromNums1 = (idx1 < nums1.length) && (idx2 >= nums2.length || nums1[idx1] <= nums2[idx2]);
                    ans = takeFromNums1 ? nums1[idx1++] : nums2[idx2++];
                }
                
                return ans;
            }
        }
        
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            DualSortedListIterator iter = new DualSortedListIterator(nums1, nums2);
            int midIdx = (iter.length() - 1)/2;
            boolean isEven = (iter.length() & 1) == 0;
            int midVal = 0;
            
            for (int i = 0; i <= midIdx; i++) {
                midVal = iter.next();
            }
            
            return isEven ? (midVal + iter.next()) / 2.0 : midVal;
        }
    }
    

  • -1
    S

    class Solution {
    public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int i = 0,j = 0,t;
    double n = (nums1.size()+nums2.size())/2.0,s=0,ss=0;
    for(int k=0;k<=floor(n);k++)
    {
    if(j == nums2.size())
    {
    t = nums1[i];
    i++;
    }
    else if(i == nums1.size()||nums1[i]>nums2[j])
    {
    t = nums2[j];
    j++;
    }
    else
    {
    t = nums1[i];
    i++;
    }
    if(k>=ceil(n-1))
    {
    s+=t;
    ss+=1.0;
    }
    }
    return s/ss;
    }
    };


  • -1
    Z

    //use merge method
    class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int num1=nums1.length;
    int num2=nums2.length;
    int index=(num1+num2)/2;
    boolean IsOdd=(num1+num2)%2==1;
    if(IsOdd)
    {
    return find(nums1,num1,nums2,num2,index);
    }
    else
    {
    return (find(nums1,num1,nums2,num2,index)+find(nums1,num1,nums2,num2,index-1))/2.0;
    }

    }
    private double find(int[] nums1,int num1,int [] nums2,int num2,int k)
    {
        int i=0;
        int j=0;
        boolean is1=false;
        boolean is2=false;
        int l=0;
        for(l=0;l<=k;l++)
        {
            if(i>=num1)
            {
                is2=true;
                j++;
            }
            else if(j>=num2)
            {
                is1=true;
                i++;
            }
            else if(nums1[i]<nums2[j])
            {
                is1=true;
                i++;
            }
            else
            {
                is2=true;
                j++;
            }
        }
        if(j-1<0)
        {
            return nums1[i-1];
        }
        if(i-1<0)
        {
            return nums2[j-1];
        }
        return Math.max(nums1[i-1],nums2[j-1]);
    }
    

    }


  • -1
    H

    from heapq import merge
    class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
    """
    :type nums1: List[int]
    nums2: List[int]
    :type nums3: List[int]
    rtype: float
    """
    num3=[]

        num3=list(merge(nums1, nums2))
        print(num3)
        if(len(num3)%2!=0):
            return num3[len(num3)/2]
        else:
            return (float)(num3[len(num3)//2]+num3[(len(num3)//2)-1])/2

  • 2
    P

    There are typos in the Java code that break the time complexity. iMax should be set to i - 1 instead of iMax - 1. Similarly, iMin should be set to i + 1 instead of iMin - 1.


  • -1
    I

    class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len1 = nums1.length;
    int len2 = nums2.length;
    int[] nums = new int[len1 + len2];
    int n = 0;
    for(int i=0,j=0;i<len1 || j<len2;) {
    if(i>=len1){
    nums[n++] = nums2[j++];
    }else if(j>=len2) {
    nums[n++] = nums1[i++];
    }else if(nums1[i] < nums2[j]){
    nums[n++] = nums1[i++];
    } else {
    nums[n++] = nums2[j++];
    }

    	}
    	
    	int x = (len1+len2)/2;
    	return (len1+len2)%2==0?
    			 new Double(nums[x-1]+nums[x])/2
    			:new Double(nums[x]) ;
    }
    

    }


  • -1
    S

    For the java solution, will it throw an exception if both arrays are empty?


  • -1
    T

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    double [] result = new double[m+n];
    int p = 0, q = 0, i = 0;
    while(p < m && q < n){
    if (nums1[p] <= nums2[q]){
    result[i++] = nums1[p++];
    }else{
    result[i++] = nums2[q++];
    }
    }
    while(p < m){
    result[i++] = nums1[p++];
    }
    while(q < n){
    result[i++] = nums2[q++];
    }

        if((m+n) % 2 == 0){
            return (result[(m+n)/2] + result[(m+n)/2 - 1])/2;
        }else{
            return result[(m+n)/2];
        }
    }

  • 0
    H

    I am surprised how many people are suggesting the naive O(m+n) solution.
    It seems that I have found another O(log(m+n)) solution (but I am not 100% sure it works but it passed the tests and intuitively I think it works)

    Explanation:
    2 basic ideas:

    • Intuitively, the median of the two arrays is always between the median of nums1 and nums2.
    • Adding or removing as many items above the medians as items below the median does not change the median.

    Algorithm:
    Calculate median of nums1 and nums2.
    If medianOfNums1 < medianOfNums2, and remove min((lengthOfNum1-1)/2,(lengthOfNum2-1)/2) items below medianOfNums1 in nums1 and the same number of items above the medianOfNums2 in nums2 and recursively rerun the function on the new arrays.
    If medianOfNums1 > medianOfNums2, same but invert nums1 and nums2
    If medianOfNums1 = medianOfNums2, it's your result (that's a most unlikely way to finish the test).

    Edge cases:
    When one array has 0 items, take the median of the second array
    When one of the array has 2 or less than 2 items, merge the two arrays using 1 or 2 dicotomy insert and calculate the median of this unique sorted array.

    Note:

    • Why removing (lengthOfNum-1)/2 items and not (lengthOfNum1)/2: because, you need to keep 1 item above and below the median. In the worst case senario, you need to save 2 items in case the median is between 2 items. You do not want to delete an item that might be required to calculate a median that is a mean. (This is were the intuition is going really far and I cannot explain exactly why it works). That's why the edge cases are length = 1 or 2.
    • Why dichotomy insert: in most of the cases, if the two arrays had the same size, dichotomy insert is not required as your edge case will be 2 1 or 2 items arrays. But if you have 1 array of m items and 1 array of 1 item, naive insert will take you O(m) and you will have done all of this for nothing.

    If you find a flaw in my process, I'd be really happy if you could tell me so I can find where my logic was wrong.

    Code (Javascript):
    /**

    • @param {number[]} nums1
    • @param {number[]} nums2
    • @return {number}
      */

    var findMedianOfOneArray = function(nums) {
    return (nums.length % 2 == 1) ? nums[(nums.length-1)/2] : (nums[nums.length/2-1]+nums[nums.length/2])/2
    }

    var dicotomyInsert = function (a,nums) {
    if (nums.length == 1) {
    return (a < nums[0]) ? [a,nums[0]] : [nums[0],a]
    }
    var middle = Math.floor(nums.length-1/2)
    if (a < nums[middle]) {
    return dicotomyInsert(a,nums.slice(0,middle)).concat(nums.slice(middle,nums.length))
    } else {
    return nums.slice(0,middle).concat(dicotomyInsert(a,nums.slice(middle,nums.length)))
    }
    }

    var findMedianSortedArrays = function(nums1, nums2) {
    if (nums1.length == 0) {
    return findMedianOfOneArray(nums2)
    }
    if (nums2.length == 0) {
    return findMedianOfOneArray(nums1)
    }
    if (nums1.length == 1) {
    return findMedianOfOneArray(dicotomyInsert(nums1[0],nums2))
    }
    if (nums2.length == 1) {
    return findMedianOfOneArray(dicotomyInsert(nums2[0],nums1))
    }
    if (nums1.length == 2) {
    return findMedianOfOneArray(dicotomyInsert(nums1[1],dicotomyInsert(nums1[0],nums2)))
    }
    if (nums2.length == 2) {
    return findMedianOfOneArray(dicotomyInsert(nums2[1],dicotomyInsert(nums2[0],nums1)))
    }
    var median1 = findMedianOfOneArray(nums1)
    var median2 = findMedianOfOneArray(nums2)
    var numberOfItemsToSlice = (nums1.length <= nums2.length) ? Math.floor((nums1.length-1)/2) : Math.floor((nums2.length-1)/2)
    if (median1 < median2) {
    return findMedianSortedArrays(nums1.slice(numberOfItemsToSlice,nums1.length),nums2.slice(0,nums2.length-numberOfItemsToSlice))
    } else if (median1 > median2) {
    return findMedianSortedArrays(nums2.slice(numberOfItemsToSlice,nums2.length),nums1.slice(0,nums1.length-numberOfItemsToSlice))
    } else {
    return median1
    }
    }


  • 0
    B

    If you're only incrementing / decrementing by 1 each iteration how is that a log runtime solution? How is the searching range reduced by half each loop? Am I misunderstanding something?


  • 0
    H

    Hello, I am not decrementing by 1 each iteration, I am decrementing by (min(n,m)-1)/2 at each iteration.
    "numberOfItemsToSlice = (nums1.length <= nums2.length) ? Math.floor((nums1.length-1)/2) : Math.floor((nums2.length-1)/2)"
    Basically, I remove (almost) half of the smallest array (and as many items in the longest array) every loop as long as the smallest array is bigger than 2 items. Then I merge it into the biggest array.

    If n < m:
    each turn I remove (n-1)/2 items in each array (and n is decreased but m is still above m). So I will shrink my n-array into a 2-array in O(log(n))
    Then I insert the 1 or 2 reaming items into the "m"-array which is at worst m-size which cost at worst O(log(m))
    So in the worst case (really specific when the 2 sizes are really different), it costs O(log(max(n,m)) which is still less than O(log(m+n))


  • 1
    B

    @horo I'm referring to the solution in the article, not to your solution. Sorry if I wasn't clear. In the article it has the following snippit:

    while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = iMin + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = iMax - 1; // i is too big
            }
    

    I'm referring to the fact that it only does iMin+ 1 / iMax - 1. Even if (iMin+iMax) is divided by 2 it only moves 1 at a time.


  • 0
    S

    M= 1000000
    Let A[1, 3, 5,7] , B [M+1, M+6,M+9, M+20],
    left half A+B = [1,3, M+1, M+6]
    right half A+B = [5,7,M+9,M+20]
    with the solution, outcome = (5+(M+6))/2= 0.5M+5.5
    but the M of the 2 array is( 7+(M+1))/2 = 0.5M+4
    ????????


  • -1
    D

    why this question has a label of hard ?


  • 0
    S

    @Nijat666
    Runtime needs to be O(log (m+n))
    It's easy to solve the problem itself, but come up with a solution that meets the runtime requirement is somehow not that easy


  • 0
    G

    @horo, I think your method should work. It's actually the same solution I was working on myself when I saw your comment.


  • 0
    G

    A few other thoughts on your solution, @horo, as I am working through the c# implementation:

    1. There is no need to insert the one item array at the end into the other. Once you're at that point, you can find the median of the big array, and then shift it by one left or right, based on whether the one value left in the small array is smaller or bigger than it, respectively.
      e.g. num1 = [1] and num2 = [5, 7, 10, 13]. You can figure out that the median of num2 would normally be 7 and 10 averaged together, but because 1 is less than that average, you just shift your median one to the left to the 7 and that's your answer.
    2. You can eliminate all the min calls by just ensuring at the beginning that num1 is the smaller array and num2 is the bigger. Swap them around if they're not and from there on out the small array will stay the smaller (Because you're slicing off the same number of items from each).

  • 0
    R

    @songsongsong666
    Actually, left_part will be A itself under the conditions you give.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.