@Ravi: Construct a min-heap of the elements of the first column, each
appended with its row and column number, i.e., form a heap whose elements
contain (a[i][0], i, 0).
While the heap is not empty:
Output the top element of the heap.
Insert the next element from its row, if any.
If the output array is empty, or if the outputted heap top is different
from the last element in the output array,
then insert the outputted heap top into the output array.
Complexity is m*n*log(m).
Dave
On Tuesday, January 8, 2013 11:59:55 AM UTC-6, Ravi Ranjan wrote:
> You have a two dimensional array of size m*n. The
> elements in the rows are sorted and every row has
> unique elements means( in a row no two elements are same) but
> the elements can repeat across the rows.
> For example:
> you have following 2-D array:
> 2 5 7 9 14 16
> 3 6 8 10 15 21
> 4 7 9 15 22 35
> 7 8 9 22 40 58
> You are supposed to write an efficient function which
> will take upper 2-D array as input and will return a
> one-dimensional array with following properties:
> a) the 1-D array must contain all the elements of above
> 2-D array.
> b) the 1-D array should not have any repeated elements.
> c) all the elements should be in sorted order.
> For example:
> for the above 2-D array, the output should be:
> A [ ] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 21, 22, 35,
> 40, 58 }
--
