class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int r = mat.size();
        int c = mat[0].size();
        int cnt[100];

        int dr = r - 1;
        int dc = 0;

        int diagonals = r + c - 1;

        vector<vector<int>> anis;

        for(int i = 0; i < r; i++) {
            vector<int> vec;
            anis.push_back(vec);
        }

        for(int i = 0; i < diagonals; i++) {
            int sr = dr;
            int sc = dc;

            memset(cnt, 0, sizeof cnt);
            while(sr < r && sc < c) {
                cnt[mat[sr][sc]]++;
                sr++;
                sc++;
            }

            int pushInd = dr;
            for(int num = 1; num <= 100; num++) {
                int times = cnt[num];
                for(int k = 0; k < times; k++) {
                    anis[pushInd].push_back(num);
                    pushInd++;
                }
            }

            if(dr > 0) {
                dr--;
            } else {
                dc++;
            }
        }

        return anis;
    }
};