Kth smallest in union of arrays

Given two sorted arrays of size M and N. Find Kth smallest element in the union of the two arrays in constant space. (i.e. without using additional space).

Solution :

The Kth element will be found within first K elements of both arrays, so we consider only these elements or whole array if size is less than K
We use recursive procedure. We compare (K/2)th element in arrays A(0 K) and B(0 K)
if A(K/2) < B(K/2) we recursively find (K-K/2)th smallest element in A(K/2+1 K) and B(0 K/2) eliminating first K/2 elements from A
else if A(K/2) > B(K/2) we recursively find (K-K/2)th smallest element in B(K/2+1 K) and A(0 K/2) eliminating first K/2 elements from B
if A(K/2) == B(K/2) return A(K/2) as answer

Boundaries must be checked in the procedure

Complexity :

• Time : log N + log M (Please check if its min(log N, log M) rather than this)
• Space : O(1)

Code :

void kth_smallest(int[] A, int M, int[] B, int N, int K, int &result){

int a_high = (M < K) ? M : K;
int b_high = (N < K) ? N : K;

result = find_kth(A, 0, a_high, B, 0, b_high, K);

}

int find_kth(int[] A, int a_low, int a_high, int[] B, int b_low, int b_high, int K){

// boundary cases
if(a_low > a_high)

return B[b_low + K - 1];

if(b_low > b_high)

return A[a_low + K - 1];

int mid = (K+1)/2;  // finding ceiling of K/2

if(A[mid] == B[mid])

return A[mid];

else if(A[mid] < B[mid])

return find_kth(A, a_low + mid+1, a_high, B, b_low, b_low + mid, mid);

else if(A[mid] > B[mid])

return find_kth(A, a_low, a_low + mid, B, b_low + mid + 1, b_high, mid);

}

void kth_smallest_linear(int[] A, int M, int[] B, int N, int K, int &result){

int i=0, j=0;
for( ; K; K--){

if(i >= M){

result = B[j + K - 1];
break;

}
if(j >= N){

result = A[i + K - 1];
break;

}
if(A[i] == B[j]){

result = A[i++];
j++;

}
else

result = (A[i] < B[j]) ? A[i++] : B[j++];

}

}