- 21.0%

https://leetcode.com/problems/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)).

1 | Example 1: |

1 | Example 2: |

#### cpp

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:

1 | "if we cut the sorted array to two halves of EQUAL LENGTHS, then |

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

1 | [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:

1 | N Index of L / R |

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

1 | (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.

1 | [6 9 13 18] -> [# 6 # 9 # 13 # 18 #] (N = 4) |

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:

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

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

1 | "any number in the two left halves" <= "any number in the two right |

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 | [# 1 # 2 # 3 # (4/4) # 5 #] |

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,

1 | L1 = A1[(7-1)/2] = A1[3] = 4; R1 = A1[7/2] = A1[3] = 4; |

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

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

1 | If we have L1 > R1, it means there are too many large numbers on the left half of A1, |

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.

I know that was not very easy to understand, but all the above reasoning eventually boils down to the following concise code:

1 | double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { |

If you have any suggestions to make the logic and implementation even more cleaner. Please do let me know!

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

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

1 | class Solution { |

Share one divide and conquer O(log(m+n)) method with clear description

// using divide and conquer idea, each time find the mid of both arrays

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

https://discuss.leetcode.com/topic/11478/o-lg-m-n-c-solution-using-kth-smallest-number

O(lg(m+n)) c++ solution using kth smallest number

1 | class Solution { |

Another simple and neat solution, binary search, non-recursion, 3 rows of core code, O(log(min(m, n)))

If you solve the k-th minmum value of two sorted arrays, you solve this problem.This is a classical problem of “Divide and conquer”.

Here is another more simple and more neat solution.

Cosider chosing first x numbers from A and k - x numbers from B.if these k numbers are the k minmum numbers of A and B, x must satisfies that A[x + 1] >= B[k - x] and B[k - x + 1] >= A[x] (for better explanation index is base-1).

So this x is what we want.

Obviously, if A[x + 1] < B[k - x + 1] then x must be smaller, else if B[k - x] < A[x] then x must be greater. A nice two-value definition for binary search :)

To simplify edge cases, we cosider each array indefinite, with value of INTMIN when index < 1 and INTMAX when index > n.

Here is the solution of c++ version:

1 | typedef vector<int> vi; |

#### python

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

To solve this problem, we need to understand “What is the use of median”. In statistics, the median is used for dividing a set into two equal length subsets, that one subset is always greater than the other. If we understand the use of median for dividing, we are very close to the answer.

1 | First let's cut A into two parts at a random position i: |

Since A has m elements, so there are m+1 kinds of cutting( i = 0 ~ m ). And we know: len(left_A) = i, len(right_A) = m - i . Note: when i = 0 , left_A is empty, and when i = m , right_A is empty.

1 | With the same way, cut B into two parts at a random position j: |

Put left_A and left_B into one set, and put right_A and right_B into another set.

1 | Let's name them left_part and right_part : |

If we can ensure:

1 | 1) len(left_part) == len(right_part) |

then we divide all elements in {A, B} into two parts with equal length, and one part is always greater than the other. Then median = (max(left_part) + min(right_part))/2.

To ensure these two conditions, we just need to ensure:

1 | (1) i + j == m - i + n - j (or: m - i + n - j + 1) |

(For simplicity, I presume A[i-1],B[j-1],A[i],B[j] are always valid even if i=0/i=m/j=0/j=n . I will talk about how to deal with these edge values at last.)

So, all we need to do is:

1 | Searching i in [0, m], to find an object `i` that: |

And we can do a binary search following steps described below:

1 | <1> Set imin = 0, imax = m, then start searching in [imin, imax] |

When the object i is found, the median is:

1 | max(A[i-1], B[j-1]) (when m + n is odd) 注释 odd 奇数 |

Now let’s consider the edges values i=0,i=m,j=0,j=n where A[i-1],B[j-1],A[i],B[j] may not exist. Actually this situation is easier than you think.

What we need to do is ensuring that max(left_part) <= min(right_part). So, if i and j are not edges values(means A[i-1],B[j-1],A[i],B[j] all exist), then we must check both B[j-1] <= A[i] and A[i-1] <= B[j]. But if some of A[i-1],B[j-1],A[i],B[j] don’t exist, then we don’t need to check one(or both) of these two conditions. For example, if i=0, then A[i-1] doesn’t exist, then we don’t need to check A[i-1] <= B[j]. So, what we need to do is:

1 | Searching i in [0, m], to find an object `i` that: |

Thank @Quentin.chen , him pointed out that: i < m ==> j > 0 and i > 0 ==> j < n . Because:

1 | m <= n, i < m ==> j = (m+n+1)/2 - i > (m+n+1)/2 - m >= (2*m+1)/2 - m >= 0 |

So in situation ** and , we don’t need to check whether j > 0 and whether j < n.**

Below is the accepted code:

1 | def median(A, B): |

https://leetcode.com/discuss/15790/share-my-o-log-min-m-n-solution-with-explanation

120ms, 86.12%, June.25th, 2016

1 | class Solution(object): |

https://leetcode.com/discuss/20897/intuitive-python-solution-smallest-two-sorted-arrays-252ms

Intuitive Python O(log (m+n)) solution, by kth smallest in the two sorted arrays, 252ms

144ms, 30.79%, June.25th, 2016

The idea is in the comment:

1 | class Solution(object): |

https://discuss.leetcode.com/topic/22406/python-o-log-min-m-n-solution

Python O(log(min(m,n)) solution

It’s guaranteed to be O(log(min(m,n)) because every time the findKth function cuts the shorter array by half of its size.

1 | class Solution: |

#### java

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

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.

Here is the code:

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

I’m lazy to type. But I found a very good pdf to explain my algorithm:

BTW: Thanks to xdxiaoxin. I’ve removed the check “midB > k”.

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

Concise JAVA solution based on Binary Search

**Explanation**

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:

1 | if (aMid < bMid) Keep [aRight + bLeft] |

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

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