Sort 2D matrix with constraint


  • 0
    E

    Given a 2D matrix of integers, sort it such that:

    • all rows and columns are sorted
    • all items in the same row are unique

    You may assume the input matrix is always valid, meaning that such a sort is always possible.

    For example:

    1 3 4 5
    2 3 4 6
    2 4 5 6
    3 4 5 7
    

    One kinda trivial solution is to sort the 2D matrix column wise. For example, you can push all items into a heap and pop one after another, putting it into the matrix column after column. This would be a O(n lg n) time complexity where n is the number of items in the matrix, i.e., n = rows*cols. Can you do better?

    Follow-up: What if all items in the same column are also unique?

    For example:

    1 2 3 4
    2 3 4 5
    3 4 5 6
    4 5 6 7

Log in to reply
 

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