Considering a general case of two sorted arrays X[n], Y[m] , n<=m and kth
element is requied in the set Z = {x+y, such that x is in X[], &y is in
Y[]}, here is an algorithm which takes *O(n + klogn) time and O(n) space.*
So I guess, if k=n, this time complexity is better than O(kn).
*Logic*: Let we are trying to find k smallest elements. Then, at each
iteration i < k,* we can at maximum have n options to choose the ith element
*. For e.g.
Let X[3] = {3, 5, 8}
Y[8] = {1, 2, 4, 5, 7, 9, 11, 12}.
And we need to find 8th element.
Initialize an array C[3] = {0,0,0}. C denotes the array indices in array Y,
which are to summed with corresponding elements in X and compared.
So for comparison of 1st element in Z, we have 3 options ( X[0] + Y[0],
X[1]+Y[0], X[2]+Y[0] ). 4 is the answer
Next update the array C = {1,0,0}, now 2nd element is min of ( X[0]+Y[1],
X[1] + Y[0], X[2] + Y[0] ), 5 is the answer.
Continuing similarly, for the 8th element, array C is {4,3,0} so the 8th
element is minimum of ( X[0] + Y[4], X[1]+ Y[3], X[2] + Y[0] ), which is 10.
*Algorithm.*
1) Corresponding to each element in X, create a node with 2 values, to be
compared indexed of Y, and the corresponding sum.
NODE[i] = {yIndex, sum = X[i] + Y[yIndex]}
2) Form a MinHeap of the nodes.
3) Increment the yIndex of the root node of heap and also the corresponding
sum value.
4) Min Heapify this array of nodes, with key as sum value.
5) Repeat steps 3 and 4, k-2 times.
6) sum value of root node is the required answer.
*Space Complexity : O(n),
Time Complexity : O(n + (k-1)logn).*
*For k = n, Time complexity : O(nlogn)*.
However, in the above method, I found out the k smallest elements in Z in
sorted order, even though only the kth element was asked.
Hence, I believe there is still some scope of optimization!
On Fri, Sep 4, 2009 at 10:33 PM, ankur aggarwal <[email protected]>wrote:
> Find nth smallest inO(n) Given two arrays of length n in sorted order
> X[n] & Y[n].
> Now make another array Z[n^2]={such that z belongs to X+Y}.
> AS all possible sum of x+y is there in Z. You have to give the nth smallest
> no of Z in O(n) time.
> Space complexity : No bound on it. But try to optimize it if possible.
>
> >
>
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
