1329. Sort the Matrix Diagonally
https://leetcode.com/problems/sort-the-matrix-diagonally/
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.lengthn == mat[i].length1 <= m, n <= 1001 <= mat[i][j] <= 100
---
Intuition
Collect each diagonal into a data structure
Note r - c for each cell uniquely identifies the diagonal
Note There are (m + n - 1) diagonals
Sort each diagonal
Map the sorted element back to the matrix
Note - Math.min(r, c) rightly identifies index of element from data structure
---
Time - O((m + n) * log(m + n) + m * n)
Space - O(m * n)
---
Note - Problem statement mentions m[i][j] <= 100 and m, n between 1.. 100
Counting sort is faster in this case
TODO - Implement counting sort
---
