@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 needed to establish the heap condition.
2. Print the root node of the heap. 3. Replace the root node with the element of the array that is in the next column of the same row. If all of the elements in that row have been printed, instead move the last node in the heap into the root position and decrease the heap size by 1. 4. Perform a downheap operation to restore the heap condition. 5. Go back to step 2 if the heap is not empty. Comments: 1. You can interchange "row" and "column" in the above description if you prefer. 2. If the array is of size m by n, then the work involved in this algorithm is O(m n log m) if you use the algorithm as described above, or O(m n log n) if you switch "row" and "column." 3. The heap will have m or n nodes, so you need 3*m or 3*n extra memory. I suppose that we could write this as O(m + n). Dave On Feb 7, 2:43 am, jalaj jaiswal <[email protected]> wrote: > You are given a array with rows sorted and column sorted. You have to print > entire array in sorted order. > > -- > 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.
