On Fri, Sep 18, 2009 at 6:20 PM, Mangal Dev Gupta dev.it...@gmail.comwrote:
@mittal
I am not able to understand . How are you updating the C
array?..You didnt tell what will be the updated array after second
element?Please elaborate...
Size of array C is same as that of X, i.e.
@Anil
Thats right O(n,n) time complexity for k=O(n).
Still it is better than Rama's O(n*m*log k)
which would be order O(n.n.logn) in worst case.
// sorry for the delay in response. I was away for a week with no
access to internet
_dufus
On Sep 15, 11:19 am, Anil C R cr.a...@gmail.com wrote:
I am not sure if constant space requirement is possible. But we can do it
with O(k) space complexity.
Maintain a max heap of k elements. For each of the n*m sums add it to the
heap (if it ain't full with k elements) or replace the root and heapify if
the sum is lesser than the root.
Finally the
@dufus
if extracting the kth smallest element would tske O(kn) then extracing the
nth element would take O(n^2) right?
On 9/14/09, Ramaswamy R ramaswam...@gmail.com wrote:
I am not sure if constant space requirement is possible. But we can do it
with O(k) space complexity.
Maintain a max
Extracting the smallest from the young tableau takes O(1) and and restoring
its properties takes O(m+n) (where m n and the number of rows and
columns). This is much like extracting the max from a max-heap. So
extracting the kth element would be k*O(n+m) ~ k*O(2n) (when m=n as in this
problem) ~
A correction in the proposed algorithm.
On Tue, Sep 15, 2009 at 1:08 PM, Shishir Mittal 1987.shis...@gmail.comwrote:
*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] +
*For each of the n*m sums add it to the heap (if it ain't full with k
elements) or replace the root and heapify if the sum is lesser than the
root.* how u can judge which is the next value to be added..
try your algo at
array a 1 2 3 4 5 7 9
and array b 2 3 5 6 7
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
The order does not matter! When you keep feeding a max heap with N values
(replacing the root and heapifying if the value is smaller than root) in
this case the sums, you end up with the least k sums encountered. And the
root would be the kth sum in increasing order.
We feel all n*m values and
@dufus
lokking at your soln of young tableau
i think there is a problem of repition of some number
given
array A={1,2,3,4}
array B={2,3,4,5};
and try to look wat i say..
3 will repeated , 4 , 5 and so on..
On Sat, Sep 5, 2009 at 12:35 PM, Dufus rahul.dev.si...@gmail.com wrote:
It seems
@dufus
wat is your complexity ??
On Sat, Sep 5, 2009 at 8:17 PM, Dufus rahul.dev.si...@gmail.com wrote:
In that case I would sacrifice a little bit on time complexity and
instead of storing I would recompute the values.
_dufus
On Sep 5, 5:10 pm, ankur aggarwal ankur.mast@gmail.com
*find the posiible sums using brute force.then apply this algo
this is the main problem ..
how to do efficiently ??
*
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
It seems EXTRACT_MIN for Z[n^2] can be done in O(n) time.
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
Then using it we can find the kth smallest element in O(nk) time.
_dufus
On Sep 4, 10:03 pm, ankur aggarwal ankur.mast@gmail.com wrote:
Find nth smallest inO(n)
@dufus..
if there is constant space requirement then ??
wat will be your soln ??
On Sat, Sep 5, 2009 at 12:35 PM, Dufus rahul.dev.si...@gmail.com wrote:
It seems EXTRACT_MIN for Z[n^2] can be done in O(n) time.
In that case I would sacrifice a little bit on time complexity and
instead of storing I would recompute the values.
_dufus
On Sep 5, 5:10 pm, ankur aggarwal ankur.mast@gmail.com wrote:
@dufus..
if there is constant space requirement then ??
wat will be your soln ??
On Sat, Sep 5, 2009
find the posiible sums using brute force.then apply this algo
*function* findFirstK(list, left, right, k)
*if* right left
select pivotIndex between left and right
pivotNewIndex := partition(list, left, right, pivotIndex)
*if* pivotNewIndex k *// new condition*
16 matches
Mail list logo
