1
class Solution {
2
  public int[][] diagonalSort(int[][] mat) {
3
    int n = mat.length;
4
    int m = mat[0].length;
5
    for (int i = 0; i < m; i++) {
6
      give(0, i, mat, n, m);
7
    }
8
    for (int i = 1; i < n; i++) {
9
      give(i, 0, mat, n, m);
10
    }
11
    return mat;
12
  }
13

14
  public void give(int i, int j, int[][] mat, int n, int m) {
15
    int[] dig = new int[Math.min(m - j, n - i)];
16
    int r = i;
17
    int c = j;
18
    int k = 0;
19
    while (r < n && c < m) {
20
      dig[k] = mat[r][c];
21
      r++;
22
      c++;
23
      k++;
24
    }
25
    Arrays.sort(dig);
26
    k = 0;
27
    while (i < n && j < m) {
28
      mat[i][j] = dig[k];
29
      i++;
30
      j++;
31
      k++;
32
    }
33
  }
34
}