Blog # 61 : Kth smallest element in union of 2 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). Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: Take a look again. Both the arrays are sorted. Hit again for hints. Hints: The Kth smallest element will be within first K elements of both arrays. 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 There are two solutions possible for this problem. I am also giving the linear O(N+M) solution which is simple but less efficient. Complexity: 1. TIme : O(log N + log M) 2. 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++]; } }