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]
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.
@cz171 said in return sorted array from a matrix:
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]]
@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.
@cz171 said in return sorted array from a matrix:
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
@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]++;
}
}
@StefanPochmann Sorry, mistake in second "for" clause.
Has to be
for (int j = m-1; j>=0; j--) {