January-Leetcoding-Challenge-2021/23. Sort the Matrix Diagonally at main · Algorithms-Made-Easy/January-Leetcoding-Challenge-2021 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m=mat.length;
        int n=mat[0].length;

        //row=0
        for(int col=0;col<n;col++){
            sort(mat,0,col,m,n);
        }

        //col=0
        for(int row=1;row<m;row++){
            sort(mat,row,0,m,n);
        }

        return mat;
    }

    void sort(int[][] mat,int row,int col,int m,int n){
        List<Integer> values=new ArrayList<>();
        int r=row,c=col;
        while(r<m && c<n){
            values.add(mat[r][c]);
            r++;
            c++;
        }

        Collections.sort(values);

        r=row;
        c=col;
        int ind=0;
        while(r<m && c<n){
            mat[r][c]=values.get(ind++);
            r++;
            c++;
        }
    }
}

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m=mat.length;
        int n=mat[0].length;

        //row=0
        for(int col=0;col<n;col++){
            sort(mat,0,col,m,n);
        }

        //col=0
        for(int row=1;row<m;row++){
            sort(mat,row,0,m,n);
        }

        return mat;
    }

    void sort(int[][] mat,int row,int col,int m,int n){
        int[] values=new int[101];
        int r=row,c=col;
        while(r<m && c<n){
            // values.add(mat[r][c]);
            values[mat[r][c]]++;
            r++;
            c++;
        }

        r=row;
        c=col;

        for(int i=1;i<101;i++){
            if(values[i]>0){
                int count=values[i];
                while(count-->0){
                    mat[r][c]=i;
                    r++;
                    c++;
                }
            }
        }
    }
}