using merge sort takes lot of space complexity.
alternaticely we can solve it using a min- heap
let the array be
0 1 2
0 2 3
1 3 4
then first of all insert top left elemnt in heap(guranteed to be minimum)
heap contans {0}
then and insert elements just greater then i.e to the right and below to it
in heap and remove minimum mark the placea[0][0] as -1and print it. do not
insert if you have -1 over there(avoiding repetition.)
-1 1 2
0 2 3
1 3 4
so now 0 gets printed and in heap we have 0(a[1][0]) and 1(a[0][1]).
now insert element adjacent to a[1][0] i.e 0, now heap contains 1(a[2][0])
and 2[a[1][1]] and 1(a[0][1]).
-1 -1 2
-1 -1 3
-1 3 4
till now printed 0,0
now 1(a[0][1]) gets extracted and and 2 a[0][2] gets in heap so that the
heap now contains 1(a[2][0]) and 2[a[1][1]] and 2 a[0][2]
till now printed 0,0,1
-1 -1 -1
-1 -1 3
-1 -1 4
now 1(a[2][0]) gets extracted and 3 a[2][1] gets in heap and heap now
contains 3 a[2][1] and 2[a[1][1]] and 2 a[0][2]
till now printed 0,0,1,1
do in similar way .... i hope its better in terms of space complexity and
b/w O(n*n) and O(n*nlog(n*n))
On Tue, Feb 8, 2011 at 6:54 PM, arpit busy in novels <
[email protected]> wrote:
> take 1st as 763 2nd as 753 merge them k[]=76533
>
>
> take 42 as 1st 42 as 2nd merge as l[] 422
> now merge k & l as 7654332 add 2 ie
> a[00] always lowest
>
>
> On Tue, Feb 8, 2011 at 5:47 PM, September5th <[email protected]> wrote:
>
>> How do you handle this condition???
>>
>> 1 2 3
>> 2 4 5
>> 3 6 7
>>
>> 3 is smaller than 4~
>>
>> On Feb 8, 2:48 am, arpit busy in novels
>> <[email protected]> wrote:
>> > after a bit analysis i stick strongly to my soln :::::
>> >
>> > 0 1 2 3 since element of last row & column will
>> > always be greater than rest of array
>> > 2 2 3 4
>> > 3 3 4 5
>> > 4 5 6 7 take 7654 as 1st & 7543 as 2nd merge
>> them
>> > as k[]
>> >
>> > array reduced to
>> > 0 1 2
>> > 2 2 3
>> > 3 3 4 take 433 as 1st 432 as 2nd
>> > merge them as l[]
>> >
>> > 0 1
>> > 2 2 22 & 21 as m[]
>> >
>> > merge all k[] m[] l[] add least element always a[0,0]
>> > ..........................................hope this is clear least on
>> my
>> > side
>>
>> --
>> 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?hl=en.
>>
>>
>
>
> --
> Arpit Bhatnagar
> (MNIT JAIPUR)
>
> --
> 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?hl=en.
>
--
With Regards,
*Jalaj Jaiswal* (+919019947895)
Software developer, Cisco Systems
Final Year Undergraduate,
IIIT ALLAHABAD
--
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?hl=en.
