CareerCup

For M X N matrix, If we use heap, I think this is possible in O(nlogM) where n is total number of elements.
1, For every node in heap, store i,j which shows current cell's row, column.
2, Initialize heap with first elements of each row.
3, Whenever the elements are removed replace the next element in the same row using i,j value of the removed node.
4, If entire row is exhausted, decrease heap size by 1.
Continue till heap size is zero.

Since each elemetn is visited once & heap is of size M, order is O(nlogM).

If this kind of matrix is there then elements in the first row would be the only elements and plus the element at a[i][i].....So elements in first row can be printed in n^2 times and element at a[i][i] can be printed in constant time..........hence running time shud be O(n^2)

O(n^2 logn) is trivial, but O(n^2) seems difficult.

struct element
{
value // value of the element in the Matrix
(i,j) //location of the element
}

// Q is priority Q based on Value

Start from (i,j) = (0,0) - as it is the minimum in the Matrix

Add element[0][0] to Priority Q //element.value = a[0][0], element.i=element.j=0

while(Q not empty)
{
x = Q.pop() // gets the minimum from the Q based on value
print x.value
Add neighbour values of (x.i,x.j) to a Priority Q // which are a[i+1][j] &
a[i][j+1]
}

My bad..I think the solution is no better than O(n2logn).

However, cant we just simply sort treating the matrix as single row of all numbers and print them. Regular sorting takes O(n2).

Create a min heap of the first row in the matrix
Remove the min element and replace this with the element in the first column till the last element in the first column.

we have scanned the topmost row and leftmost column...
Now consider the new matrix where the toprow and left column does not exist.
Do the same as above with the new matrix

Time complexity => O((M+N)logN)

can any one please give the code so that the complexity is calculated.

Why is this question tagged under Operating System?

Can be done in linear time. Use 2 pointer- 1 would move from top to bottom and other from left to right. Compare the elements pointed by 2 ptrs, push the smaller elt in the output array and increment this prt. I tried to implement it in Java. Below is the code:

public class SortMatrix {
	public static void main(String[] args) 
	{
		int[][] input = new int[][] {{5,10,11,12},{6,16,26,27},{7,22,27,36},{8,23,38,43}};
		int[] op = sortMatrix(input);
		{
			for(int i:op)
			{
				System.out.print(i +", ");
			}
		}

	}

	public static int[] sortMatrix(int [][] collection)
	{
		int numOfColls = collection.length;
		int numOfRows = collection[0].length;
		int[] output = new int[numOfColls*numOfRows];
		int a = 1;
		int b = 0;
		int c = 0;
		int d = 1;
		int opctr = 0;
		output[0] = collection[0][0];
		while(++opctr<output.length)
		{
			if(a==c && b==d) //both the ptr ponting to the same elt
			{
				output[opctr] = collection[a][b];
				a++;
				d++;
			}
			else if(collection[a][b]<collection[c][d])
			{
				output[opctr] = collection[a][b];
				a++;
			}
			else
			{
				output[opctr] = collection[c][d];
				d++;
			}
			
			if(a==numOfColls)
			{
				a = c;
				b++; 
			}
			if(d==numOfRows)
			{
				d = b;
				c++;
			}
		}
		return output;
	}
}

why not user a merge sort on each row...
main() {
int a[NXM];
int b[N][M] = {{1,2,4},{3,4,6},{5,6,7});
for (i = 0 i < NXM; i++) {a[i] = 0;}
merge(a, b);
}

merge(int a[], int b[][]) {

for(int i = 0; i< N; i++) {
mergeMatrix(a, b[i]);
}

mergeMatrix(int a[], int b[]) {
mergeSort(a, b);
}

Complexity O(NM)

We can do sorting in O(n root(n)) , Matrix is a youngs tableau . So we can sort those elements as explained in the below link

lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf