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.

8 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.

Sheetal said...
This comment has been removed by the author.
Daniel said...

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