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.
Subscribe to:
Post Comments (Atom)
7 comments:
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.
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.
The refined method works for the 1st smallest element.
The question is for the kth smallest element.
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
The link isn't visible properly, please use the html tags.
select the whole link and paste it.
I found this solution helpful http://aleph.nu/blog/kth-smallest-in-sorted-union.html
Post a Comment