1
class Solution {
2
 public:
3
  void sortmat(int i, int j, vector<vector<int>> &mat, int m, int n, vector<int> &temp) {
4
    if (i >= m || j >= n) {
5
      sort(temp.begin(), temp.end());
6
      return;
7
    }
8
    temp.push_back(mat[i][j]);
9
    sortmat(i + 1, j + 1, mat, m, n, temp);
10
    mat[i][j] = temp.back();
11
    temp.pop_back();
12
  }
13

14
  vector<vector<int>> diagonalSort(vector<vector<int>> &mat) {
15
    int m = mat.size();
16
    int n = mat[0].size();
17
    vector<int> temp;
18
    //      For column
19
    for (int j = 0; j < n; j++) sortmat(0, j, mat, m, n, temp);
20
    //      For Row
21
    for (int i = 1; i < m; i++) sortmat(i, 0, mat, m, n, temp);
22
    return mat;
23
  }
24
};