A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

&nbsp;
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]]


Example 2:

Input: mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
Output: [[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]


&nbsp;
Constraints:


	m == mat.length
	n == mat[i].length
	1 &lt;= m, n &lt;= 100
	1 &lt;= mat[i][j] &lt;= 100


class Solution:
    def diagonalSort(self, A: List[List[int]]) -> List[List[int]]:
        n, m, d = len(A), len(A[0]), defaultdict(list)
        any(d[i - j].append(A[i][j]) for i in range(n) for j in range(m))
        any(d[sum_].sort(reverse=1) for sum_ in d)
        return [[d[i-j].pop() for j in range(m)] for i in range(n)]
class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int n = mat.length; 
        int m = mat[0].length;
        for(int i=0;i<m;i++){
            give(0,i,mat,n,m);
        }
        for(int i=1;i<n;i++){
            give(i,0,mat,n,m);
        }
        return mat;
    }
    public void give(int i,int j,int[][] mat,int n,int m){
        int[] dig = new int[Math.min(m-j,n-i)];
        int r = i;
        int c = j;
        int k = 0;
        while(r<n && c<m){
            dig[k] = mat[r][c];
            r++;
            c++;
            k++;
        }
        Arrays.sort(dig);
        k = 0;
        while(i<n && j<m){
            mat[i][j] = dig[k];
            i++;
            j++;
            k++;
        }
    }
}
class Solution {
public:
	void sortmat(int i,int j,vector<vector<int>>& mat,int m,int n,vector<int>& temp){
		if(i>=m || j>=n){
			sort(temp.begin(),temp.end());
			return ;
		}
		temp.push_back(mat[i][j]);
		sortmat(i+1,j+1,mat,m,n,temp);
		mat[i][j]=temp.back();
		temp.pop_back();
	}

	vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
		int m=mat.size();
		int n=mat[0].size();
		vector<int>temp;
//      For column
		for(int j=0;j<n;j++) sortmat(0,j,mat,m,n,temp);
//      For Row
		for(int i=1;i<m;i++) sortmat(i,0,mat,m,n,temp);
		return mat;
	}
};
/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var diagonalSort = function(mat) {
const res=new Array(mat.length);
    
for(let i=0;i<mat.length;i++)
    res[i]=new Array(mat[i].length);

    
for(let i=0;i<mat.length;i++){
    for(let j=0;j<mat[i].length;j++){
        if(i===0 || j===0){
            const scale= i-j;
            let val=[],index=[];
            
            for(let i=0;i<mat.length;i++){
                for(let j=0;j<mat[i].length;j++){
                    if(scale===i-j){
                        val.push(mat[i][j]);    
                        index.push([i,j]);            
                    }
                }
            }
            val=val.sort((a,b)=>a-b);
            index.forEach(([x,y],id)=>res[x][y]=val[id]);
        }
    }
}
    return res;

};
Sort the Matrix Diagonally