LC1329 Sort the Matrix Diagonally

"""
main idea: get the diagonal val based on diff of coordinate, sort by diff in descending order, then put them back  

"""
class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        # time O(CRlg(min(R,C))) space O(RC)
        d = collections.defaultdict(list)
        row = len(mat)
        col = len(mat[0])
        for i in range(row):
            for j in range(col):
                d[i-j].append(mat[i][j])
        for k in d:
            d[k].sort(reverse=1)
        for i in range(row):
            for j in range(col):
                mat[i][j] = d[i-j].pop()
                
        return mat