## Riverbed Interview Question

Software Engineer / Developers**Country:**United States

The above solution works but is O(k). For large values of k, this solution may not be optimal.

There is a better solution that works in O(log m + log n) where m and n are the lengths of the two arrays. This solution uses a divide-and-conquer approach.

Select Ai and Bj from the two arrays A and B such that i+j = k -1.

If Ai > Bj,

the kth smallest element should lie in the subarrays [A0 - Ai] and [Bj - Bn]

the way to understand this is that none of the elements in [B0 - Bj] can be the kth smallest element when u consider the union of the two arrays (think about this for a while)

by similar reasoning, all the elements in [Ai+1 - Am] should be greater than the kth smallest element and can be eliminated.

Apply the same logic recursively to the two subarrays [A0 - Ai] and [Bj - Bn]. But now since we have eliminated j elements which are less than the kth smallest element, we have to look for k-j th element in the two subarrays.

/*

* Given 2 sorted arrays find kth element in merged sorted array

*/

int KthMergedSorted (int a[], int b[], int k) {

int len1 = 5;

int len2 = 5;

int i, l = 0, m = 0;

if (len1 + len2 < k) {

return (FALSE);

}

for (i = 0; i < k; i++) {

if (l < len1 && a[l] < b[m]) {

if (i == k-1) {

return (a[l]);

}

l++;

} else {

if (i == k-1) {

return (b[m]);

}

m++;

}

}

}

int main () {

printf("I AM HERE\n");

int arr1[] = {1,5,8,7,19};

int arr2[] = {2,4,13,14,20};

printf (" ..%d..",KthMergedSorted (arr1, arr2, 10));

printf("\n");

return(0);

}

Better to just count as if you were merging, but just don't merge.

```
public class KthElementTwoSortedArrays {
public static void main(String[] args) {
int[] b = {2,3,4,5,6,7,8,9};
int[] a = {10,11,12,13,14,15,16,17,18,19};
int k = 14;
int count = 1;
int i = 0;
int j = 0;
while (i < a.length || j < b.length) {
int n;
if (i < a.length && (j > b.length - 1 || a[i] < b[j])) {
n = a[i];
i++;
}
else {
n = b[j];
j++;
}
if (count == k) {
System.out.println("Kth entry (K = " + k + ") in merged array would be: " + n + ".");
break;
}
count++;
}
}
}
```

```
public class sorted_array {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int c =0;
int numbers_1[] = {1,2,3,4,5,6,7,8,9};
int numbers_2[]= {9,8,7,6,5,4,3,2,1};
int index = 50;
c= numbers_1.length+numbers_2.length;
int numbers_3 [] = new int[c];
for(int i = 0;i<numbers_1.length;i++)
{
numbers_3[i]=numbers_1[i];
}
for(int k = 0;k<numbers_2.length;k++)
{
numbers_3[numbers_1.length+k]=numbers_2[k];
}
if(index<c)
{
System.out.println(numbers_3[index]);
}
else
{
System.out.println("wrong index given");
}
}
}
```

This is basic array merge logic, except you don't actually write the merged array.

- vijay January 14, 2012