# return sorted array from a matrix

• Input a matrix, where every number is greater or equal to the numbers on its right and
bottom.
Output a sorted array

Here is an example:
eg. Give the matrix
[ [15, 13, 12],
[13, 11, 10],
[ 9 , 5, 1 ]]

output : [1, 5, 9, 10, 11, 12, 13, 13, 15]

• @cz171 could you specify output a sorted array of what size?

• the output array should contain all elements from the matrix, so the size should be m * n.

• eg. Give the matrix
[ [15, 13, 12],
[13, 11, 10],
[ 9 , 5, 1 ]]

output : [1, 5, 9, 10, 11, 12, 13, 13, 15]

I only find a way of solving this with the method of merging k sorted array, where the Big O is O(nlogk, n is the number of elements and k is the number of rows). Can you find a way of solving it with O(n)?

• @cz171 It is better if you could edit your post and add the example there. To edit your post, click on the three vertical dots on the right side of your post, and click Edit.

• Can you find a way of solving it with O(n)?

I think so. Due to the constraint, each step you only need to scan at most two elements (the top and left elements).

EDIT: Found out that this won't work, for example:

[[10, 9, 1],
[ 9, 5, 0],
[ 8, 7, -1]]

• This post is deleted!

• @1337c0d3r
If you don't mind, show me the code. At first glance I came out of this method too, but after creating some test case I found it didn't work.

• This post is deleted!

• n is the number of elements [...] Can you find a way of solving it with O(n)?

Consider this matrix (each "?" is a number I'm keeping secret for now):

``````900  ?  800  ?  700  ?  600  ?  500
?  800  ?  700  ?  600  ?  500  ?
800  ?  700  ?  600  ?  500  ?  400
?  700  ?  600  ?  500  ?  400  ?
700  ?  600  ?  500  ?  400  ?  300
?  600  ?  500  ?  400  ?  300  ?
600  ?  500  ?  400  ?  300  ?  200
?  500  ?  400  ?  300  ?  200  ?
500  ?  400  ?  300  ?  200  ?  100
``````

There's no relationship between the eight numbers between 400 and 500. So you'll have to do a full sort of them. Same for the other diagonals. Even if you exploit the structure of my matrix and only sort each diagonal of missing numbers, I think you'll need more than linear time (unless you're doing something like radix sort, but that would render the exercise pointless).

• This problem somehow reminds me of another problem: Finding the kth smallest element from a sorted matrix:

There is an O(n + m) algorithm to determine the kth smallest element, which is written in a paper published here if anyone is interested :)
http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf

• @StefanPochmann Got u! I think the best solution wouldn't be faster than O(nlogk)

• ``````def sortMatrix(mat):
ret = []
while mat:
if len(mat) == 1:
mat[0].reverse()
ret += mat[0]
break
i,j=mat[-1][-1],mat[-2][-1]
v = -1 if i<j else -2
ret.append(mat[v].pop())
if len(mat[v]) == 0: mat.pop(v)
return ret
``````

• @1337c0d3r 5 is not greater than 7

``````[[10, 9, 1],
[ 9, 5, 0],
[ 8, 7, -1]]
``````

• @starky Your solution doesn't work:

``````>>> sortMatrix([[6, 3],
[5, 2],
[4, 1]])
[1, 2, 4, 3, 5, 6]
``````

• @StefanPochmann bummer, yea I can't do it in O(n), I can do it in O(n*#row). Eliminate one element at a time and check against the last column

``````def sortMatrix(mat):
ret = []
while mat:
_,i = min([(lst[-1],i) for i,lst in enumerate(mat)])
ret.append(mat[i].pop())
if len(mat[i]) == 0: mat.pop(i)
return ret
``````

• Hi guys,
Solution for integers with O(N). a[0][0] is the maximum and a[n-1][m-1] is minimum.
So we can create temporary array with length=n*m and just count the number of elements

``````int[] tmp = new int[n*m];
int max = a[0][0], min = a[n-1][m-1];
for (int i = n-1; i>=0; i--) {
for (int j = m-1; i>=0; i--) {
tmp[a[i][j] - min]++;
}
}
``````

• @DaniyarN That crashes for example for the matrix `[[9, 5], [5, 0]]`.

• @StefanPochmann Sorry, mistake in second "for" clause.
Has to be

`` for (int j = m-1; j>=0; j--) {``

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.