Thursday, October 04, 2007

Getting the Kth smallest element in two Sorted Lists

Problem
--------
Let A and B be two sorted arrays. The intent is to find the kth smallest number in the union of the two lists.

Sounds Simple, but the catch is to get it done with a better time complexity than O(size(A) + size(B)).

I now have the solution which works with O(log(size(A) + size(B)), but i gave a crappy solution to my friend who gave me this puzzle. I used the intuitive, 2 pointer solution. Dont fall for it.

7 comments:

Arvind said...

since A and B are already sorted, take any first element of the A or B array, then assuming that element (for example from array A[0]) as the least element do a binary search on the other array (i.e array B). Replace the least element variable with the least of the 2 numbers compared in the "for" loop. So the total time complexity will be O(log N). Correct me if I am wrong.

Arvind said...

Refining the solution more, if A[0] < B[0], then smallest element is A[0], else if A[0] >= B[0] then smallest element is B[0]. No pointers nothing, very simple solution.

Shantanu said...

The refined method works for the 1st smallest element.

The question is for the kth smallest element.

Shantanu said...

Hint/solution here
http://72.14.235.104/search?q=cache:nTs2GWQVV1EJ:www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s01/recitations/rec03/rec03.ps+get+kth+element+in+two+sorted+lists&hl=en&ct=clnk&cd=17&gl=us

Arvind said...

The link isn't visible properly, please use the html tags.

Shantanu said...

select the whole link and paste it.

Daniel said...

I found this solution helpful http://aleph.nu/blog/kth-smallest-in-sorted-union.html