# My Accepted java solution

• basic Idea is very similar to K-selection. it's easier to understand if you imagine this to be chopping off the last K elements from a total of len(A) + len(B) elements, where K = (len(A) + len(B))/2.

we want to remove K, but each time we can remove only at most K/2 elements, because we can only be sure that these elements are not within the first (len(A) + len(B)) -K elements.

``````    import static java.lang.Math.*;
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
int K = A.length + B.length;
if (K%2 ==0 ) return  (findMedianSortedArrays(A,B, (K - K/2))  +  findMedianSortedArrays(A,B, (K-(K/2+1))) )/2;
else
return  findMedianSortedArrays(A,B, K - (K/2+1));
}

// k is the number of elements to REMOVE, or "Chop off"
public double findMedianSortedArrays(int A[], int B[], int K) {

int lowA=0, lowB=0;
int highA=A.length; int highB= B.length;
int midA; int midB;
while(K>0 && highA >0 && highB > 0) {
int chopA = max(1,min(K/2, (highA)/2));
int chopB = max(1,min(K/2, (highB)/2));

midA = highA-chopA;
midB = highB-chopB;
if (A[midA] <B[midB]) { // here A[0 .. midA] < B[midB], and we know that B[0 .. midB-1] < B[midB], so B[midB..highB] can not possibly be within the first (len(A) + len(B) - K) elements, and can be safely removed.
highB = midB;
K = K - chopB;
}
else {
highA = midA ;
K = K - chopA;
}
}

if (highA == 0 && highB == 0 ) return 0;
if (highA == 0) return B[highB-1-K];
if (highB== 0) return A[highA-1-K];
return Math.max(A[highA-1], B[highB-1]);
}

}``````

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