sort-the-matrix-diagonally

< Previous 　　　　　　　　　　　　　　　　 Next >

1329. Sort the Matrix Diagonally (Medium)

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

 

Example 1:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

 

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• 1 <= mat[i][j] <= 100

Related Topics

[Sort] [Array]

Hints

Hint 1

Use a data structure to store all values of each diagonal.

Hint 2

How to index the data structure with the id of the diagonal?

Hint 3

All cells in the same diagonal (i,j) have the same difference so we can get the diagonal of a cell using the difference i-j.