How to get O(log(m+n)) complexity? I only solved it in O(m+n)

• My naive solution is just merge two array and find the median. Obvious we can do better. But I just have no idea about it.

• This post is deleted!

• Below is my O(log(n+m))algorithm.The main idea is using binary search to find the key number's position.

``````class Solution {
public:
double findMedian(int A[], int m) {
if(m%2==1) return A[m/2];
return (A[m/2-1] + A[m/2]) / 2.0;
}
bool findMedianOdd(int A[], int m, int B[], int n, double &res) {
int left = -1, right = m, half = (n + m) / 2;
while(true) {
int mid = (left + right) / 2;
if(mid > half) {
right = mid; continue;
}
int num = half - mid;
if(num > n) {
left = mid; continue;
}
if((num<=0 || B[num-1]<=A[mid]) && (num>=n || B[num]>=A[mid])) {
res = A[mid];
return true;
}
if(num<=0 || B[num-1]<=A[mid]) {
right = mid;
} else {
left = mid;
}
if(left+1 >= right) break;
}
return false;
}
bool findMedianEven(int A[], int m, int B[], int n, double &res) {
int left = -1, right = m, half = (n + m) / 2;
while(true) {
int mid = (left + right) / 2;
if(mid > half) {
right = mid; continue;
}
int num = half - mid;
if(num > n) {
left = mid; continue;
}
if((num<=0 || B[num-1]<=A[mid]) && (num>=n || B[num]>=A[mid])) {
int tmp;
if(num<=0) tmp = A[mid-1];
else if(mid==0) tmp = B[num-1];
else tmp = max(A[mid-1], B[num-1]);
res = (tmp + A[mid]) / 2.0;
return true;
}
if(num<=0 || B[num-1]<=A[mid]) {
right = mid;
} else {
left = mid;
}
if(left+1 >= right) break;
}
return false;
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if(m==0) return findMedian(B, n);
if(n==0) return findMedian(A, m);
double res;
if((m+n) % 2 == 1) { //sample A={1, 3}, B = {2, 4, 5}, so use binary search to find 4
if(findMedianOdd(A, m, B, n, res)) return res;
findMedianOdd(B, n, A, m, res); return res;
} else { ////sample A={1, 3}, B = {2, 4}, so use binary search to find 3
if(findMedianEven(A, m, B, n, res)) return res;
findMedianEven(B, n, A, m, res); return res;
}
return -9999999.90;
}
}ttt;
``````

• Here is my Solution based on finding the kth element in two sorted arrays. Get rid of at least (m+n)/4 elements each time by using a binary search. T(m+n) <= T(3/4*(m+n)) + O(lg(m+n)), so the time complexity is O(lg(m+n)).

``````class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if ((m+n) % 2 == 1)
return findkthElement(A, m, B, n, (m+n)/2+1);
else
return (findkthElement(A, m, B, n, (m+n)/2) + findkthElement(A, m, B, n, (m+n)/2+1))/2.0;
}

int findkthElement(int A[], int m, int B[], int n, int k) {
if (m == 0) return B[k-1];
if (n == 0) return A[k-1];
if (k == 1) return min(A[0], B[0]);
if (m < n) return findkthElement(B, n, A, m, k);
int i = m/2;
int low = 0, high = n-1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (B[mid] <= A[i]) low = mid + 1; else high = mid - 1;
}
int j = high; //B[j] is the maximum number which <= A[i]
if (i+j+2 == k) //i+j+2 is the rank of A[i]
return A[i];
else if (i+j+2 < k)
return findkthElement(A+i+1, m-i-1, B+j+1, n-j-1, k-i-j-2);
else
return findkthElement(A, i, B, j+1, k);
}
};``````

• I use the select sort method to solve this problem, two 'pointer' to record the current position of two arrays, each time put a smaller one into merged array. Here is my Java code.

``````public double findMedianSortedArrays(int A[], int B[]) {
int m = A.length;
int n = B.length;
int[] merge = new int[m+n];
int currentA = 0, currentB = 0;
for(int i = 0; i < m+n; i++){
if(currentA < m && currentB <n){
if(A[currentA] < B[currentB]){
merge[i] = A[currentA];
currentA++;
}else if(A[currentA] > B[currentB]){
merge[i] = B[currentB];
currentB++;
}else{
merge[i] = A[currentA];
merge[i+1] = A[currentA];
currentA++;
currentB++;
i++;
}
}else if(currentA == m){
merge[i] = B[currentB];
currentB++;
}else if(currentB == n){
merge[i] = A[currentA];
currentA++;
}
}
if((m + n) % 2 == 0){
return ((double)merge[(m+n)/2] + (double)merge[(m+n)/2-1])/2;
}else{
return merge[(m+n)/2];
}
}``````

• Unfortunately, your algorithm is O(log(m+n)*log(m+n)), not O(log(m+n)). T(m+n) <= T(3/4*(m+n)) + O(lg(m+n)) is not acceptable, you should optimize it into T(m+n) <= T(3/4*(m+n)) + O(1) and then the final complexity will be O(log(m+n)).

• You are right. Thanks a lot for pointing out my careless mistake.

• You can reuse the algorithm which solves Find the k-th Smallest Element in the Union of Two Sorted Arrays.

My implementation below used binary search to maintain the invariant (i + j = k – 1), so the complexity is O(log k) = O(log((m+n)/2)) = O(log(m+n))

``````class Solution {
public:
int findKth(int A[], int m, int B[], int n, int k) {
int l = k - 1 - min(k - 1, n), r = min(k, m);
while (l <= r) {
int i = l + ((r - l) >> 1);
int j = k - 1 - i;
if (i >= 0 && i < m && (j >= n || A[i] <= B[j]) && (j == 0 || B[j-1] <= A[i]))
return A[i];
else if (j >= 0 && j < n && (i >= m || B[j] <= A[i]) && (i == 0 || A[i-1] <= B[j]))
return B[j];
if (j >= n || A[i] < B[j]) l = i + 1;
else r = i - 1;
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if ((m + n) & 1) return findKth(A, m, B, n, ((m + n) >> 1) + 1);
else return (findKth(A, m, B, n, (m + n) >> 1) + findKth(A, m, B, n, ((m + n) >> 1) + 1)) * 0.5;
}
};
``````

• Sounds great! But I solve this problem in O(m+n) and accepted

• Could you explain the definition of l and r here? I am confused with it.

• l and r are the boundries of i, i is the index of A's element that satisfied the invariant (i + j = k – 1).

• This post is deleted!

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