@all after 32 Message Discussion I know Everyone is looking for O(N)
solution well it seems odd how we can search an element in a O(m*n)
matrix in O(n) but answer of this question is given already in the
question that all row column are sorted so why O(n) solution
exist it really matters
@bittu
Question is about to print entire array in sorted order, not searching an
element
On Wed, Mar 2, 2011 at 4:13 AM, bittu shashank7andr...@gmail.com wrote:
@all after 32 Message Discussion I know Everyone is looking for O(N)
solution well it seems odd how we can search an element in a
Hii, can you please tell me wat d ques exactly is ??
THanks,
Krishna.
On Wed, Mar 2, 2011 at 9:52 AM, sunny agrawal sunny816.i...@gmail.comwrote:
@bittu
Question is about to print entire array in sorted order, not searching an
element
On Wed, Mar 2, 2011 at 4:13 AM, bittu
You are given a array with rows sorted and column sorted. You have to print
entire array in sorted order.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
I am not very sure i understood what you meant and if your suggestion
reduces the comparisons. Please see the code i posted at
https://github.com/algoseeker/Interview/blob/master/sorting/SortArray.java
and tell me what changes you are talking about.
--
You received this message because you
I am using a minheap and not a set if you see carefully.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
I am using a minheap (similar to priority queue) and order of extra space is
at O(n+m) which in fact is at max equal to n+m.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To
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
arpitbhatnagarm...@gmail.com wrote:
after a bit analysis i stick strongly to my soln :
0 1 2 3 since element of last row column will
always be
Merge sort with divide and conquer:
suppose n by n array,
Method 1.
1- Get sorted top half and sorted bottom half, (To get sorted top
half and sorted bottom half, recursively using this process)
2- and merge them together.
Time complexity: T(n * n) = 2 * T(n/2 * n) + n * n [until only 2 rows
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 hi.ming...@gmail.com wrote:
How do you handle this
@Jalaj: An efficient algorithm follows:
1. Using a data structure (int value, int row, int col), place the
first column of the array into a minheap. Because the columns are
sorted, the data can simply be copied in order, with row and column
numbers appended; no heap ordering operations will be
as per my analisys
sort elements diagonally in the 2d arry.
we can define diagonals by a[0,i] to a[i,0] is
a[0,i],a[1,i-1],a[2,i-2],.. a[i-1,1],a[i,0], sort the elements
if i col_size then diagonal is a[0,i] is define as
a[0,i],a[1,i-1],a[2,i-2]...a[x,i-x] where
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
I am not very sure about the correctness of this procedure.
But my approach would be as follows:
Concept: Maintain a set of numbers in which you maintain the values along
with its array indices, such that the next number in the sorted output will
be a part of this set. Consider the set
Just coded the solution, it worked on all the test cases described here in
this thread using the algo i described above :)
The code is available at
https://github.com/algoseeker/Interview/tree/master/sorting
--
You received this message because you are subscribed to the Google Groups
I see a scope of optimization in the algo.
In step 2. Before inserting the element a[i][j], you can make sure that
a[i][j-1] and a[i-1][j] are in the set. If not then do no insert a[i][j] in
the heap. (considering the boundary condition, if j-1 0 or i-1 0 then
assume it is true)
Correct me if I
U using extra space, if you using extra space, simple C++ implementation
will be use a priority queue and do BFS.
On Wed, Feb 9, 2011 at 10:47 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
@algoseeker
mine approach is also the same but m inserting the elements in a min heap
and you in a
I guess it will fail for the array, looks like incomplete logic.
4 911 14
5 10 13 16
9 16 18 20
On Feb 7, 5:55 pm, Ashish Goel ashg...@gmail.com wrote:
yet to test...
will download xcode to compile, not on linux or windows (:
remote case of all both entries in last row or last
But then we are not using the other property of the array that it's
columns are sorted
On Feb 7, 6:33 pm, jagannath prasad das jpdasi...@gmail.com wrote:
u can merge first two rows and proceed two at time.then slowly merge 4 at a
tym and so on.a recursive algo will do
On Mon, Feb 7,
@ spark , hi
i think either a[0,0] or a[n,n] will be the largest element
we need one more step to test which one is biggest then apply my algo:
I just though we should apply merge sortmean merge 2 array into one )
on 1st row 1st column this will be accurate since rows columns r
Sorted)
hey jalaj ,
i just wanna say can be 2 test cases
2 4 8
6 7 9
7 8 10 where a[n,n] is big
or 12 11 10
987
654where a[0,0] is biggest
if u didnt consider increment
can you explain what are you doing ... take this array for example and tell
how are you printing the sorted output
0 1 2 3
2 2 3 4
3 3 4 5
4 5 6 7
On Mon, Feb 7, 2011 at 10:27 PM, arpit busy in novels
arpitbhatnagarm...@gmail.com wrote:
hey jalaj ,
i just wanna say can be 2 test cases
i m taking 1st array as 7 6 5 4 2nd as 7 5 43and merging them
by merge sort so k[]={7,7,6,5,5,4,4,3}
then 1st as 4 3 3 2nd as 4 3 2
l[]=4,4,3,3,3,2
den
m=[2,2,1]
finally merging k , l , m
after a bit analysis i stick strongly to my soln :
0 1 2 3since 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 1st7543 as 2nd merge them
as k[]
array reduced to
0 1 2
2 2 3
3
24 matches
Mail list logo
