Massive Algorithms: LeetCode 4 - Median of two sorted arrays

LeetCode 4 - Median of two sorted arrays

LeetCode-Median of Two Sorted Array
Median of two sorted arrays - geeksforgeeks

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)).

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

X. Iterative version
https://discuss.leetcode.com/topic/4996/share-my-o-log-min-m-n-solution-with-explanation

log(min(m,n)
https://discuss.leetcode.com/topic/3367/share-my-iterative-solution-with-o-log-min-n-m

This is my iterative solution using binary search. The main idea is to find the approximate location of the median and compare the elements around it to get the final result.

do binary search. suppose the shorter list is A with length n. the runtime is O(log(n)) which means no matter how large B array is, it only depends on the size of A. It makes sense because if A has only one element while B has 100 elements, the median must be one of A[0], B[49], and B[50] without check everything else. If A[0] <= B[49], B[49] is the answer; if B[49] < A[0] <= B[50], A[0] is the answer; else, B[50] is the answer.
After binary search, we get the approximate location of median. Now we just need to compare at most 4 elements to find the answer. This step is O(1).
the same solution can be applied to find kth element of 2 sorted arrays.

    public double findMedianSortedArrays(int A[], int B[]) {
    int n = A.length;
    int m = B.length;
    // the following call is to make sure len(A) <= len(B).
    // yes, it calls itself, but at most once, shouldn't be
    // consider a recursive solution
    if (n > m)
        return findMedianSortedArrays(B, A);

    // now, do binary search
    int k = (n + m - 1) / 2;
    int l = 0, r = Math.min(k, n); // r is n, NOT n-1, this is important!!
    while (l < r) {
        int midA = (l + r) / 2;
        int midB = k - midA;
        if (A[midA] < B[midB])
            l = midA + 1;
        else
            r = midA;
    }
    
    // after binary search, we almost get the median because it must be between
    // these 4 numbers: A[l-1], A[l], B[k-l], and B[k-l+1] 

    // if (n+m) is odd, the median is the larger one between A[l-1] and B[k-l].
    // and there are some corner cases we need to take care of.
    int a = Math.max(l > 0 ? A[l - 1] : Integer.MIN_VALUE, k - l >= 0 ? B[k - l] : Integer.MIN_VALUE);
    if (((n + m) & 1) == 1)
        return (double) a;

    // if (n+m) is even, the median can be calculated by 
    //      median = (max(A[l-1], B[k-l]) + min(A[l], B[k-l+1]) / 2.0
    // also, there are some corner cases to take care of.
    int b = Math.min(l < n ? A[l] : Integer.MAX_VALUE, k - l + 1 < m ? B[k - l + 1] : Integer.MAX_VALUE);
    return (a + b) / 2.0;
}

https://discuss.leetcode.com/topic/16797/very-concise-o-log-min-m-n-iterative-solution-with-detailed-explanation

This problem is notoriously hard to implement due to all the corner cases. Most implementations consider odd-lengthed and even-lengthed arrays as two different cases and treat them separately. As a matter of fact, with a little mind twist. These two cases can be combined as one, leading to a very simple solution where (almost) no special treatment is needed.

First, let's see the concept of 'MEDIAN' in a slightly unconventional way. That is:

"if we cut the sorted array to two halves of EQUAL LENGTHS, then
median is the AVERAGE OF Max(lower_half) and Min(upper_half), i.e. the
two numbers immediately next to the cut".

For example, for [2 3 5 7], we make the cut between 3 and 5:

[2 3 / 5 7]

then the median = (3+5)/2. Note that I'll use '/' to represent a cut, and (number / number) to represent a cut made through a number in this article.

for [2 3 4 5 6], we make the cut right through 4 like this:

[2 3 (4/4) 5 7]

Since we split 4 into two halves, we say now both the lower and upper subarray contain 4. This notion also leads to the correct answer: (4 + 4) / 2 = 4;

For convenience, let's use L to represent the number immediately left to the cut, and R the right counterpart. In [2 3 5 7], for instance, we have L = 3 and R = 5, respectively.

We observe the index of L and R have the following relationship with the length of the array N:

N        Index of L / R
1               0 / 0
2               0 / 1
3               1 / 1  
4               1 / 2      
5               2 / 2
6               2 / 3
7               3 / 3
8               3 / 4

It is not hard to conclude that index of L = (N-1)/2, and R is at N/2. Thus, the median can be represented as

(L + R)/2 = (A[(N-1)/2] + A[N/2])/2

To get ready for the two array situation, let's add a few imaginary 'positions' (represented as #'s) in between numbers, and treat numbers as 'positions' as well.

[6 9 13 18]  ->   [# 6 # 9 # 13 # 18 #]    (N = 4)
position index     0 1 2 3 4 5  6 7  8     (N_Position = 9)
    
[6 9 11 13 18]->   [# 6 # 9 # 11 # 13 # 18 #]   (N = 5)
position index      0 1 2 3 4 5  6 7  8 9 10    (N_Position = 11)

As you can see, there are always exactly 2*N+1 'positions' regardless of length N. Therefore, the middle cut should always be made on the Nth position (0-based). Since index(L) = (N-1)/2 and index(R) = N/2 in this situation, we can infer that index(L) = (CutPosition-1)/2, index(R) = (CutPosition)/2.

Now for the two-array case:

A1: [# 1 # 2 # 3 # 4 # 5 #]    (N1 = 5, N1_positions = 11)

A2: [# 1 # 1 # 1 # 1 #]     (N2 = 4, N2_positions = 9)

Similar to the one-array problem, we need to find a cut that divides the two arrays each into two halves such that

"any number in the two left halves" <= "any number in the two right
halves".

We can also make the following observations：

There are 2N1 + 2N2 + 2 position altogether. Therefore, there must be exactly N1 + N2 positions on each side of the cut, and 2 positions directly on the cut.
Therefore, when we cut at position C2 = K in A2, then the cut position in A1 must be C1 = N1 + N2 - k. For instance, if C2 = 2, then we must have C1 = 4 + 5 - C2 = 7.
```
 [# 1 # 2 # 3 # (4/4) # 5 #]    

 [# 1 / 1 # 1 # 1 #]   
```

When the cuts are made, we'd have two L's and two R's. They are

 L1 = A1[(C1-1)/2]; R1 = A1[C1/2];
 L2 = A2[(C2-1)/2]; R2 = A2[C2/2];

In the above example,

    L1 = A1[(7-1)/2] = A1[3] = 4; R1 = A1[7/2] = A1[3] = 4;
    L2 = A2[(2-1)/2] = A2[0] = 1; R2 = A1[2/2] = A1[1] = 1;

Now how do we decide if this cut is the cut we want? Because L1, L2 are the greatest numbers on the left halves and R1, R2 are the smallest numbers on the right, we only need

L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2

to make sure that any number in lower halves <= any number in upper halves. As a matter of fact, since
L1 <= R1 and L2 <= R2 are naturally guaranteed because A1 and A2 are sorted, we only need to make sure:

L1 <= R2 and L2 <= R1.

Now we can use simple binary search to find out the result.

If we have L1 > R1, it means there are too many large numbers on the left half of A1, then we must move C1 to the left (i.e. move C2 to the right); 
If L2 > R1, then there are too many large numbers on the left half of A2, and we must move C2 to the left.
Otherwise, this cut is the right one. 
After we find the cut, the medium can be computed as (max(L1, L2) + min(R1, R2)) / 2;

Two side notes:

A. since C1 and C2 can be mutually determined from each other, we might as well select the shorter array (say A2) and only move C2 around, and calculate C1 accordingly. That way we can achieve a run-time complexity of O(log(min(N1, N2)))

B. The only edge case is when a cut falls on the 0th(first) or the 2Nth(last) position. For instance, if C2 = 2N2, then R2 = A2[2*N2/2] = A2[N2], which exceeds the boundary of the array. To solve this problem, we can imagine that both A1 and A2 actually have two extra elements, INT_MAX at A[-1] and INT_MAX at A[N]. These additions don't change the result, but make the implementation easier: If any L falls out of the left boundary of the array, then L = INT_MIN, and if any R falls out of the right boundary, then R = INT_MAX.

Very concise O(log(min(M,N))) iterative solution with detailed explanation

 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int N1 = nums1.size();
    int N2 = nums2.size();
    if (N1 < N2) return findMedianSortedArrays(nums2, nums1); // Make sure A2 is the shorter one.
    
    if (N2 == 0) return ((double)nums1[(N1-1)/2] + (double)nums1[N1/2])/2;  // If A2 is empty
    
    int lo = 0, hi = N2 * 2;
    while (lo <= hi) {
        int mid2 = (lo + hi) / 2;   // Try Cut 2 
        int mid1 = N1 + N2 - mid2;  // Calculate Cut 1 accordingly
        
        double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2]; // Get L1, R1, L2, R2 respectively
        double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
        double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
        double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];
        
        if (L1 > R2) lo = mid2 + 1;  // A1's lower half is too big; need to move C1 left (C2 right)
        else if (L2 > R1) hi = mid2 - 1; // A2's lower half too big; need to move C2 left.
        else return (max(L1,L2) + min(R1, R2)) / 2; // Otherwise, that's the right cut.
    }
    return -1;
}

该方法的核心是将原问题转变成一个寻找第k小数的问题（假设两个原序列升序排列），这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题，原问题也得以解决。首先假设数组A和B的元素个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况：>、<和=。如果A[k/2-1]<B[k/2-1]，这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
X. log(m+n)
https://discuss.leetcode.com/topic/28602/concise-java-solution-based-on-binary-search

The key point of this problem is to ignore half part of A and B each step recursively by comparing the median of remaining A and B:

if (aMid < bMid) Keep [aRight + bLeft]    
else Keep [bRight + aLeft]

As the following: time=O(log(m + n))

public double findMedianSortedArrays(int[] A, int[] B) {
     int m = A.length, n = B.length;
     int l = (m + n + 1) / 2;
     int r = (m + n + 2) / 2;
     return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
 }

public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
 if (aStart > A.length - 1) return B[bStart + k - 1];            
 if (bStart > B.length - 1) return A[aStart + k - 1];                
 if (k == 1) return Math.min(A[aStart], B[bStart]);
 
 int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
 if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; 
 if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];        
 
 if (aMid < bMid) 
     return getkth(A, aStart + k/2, B, bStart,       k - k/2);// Check: aRight + bLeft 
 else 
     return getkth(A, aStart,       B, bStart + k/2, k - k/2);// Check: bRight + aLeft
}

https://discuss.leetcode.com/topic/2778/share-my-simple-o-log-m-n-solution-for-your-reference

Binary search. Call 2 times getkth and k is about half of (m + n). Every time call getkth can reduce the scale k to its half. So the time complexity is log(m + n).

    int getkth(int s[], int m, int l[], int n, int k){
        // let m <= n
        if (m > n) 
            return getkth(l, n, s, m, k);
        if (m == 0)
            return l[k - 1];
        if (k == 1)
            return min(s[0], l[0]);

        int i = min(m, k / 2), j = min(n, k / 2);
        if (s[i - 1] > l[j - 1])
            return getkth(s, m, l + j, n - j, k - j);
        else
            return getkth(s + i, m - i, l, n, k - i);
        return 0;
    }
    
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int l = (m + n + 1) >> 1;
        int r = (m + n + 2) >> 1;
        return (getkth(A, m ,B, n, l) + getkth(A, m, B, n, r)) / 2.0;
    }

https://discuss.leetcode.com/topic/28602/concise-java-solution-based-on-binary-search
Java code:

public static double findMedianSortedArrays(int A[], int B[]) {
 int m = A.length;
 int n = B.length;
 
 if ((m + n) % 2 != 0) // odd
  return (double) findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1);
 else { // even
  return (findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1) 
   + findKth(A, B, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
 }
}
 
public static int findKth(int A[], int B[], int k, 
 int aStart, int aEnd, int bStart, int bEnd) {
 
 int aLen = aEnd - aStart + 1;
 int bLen = bEnd - bStart + 1;
 
 // Handle special cases
 if (aLen == 0)
  return B[bStart + k];
 if (bLen == 0)
  return A[aStart + k];
 if (k == 0)
  return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
 
 int aMid = aLen * k / (aLen + bLen); // a's middle count
 int bMid = k - aMid - 1; // b's middle count
 
 // make aMid and bMid to be array index
 aMid = aMid + aStart;
 bMid = bMid + bStart;
 
 if (A[aMid] > B[bMid]) {
  k = k - (bMid - bStart + 1);
  aEnd = aMid;
  bStart = bMid + 1;
 } else {
  k = k - (aMid - aStart + 1);
  bEnd = bMid;
  aStart = aMid + 1;
 }
 
 return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}

http://www.jiuzhang.com/solutions/median-of-two-sorted-arrays/

    public double findMedianSortedArrays(int A[], int B[]) {
        int len = A.length + B.length;
        if (len % 2 == 1) {
            return findKth(A, 0, B, 0, len / 2 + 1);
        }
        return (
            findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)
        ) / 2.0;
    }

    // find kth number of two sorted array
    public static int findKth(int[] A, int A_start,
                              int[] B, int B_start,
                              int k){  
  if (A_start >= A.length) {
   return B[B_start + k - 1];
  }
  if (B_start >= B.length) {
   return A[A_start + k - 1];
  }

  if (k == 1) {
   return Math.min(A[A_start], B[B_start]);
  }
  
  int A_key = A_start + k / 2 - 1 < A.length
              ? A[A_start + k / 2 - 1]
              : Integer.MAX_VALUE;
  int B_key = B_start + k / 2 - 1 < B.length
              ? B[B_start + k / 2 - 1]
              : Integer.MAX_VALUE; 
  
  if (A_key < B_key) {
   return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
  } else {
   return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
  }
 }
}

http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
O(n)的解法比较直观，直接merge两个数组，然后求中间值。而对于O(log(m+n))显然是用二分搜索了，相当于“Kth element in 2 sorted array”的变形。如果(m+n)为奇数，那么找到“(m+n)/2+1 th element in 2 sorted array”即可。如果（m+n）为偶数，需要找到(m+n)/2 th 及(m+n)/2+1 th，然后求平均。

而对于“Kth element in 2 sorted array”，如下图，两个中位数 A[m/2] 和 B[n/2]，可以将数组划分为四个部分。而丢弃哪一个部分取决于两个条件：1， (m/2 + n/2)?k；2，A[m/2] ? B[n/2];

如果 (m/2 + n/2) > k，那么意味着，当前中位数取高了，正确的中位数要么在 Section 1或者Section3中。如果A[m/2] > B[n/2], 意味着中位数肯定不可能在Section 2里面，那么新的搜索可以丢弃这个区间段了。同理可以推断出余下三种情况，如下所示：

If (m/2+n/2+1) > k && am/2 > bn/2 , drop Section 2

If (m/2+n/2+1) > k && am/2 < bn/2 , drop Section 4

If (m/2+n/2+1) < k && am/2 > bn/2 , drop Section 3

If (m/2+n/2+1) < k && am/2 < bn/2 , drop Section 1

1:    double findMedianSortedArrays(int A[], int m, int B[], int n) {  
2:      if((n+m)%2 ==0)  
3:      {  
4:        return (GetMedian(A,m,B,n, (m+n)/2) + GetMedian(A,m,B,n, (m+n)/2+1))/2.0;  
5:      }  
6:      else  
7:        return GetMedian(A,m,B,n, (m+n)/2+1);        
8:    }  
9:       int GetMedian(int a[], int n, int b[], int m, int k)  
10:       {  
11:            assert(a && b);   
12:            if (n <= 0) return b[k-1];  
13:            if (m <= 0) return a[k-1];  
14:            if (k <= 1) return min(a[0], b[0]);   
15:            if (b[m/2] >= a[n/2])  
16:            {  
17:                 if ((n/2 + 1 + m/2) >= k)  
18:                      return GetMedian(a, n, b, m/2, k);  
19:                 else  
20:                      return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1));  
21:            }  
22:            else  
23:            {  
24:                 if ((m/2 + 1 + n/2) >= k)  
25:                      return GetMedian( a, n/2,b, m, k);  
26:                 else  
27:                      return GetMedian( a, n, b + m/2 + 1, m - (m/2 + 1),k - (m/2 + 1));  
28:            }  
29:       }

http://www.lifeincode.net/programming/leetcode-median-of-two-sorted-arrays-java/

If the length of an array is smaller or equal than zero, we know that we can directly get the K th element from the other array.

And If K = 1, we can just compare the first element and decide which one is the answer.

One thing needs to mention is that the comparison of k and the length of A_1 and B_1. We not only throws the half part of an array, we also throws the mid element out. So we will compare k with n / 2 + m / 2 + 1. And we throws half of the element like k – n / 2 – 1 or k – m / 2 – 1, in which “1” denoting the mid element. We are doing this because it can make sure that every time we will throw at least one element, otherwise sometimes it is possible that the solution is not able to stop.

public class Solution {

    public double findMedianSortedArrays(int A[], int B[]) {

        int lengthA = A.length;

        int lengthB = B.length;

        if ((lengthA + lengthB) % 2 == 0) {

            double r1 = (double) findMedianSortedArrays(A, 0, lengthA, B, 0, lengthB, (lengthA + lengthB) / 2);

            double r2 = (double) findMedianSortedArrays(A, 0, lengthA, B, 0, lengthB, (lengthA + lengthB) / 2 + 1);

            return (r1 + r2) / 2;

        } else

            return findMedianSortedArrays(A, 0, lengthA, B, 0, lengthB, (lengthA + lengthB + 1) / 2);

    }

    public int findMedianSortedArrays(int A[], int startA, int endA, int B[], int startB, int endB, int k) {

        int n = endA - startA;

        int m = endB - startB;

        if (n <= 0)

            return B[startB + k - 1];

        if (m <= 0)

            return A[startA + k - 1];

        if (k == 1)

            return A[startA] < B[startB] ? A[startA] : B[startB];

        int midA = (startA + endA) / 2;

        int midB = (startB + endB) / 2;

        if (A[midA] <= B[midB]) {

            if (n / 2 + m / 2 + 1 >= k)

                return findMedianSortedArrays(A, startA, endA, B, startB, midB, k);

            else

                return findMedianSortedArrays(A, midA + 1, endA, B, startB, endB, k - n / 2 - 1);

        } else {

            if (n / 2 + m / 2 + 1 >= k)

                return findMedianSortedArrays(A, startA, midA, B, startB, endB, k);

            else

                return findMedianSortedArrays(A, startA, endA, B, midB + 1, endB, k - m / 2 - 1);

        }

    }

}

Median of two sorted arrays of different sizes

O(m+n)

double findMedianSortedArrays(int A[], int m, int B[], int n)

02{

03    int i=0, j=0, median = m+n;

04    double prev=0, last=0;

05

06    if(median<2)

07    {

08        if (m == 0 && n == 0) return 0;

09        if (m==1) return A[0];

10        else return B[0];

11    }

12

13    while ( (i+j) <= (median/2) )

14    {

15        prev = last;

16        if (i >= m) //如果A中的元素已经用完，直接取B数组

17        {

18            last=B[j];

19            j++;

20        }

21        else if (j>=n) //同上

22        {

23            last = A[i];

24            i++;

25        }

26        else if (A[i]<B[j]) //取A[i] 和 B[j] 中较小的

27        {

28            last = A[i];

29            i++;

30        }

31        else

32        {

33            last=B[j];

34            j++;

35        }

36    }

37

38    if ((median & 1) == 0) //偶数个

39        return (prev + last) / 2.0;

40    else //奇数个

41        return last;

42}

Solution: A bianry algorithm for this is as follows:

Compare the medians of the 2 arrays.
If they are equal, median is found.
Else if arr1[mid] < arr2[mid], then:
1. Eliminate the smaller half of arr1 and
2. Eliminate the greater half of arr2 as they will form the first quarter and last quarter of the merged arrays.
Recurse for the remaining halves of each array to get the median of the merged arrays.

The above algorithm works well till we get the array sizes down to 2
When any of the arrays' size becomes less than 2, then special cases arise.
Let A[N] and B[M] be the arrays with sizes N and M such that N < M
There are 4 cases:

N=1 and M=even: Median is median of 3 numbers: A[0], B[M/2 - 1] and B[M/2]
N=1 and M=odd: Median is median of 4 numbers: A[0], B[M/2 - 1], B[M/2] and B[M/2 + 1]
N=2 and M=odd: Median is median of 3 numbers: B[M/2], max(A[0], B[M/2 - 1]), min(A[1], B[M/2 + 1])
N=2 and M=even: Median is median of 4 numbers: B[M/2], B[M/2 - 1], max(A[0], B[M/2 - 2]), min(A[1], B[M/2 + 1])

Read full article from Median of two sorted arrays - PrismoSkills

LeetCode 4 - Median of two sorted arrays

Labels

Popular Posts