Problem statement

https://binarysearch.com/problems/Diagonal-Sort/

Solution

Equal to Leetcode 1329. Sort the Matrix Diagonally

Complexity

Time complexity is O(mn*log(min(m, n)), space complexity is O(mn).

Code

class Solution:
    def solve(self, mat):
        m, n, d = len(mat), len(mat[0]), defaultdict(list)
        for i in range(m):
            for j in range(n):
                d[j - i].append(mat[i][j])
                
        for k in d:
            for i, num in enumerate(sorted(d[k])):
                mat[i + max(-k, 0)][k + i + max(-k, 0)] = num
                
        return mat