wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Merge Arrays in constant space and linear time
        
(Message started by: hary on Feb 6^th, 2010, 1:10am)

Title: Merge Arrays in constant space and linear time
Post by hary on Feb 6^th, 2010, 1:10am

Merge two sorted arrays one containing "m" elements and other caontaining "n" elements. We need to do this in constant space. Most of us know that linear time complexity for merging is possible. I am wondering if tconstant space complexity is possible. Can someone comment.

Title: Re: Merge Arrays in constant space and linear time
Post by birbal on Feb 6^th, 2010, 1:20am

on 02/06/10 at 01:10:39, hary wrote:

I dont think constant space complexity is possible. But yes you can do it with min( m, n) extra space.

Title: Re: Merge Arrays in constant space and linear time
Post by dormant on Feb 6^th, 2010, 2:55am

Quote:

where to store the merged arrays?
we must have space for that.

or do we have a single array of m+n size in which first m elemnts are sorted and last n elements are sorted?

Title: Re: Merge Arrays in constant space and linear time
Post by towr on Feb 6^th, 2010, 3:23am

See here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?action=display;board=riddles_cs;num=1261939168;start=0#6) and here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?action=display;board=riddles_cs;num=1237111757;start=0#9).

In summary, it's possible, but it's so complicated no one here has tried to post an algorithm for it :P

Title: Re: Merge Arrays in constant space and linear time
Post by bmudiam on Feb 8^th, 2010, 7:17pm

You can do merging in O(N), if the elements are maintained in a singly linked list.

Actually, you can do merge sort also using singly linked list in O(nlogn) without using any extra space.

Title: Re: Merge Arrays in constant space and linear time
Post by towr on Feb 9^th, 2010, 3:26am

on 02/08/10 at 19:17:58, bmudiam wrote:

You can do merging in O(N), if the elements are maintained in a singly linked list.

Yes, but we don't have a linked list, we have an array. That's what makes the problem problematic.