return sorted array from a matrix


  • 0
    C

    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]


  • 0

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


  • 0
    C

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


  • 0

    @cz171 Could you please add at least an example to your problem description? Thanks.


  • 0
    C

    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)?


  • 0

    @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.


  • 0

    @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]]


  • 0
    C
    This post is deleted!

  • 0
    C

    @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.


  • 0
    This post is deleted!

  • 0

    @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).


  • 0

    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


  • 0
    C

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


  • 0
    S
    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
    

  • 1
    S

    @1337c0d3r 5 is not greater than 7

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

  • 0

    @starky Your solution doesn't work:

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

  • 0
    S

    @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
    

  • 0
    D

    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]++;
      }
    }
    

  • 0

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


  • 0
    D

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

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

Log in to reply
 

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